Обход дерева (в порядке, в предварительном порядке, в обратном порядке)

Что такое обход дерева?

В древовидной структуре данных обход означает посещение узлов определенным образом. Существует два типа обхода. Как правило, этот тип обхода основан на бинарном дереве. Бинарное дерево означает, что каждый узел может содержать максимум 2 узла.

Бинарное дерево — это хорошо известная структура данных. Также есть дерево двоичного поиска (BST). Этот тип обхода используется для различных целей. Обход порядка уровней. Используется для расчета глубины между двумя узлами. Есть еще один вид дерева, называемый «AVL», в котором необходимо вычислить высоту узла. Мы можем представить двоичное дерево в массиве, но для оптимизации памяти мы будем использовать структуру и указатель для ссылки на следующий узел.

Типы обхода дерева

Как мы обсуждали бинарные деревья, теперь обсудим отдельные типы обходов. В зависимости от типа различают два типа обхода. Ранее мы упоминали о необходимости порядка уровней или обхода в ширину. Сейчас Обход в глубину например, почтовый порядок используется для удаления узла (мы обсудим это позже), предварительный порядок используется для копирования двоичного дерева, а «inorder» будет проходить по дереву в неубывающем порядке.

• Обход в ширину
• Обход в глубину
• Предварительный заказ обхода
• Обход после заказа
• Обход по порядку

Обход в ширину

Это также известно как обход уровня. Давайте рассмотрим следующее дерево для демонстрации обхода уровня.

Итак, начнем с корневого узла «1». Он будет отмечен как уровень 1. Тогда алгоритм перейдет ко всем дочерним элементам текущего узла. Сейчас мы посетим узлы 2 и 3. Они будут отмечены как уровень 2.

После этого, поскольку у нас есть 2 узла на уровне 2, мы посетим и их детей. Итак, мы посетим 5,6,8,7 и отметим их как уровень 3. Вот о чем не стоит упоминать:

Уровень узла = уровень родительского узла + 1.

Уровень 1: 1

Уровень 2: 2 3

Уровень 3: 5 6 8 7

Аналогичный алгоритм используется для BFS (Поиск в ширину).

Вот псевдокод для обхода порядка уровней:

level_order(node)
Q → Queue()
Q.push(node)
while !Q.empty():
    current_node = Q.pop()
    print current_node.value
# Checking if the current node have any child or not
if current_node.left is not NULL:
    Q.push(current_node.left)
if current_node.right is not NULL:
    Q.push(current_node.right)

Бинарное дерево с обходом в порядке возрастания

Давайте возьмем тот же пример, что и раньше. При этом типе обхода мы сначала посещаем левое поддерево, затем корень и после этого правое поддерево. Для простоты запоминания мы можем сказать, что порядок идет как левый корень-правый.

Допустим, для всего дерева корень равен 1. Теперь алгоритм будет следующим:

• Посетите левое поддерево узла 1.
• Текущий узел равен 2 (так как это левое поддерево 1).

• Посетите левое поддерево дерева 2. На этот раз текущий узел будет номером 5.
• При переходе к 5 у него нет дочерних узлов, поэтому узел 5 будет помечен как посещенный. Он вернется к родительскому узлу; что равно 2.
• Поскольку посещено левое поддерево дерева 2, теперь будет посещено и 2.
• алгоритм переместит текущий узел в правое поддерево узла 2, то есть узла 6. После посещения узла 6 он переместится к своему родительскому узлу 2.
• Поскольку узел 2 посещен, теперь мы посетим родителя узла 2; это узел 1.
• После этого мы посетим правое поддерево.

Таким образом, окончательный обход будет выглядеть так:

В порядке: 5 → 2 → 6 → 1 → 8 → 3 → 7.

Вот псевдокод для обхода по порядку:

InOrder(node):
  if node is not null:
    InOrder(node.left)
  print node.value
    InOrder(node.right)

Это рекурсивный алгоритм обхода по порядку. Для Дерево двоичного поиска (BST), Обход в неупорядоченном порядке дает отсортированный массив значений.

