Обхождане на дърво (по ред, предварителна поръчка, след поръчка)

Какво е Tree Traversal?

В дървовидната структура от данни, обхождането означава посещение на възли по някакъв специфичен начин. Има два вида обхождания. Обикновено този вид обхождане се основава на двоичното дърво. Двоично дърво означава, че всеки възел може да има максимум 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. Сега по подобен начин ще посетим дясното поддърво.

Маркираният кръг е дясното поддърво. Сега ще посетим дясното поддърво, както посетихме лявото поддърво. След това ще посетим възела. Така окончателното преминаване ще бъде:

Пощенска поръчка: 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 няма дъщерен възел, ще се преместим към неговия родител.
• Сега root е 2 и се посещава заедно с лявото и дясното му поддърво. И така, ще преминем към неговия родителски възел. Сега root става 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

Въпроси и Отговори