Обхід дерева (в порядку, попередньому порядку, після замовлення)

Що таке обхід дерева?

У деревоподібній структурі даних обхід означає відвідування вузлів певним чином. Існує два типи обходів. Зазвичай цей вид обходу базується на бінарному дереві. Бінарне дерево означає, що кожен вузол може мати максимум 2 вузли.

Двійкове дерево — добре відома структура даних. Існує також бінарне дерево пошуку (BST). Цей тип обходу використовується для різних цілей. Обхід порядку рівня, використовується для обчислення глибини між двома вузлами. Існує інший тип дерева під назвою «AVL», де необхідно обчислити висоту вузла. Ми можемо представити двійкове дерево в масиві, але для оптимізації пам’яті ми будемо використовувати структуру та покажчик для посилання на наступний вузол.

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

Як ми говорили бінарні дерева, тепер ми обговоримо окремі типи обходів. Залежно від типів розрізняють два види обходу. Раніше ми згадували про необхідність порядку рівнів або обходу в ширину. Зараз Перехід на глибину як post order використовується для видалення вузла (ми обговоримо це пізніше), preorder використовується для копіювання двійкового дерева, а «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. Тепер так само ми відвідаємо праве піддерево.

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

PostOrder: 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

Поширені запитання