Обход после заказа

В этом обходе мы сначала пройдем самое левое поддерево, а затем самое правое поддерево после корня. Все обходы будут в пост-порядке. Продемонстрируем пример:

Здесь для корня = 1,

• Сначала мы перейдем к левому поддереву. Таким образом, корень станет 2.
• Тогда 2 покинул поддерево, поэтому мы перейдем к узлу 5. Теперь корень равен 5.
• У него нет левого поддерева, а также нет правого поддерева. Итак, теперь мы отметим узел 5 как посещенный и перейдем к его родительскому узлу.

• Теперь корень равен 2, и его левое поддерево полностью посещено. Теперь мы перейдем к его правому поддереву. Таким образом, корень становится 6.
• Поскольку узел 6 не имеет левого и правого поддерева, мы отметим узел 6 посещенным и перейдем к его родительскому узлу 2.
• Теперь для узла 2 посещаются как левое, так и правое поддерево. Он также будет помечен как посещенный.
• Мы перейдем к родительскому узлу 2, то есть узлу 1.
• Левое поддерево посещается для корня 1. Теперь аналогичным образом посетим правое поддерево.

Отмеченный кружок — это правое поддерево. Теперь мы посетим правое поддерево так же, как посетили левое поддерево. После этого мы посетим узел. Итак, окончательный обход будет:

Постзаказ: 5 → 6 → 2 → 8 → 7 → 3 → 1

Вот псевдокод для обхода пост-заказа:

PostOrder(node):
    if node is not null:
       PostOrder(node.left)
       PostOrder(node.right)
       print node.value

Предварительный заказ

Для обхода по предзаказу алгоритм сначала посетит корневой узел, после чего переместится в левое и правое поддерево соответственно. Для простоты понимания мы можем подумать о посещении обхода по предварительному заказу, например корень → лево-право.

Итак, давайте выберем узел 1 в качестве корня.

• Согласно алгоритму, сначала будет обнаружен корень, затем левое, а затем правое поддерево.
• Итак, мы посетим корень 1. Затем перейдем в его левое поддерево. Корень становится 2.
• Мы перейдём к узлу 2 и перейдём к его левому поддереву. Таким образом, корнем станет узел 3.
• Мы посещаем узел 3, затем переходим к его родительскому узлу. Теперь посещен узел 2 и его левое поддерево. Время посетить нужное поддерево.
• Мы перейдем к правому поддереву, корень станет 4. Мы посетим 4. Поскольку у 4 нет дочернего узла, мы перейдем к его родительскому узлу.
• Теперь корень равен 2, и он посещается вместе с его левым и правым поддеревом. Итак, мы перейдем к его родительскому узлу. Теперь корень становится 1.
• Аналогично мы посетим правое поддерево.

Предзаказ: 1 → 2 → 3 → 4 → 5 → 6 → 7

Вот псевдокод для обхода массива в порядке предварительного просмотра:

PreOrder(node):
   if node is not null:
     print node.value
         PreOrder(node.left)
         PreOrder(node.right)

Реализация в Python

class Node:
    def __init__(self, item):
    self.left = None
self.right = None
self.val = item
# creating a tree data structure
def inorder(root):
#checking if the root is null or not
if root:
    inorder(root.left)
# recursively calling left subtree
print(str(root.val) + " ", end = '')
inorder(root.right)
# recursively calling right subtree
def postorder(root):
    if root:
    postorder(root.left)
postorder(root.right)
print(str(root.val) + " ", end = '')
def preorder(root):
    if root:
    print(str(root.val) + " ", end = '')
preorder(root.left)
preorder(root.right)
def levelOrder(root):
    queue = list()
queue.append(root)
while len(queue) >
0:
    current = queue[0]
queue = queue[1: ]
print(str(current.val) + " ", end = "")
if current.left:
    queue.append(current.left)
if current.right:
   queue.append(current.right)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print("\nLevelOrder traversal:\t", end = " ")
levelOrder(root)
print("\nInorder traversal:\t", end = " ")
inorder(root)
print("\nPreorder traversal:\t", end = " ")
preorder(root)
print("\nPostorder traversal:\t", end = " ")
postorder(root)

Выход:

LevelOrder traversal:  1 2 3 4 5 6 7
Inorder traversal:     4 2 5 1 6 3 7
Preorder traversal:    1 2 4 5 3 6 7
Postorder traversal:   4 5 2 6 7 3 1

Реализация на C

#include <stdio.h>
#include <stdlib.h>
struct node {
   int value;
   struct node* left;
   struct node* right;
};
// Inorder traversal
void InOrder(struct node* root) {
   if (root == NULL) return;
   InOrder(root->left);
   printf("%d ", root->value);
   InOrder(root->right);
}
// PreOrder traversal
void PreOrder(struct node* root) {
  if (root == NULL) return;
  printf("%d ", root->value);
  PreOrder(root->left);
  PreOrder(root->right);
}
// PostOrder traversal
void PostOrder(struct node* root) {
  if (root == NULL) return;
  PostOrder(root->left);
  PostOrder(root->right);
  printf("%d ", root->value);
}
// Create a new Node
struct node* createNode(int value) {
  struct node* newNode = malloc(sizeof(struct node));
  newNode->value = value;
  newNode->left = NULL;
  newNode->right = NULL;
  return newNode;
}
int main() {
  struct node* root = createNode(1);
  root->left = createNode(2);
  root->right = createNode(3);
  root->left->left = createNode(4);
  root->left->right = createNode(5);
  root->right->left = createNode(6);
  root->right->right = createNode(7);
  printf("Inorder traversal:\t");
  InOrder(root);
  printf("\PreOrder traversal:\t");
  PreOrder(root);
  printf("\nPostOrder traversal:\t");
  PostOrder(root);
}

Выход:

Inorder traversal: 4 2 5 1 6 3 7
Preorder traversal: 1 2 4 5 3 6 7
Postorder traversal: 4 5 2 6 7 3 1

Реализация C++ (Используется std::queue для определения порядка уровней)

#include <stdio.h>
#include <stdlib.h>
#include<queue>
typedef struct node {
  int value;
  struct node* left;
  struct node* right;
}node;
// Inorder traversal
void InOrder(struct node* root) {
  if (root == NULL) return;
  InOrder(root->left);
  printf("%d ", root->value);
  InOrder(root->right);
}
// PreOrder traversal
void PreOrder(struct node* root) {
  if (root == NULL) return;
  printf("%d ", root->value);
  PreOrder(root->left);
  PreOrder(root->right);
}
// PostOrder traversal
void PostOrder(struct node* root) {
  if (root == NULL) return;
  PostOrder(root->left);
  PostOrder(root->right);
  printf("%d ", root->value);
}
void LevelOrder(struct node* root){
   std::queue<struct node*> Q;
   Q.push(root);
   while(!Q.empty()){
   struct node* current = Q.front();
   Q.pop();
   printf("%d ",current->value);
 if(current->left)
   Q.push(current->left);
 if(current->right)
   Q.push(current->right);
  }
}
// Create a new Node
struct node* createNode(int value) {
  struct node* newNode = new node();
  newNode->value = value;
  newNode->left = NULL;
  newNode->right = NULL;
  return newNode;
}
int main() {
  struct node* root = createNode(1);
  root->left = createNode(2);
  root->right = createNode(3);
  root->left->left = createNode(4);
  root->left->right = createNode(5);
  root->right->left = createNode(6);
  root->right->right = createNode(7);
  printf("Level Order traversal:\t");
  LevelOrder(root);
  printf("\nInorder traversal:\t");
  InOrder(root);
  printf("\nPreOrder traversal:\t");
  PreOrder(root);
  printf("\nPostOrder traversal:\t");
  PostOrder(root);
}

LevelOrder traversal:  1 2 3 4 5 6 7
Inorder traversal:     4 2 5 1 6 3 7
Preorder traversal:    1 2 4 5 3 6 7
Postorder traversal:   4 5 2 6 7 3 1

Часто задаваемые вопросы (FAQ)