Przemierzanie drzew (zamówienie, zamówienie w przedsprzedaży i zamówienie pocztowe) z przykładami

Co to jest przechodzenie przez drzewo?

W drzewiastej strukturze danych przechodzenie oznacza odwiedzanie węzłów w określony sposób. Istnieją 2 typy przejść. Ogólnie rzecz biorąc, ten rodzaj przechodzenia opiera się na drzewie binarnym. Drzewo binarne oznacza, że każdy węzeł może mieć maksymalnie 2 węzły.

Drzewo binarne jest dobrze znaną strukturą danych. Istnieje również drzewo wyszukiwania binarnego (BST). Ten rodzaj przejścia jest używany do różnych celów. Przechodzenie rzędu poziomów służy do obliczania głębokości pomiędzy dwoma węzłami. Istnieje inny rodzaj drzewa zwany „AVL”, w którym konieczne jest obliczenie wysokości węzła. Możemy reprezentować drzewo binarne w tablicy, ale w celu optymalizacji pamięci użyjemy struktury i wskaźnika do odwoływania się do następnego węzła.

Rodzaje przechodzenia przez drzewa

Tak jak mówiliśmy drzewa binarne, teraz omówimy poszczególne typy przejść. W zależności od rodzaju istnieją dwa rodzaje przechodzenia. Wcześniej wspominaliśmy o konieczności utrzymywania porządku poziomów lub przechodzenia wszerz. Teraz Przemierzanie w głąb Podobnie jak kolejność początkowa służy do usuwania węzłów (omówimy to później), kolejność wstępna służy do kopiowania drzewa binarnego, a kolejność „inorder” będzie przechodzić przez drzewo w sposób niemalejący.

Trawersa wszerz
Przemierzanie w głąb
Zamów przejazd w przedsprzedaży
Przejście po złożeniu zamówienia
Przechodzenie w kolejności

Trawersa wszerz

Znane jest również jako przechodzenie w kolejności poziomów. Rozważmy następujące drzewo, aby zademonstrować przechodzenie w kolejności poziomów.

Zaczniemy więc od węzła głównego „1”. Zostanie on oznaczony jako poziom 1. Następnie algorytm trafi do wszystkich dzieci bieżącego węzła. Odwiedzimy teraz węzeł 2 i 3. Będą one oznaczone jako poziom 2.

Następnie, ponieważ mamy 2 węzły na poziomie 2, odwiedzimy także ich dzieci. Odwiedzimy więc 5,6,8,7 i oznaczymy je jako poziom 3. Oto rzecz, o której nie ma mowy,

Poziom węzła = poziom węzła nadrzędnego + 1

Poziom 1: 1

Poziom 2: 2 3

Poziom 3: 5 6 8 7

Podobny algorytm stosowany jest dla BFS (Wyszukiwanie wszerz).

Oto pseudokod przejścia w kolejności poziomów:

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)

Inorderowe drzewo Bianry'ego

Weźmy ten sam przykład, co poprzednio. W tego typu przechodzeniu najpierw odwiedzamy lewe poddrzewo, następnie korzeń, a następnie prawe poddrzewo. Dla ułatwienia zapamiętywania można powiedzieć, że kolejność wygląda następująco: lewa-pierwiastek-prawa.

Załóżmy, że dla całego drzewa pierwiastkiem jest 1. Teraz algorytm będzie postępować następująco:

Odwiedź lewe poddrzewo węzła 1.
Bieżącym węzłem jest 2 (ponieważ jest to lewe poddrzewo liczby 1)

Odwiedź lewe poddrzewo 2. Tym razem bieżącym węzłem będzie 5.
Przechodząc do 5, nie ma on dzieci, więc węzeł 5 zostanie oznaczony jako odwiedzony. Powróci do węzła nadrzędnego; czyli 2.
W miarę odwiedzania lewego poddrzewa 2, teraz odwiedzane będą również 2.
Kolekcja algorytm przeniesie bieżący węzeł do prawego poddrzewa węzła 2, czyli węzła 6. Po odwiedzeniu węzła 6. przeniesie się do węzła nadrzędnego 2.
Podczas odwiedzania węzła 2 odwiedzimy teraz rodzica węzła 2; czyli węzeł 1.
Następnie odwiedzimy prawe poddrzewo.

Zatem ostateczne przejście będzie wyglądać następująco:

W kolejności: 5 → 2 → 6 → 1 → 8 → 3 → 7

Oto pseudokod przejścia w kolejności:

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

Jest to algorytm rekurencyjny dla przechodzenia wewnątrz rzędu. Dla Drzewo wyszukiwania binarnego (BST), Przechodzenie Inorder daje posortowaną tablicę wartości.

Przechodzenie po złożeniu zamówienia

Podczas tego przechodzenia najpierw przejdziemy przez poddrzewo znajdujące się najbardziej na lewo, a następnie po korzeniu przez poddrzewo znajdujące się najbardziej na prawo. Wszystkie przejścia będą realizowane w trybie Post-Order. Zademonstrujmy przykład:

Tutaj dla pierwiastka = 1,

Najpierw przejdziemy do lewego poddrzewa. Zatem pierwiastek stanie się 2.
Następnie 2 opuściło poddrzewo, więc przejdziemy do węzła 5. Teraz pierwiastkiem jest 5.
Nie ma lewego poddrzewa, nie ma też prawego poddrzewa. Zatem teraz oznaczymy węzeł 5 jako odwiedzony i przejdziemy do jego węzła nadrzędnego.

Teraz korzeń ma wartość 2, a jego lewe poddrzewo zostało całkowicie odwiedzone. Przejdziemy teraz do jego prawego poddrzewa. Zatem pierwiastek wynosi 6.
Ponieważ węzeł 6 nie ma lewego i prawego poddrzewa, zaznaczymy węzeł 6 jako odwiedzony i przejdziemy do jego węzła nadrzędnego 2.
Teraz dla węzła 2 odwiedzane jest zarówno lewe, jak i prawe poddrzewo. Ono również zostanie oznaczone jako odwiedzone.
Przejdziemy do rodzica węzła 2, czyli węzła 1.
Lewe poddrzewo jest odwiedzane dla korzenia 1. Teraz w podobny sposób odwiedzimy prawe poddrzewo.

Zaznaczony okrąg to prawe poddrzewo. Teraz odwiedzimy prawe poddrzewo tak samo, jak odwiedziliśmy lewe poddrzewo. Następnie odwiedzimy węzeł. Zatem ostatecznym przejściem będzie:

PostOrder: 5 → 6 → 2 → 8 → 7 → 3 → 1

Oto pseudokod przejścia po zamówieniu:

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

Przechodzenie przed zamówieniem

W przypadku przejścia w przedsprzedaży algorytm najpierw odwiedzi węzeł główny, a następnie przejdzie odpowiednio do lewego i prawego poddrzewa. Dla ułatwienia zrozumienia możemy pomyśleć o wizytach w przedsprzedaży, np korzeń → lewy-prawy.

Wybierzmy więc węzeł 1 jako korzeń.

Zgodnie z algorytmem najpierw zostanie odkryty korzeń, następnie lewe i prawe poddrzewo.
Odwiedzimy więc korzeń 1. Następnie przejdziemy do jego lewego poddrzewa. Korzeń staje się 2.
Odwiedzimy węzeł 2 i przejdziemy do jego lewego poddrzewa. Zatem pierwiastek staje się 3.
Odwiedzamy węzeł 3, następnie przechodzimy do jego węzła nadrzędnego. Teraz odwiedzany jest węzeł 2 i jego lewe poddrzewo. Czas odwiedzić prawe poddrzewo.
Przejdziemy do prawego poddrzewa, korzeniem będzie 4. Odwiedzimy 4. Ponieważ 4 nie ma węzła potomnego, przejdziemy do jego rodzica.
Teraz korzeń ma wartość 2 i jest odwiedzany wraz z lewym i prawym poddrzewem. Przejdziemy więc do jego węzła nadrzędnego. Teraz root staje się 1.
Podobnie odwiedzimy prawe poddrzewo.

Zamów w przedsprzedaży: 1 → 2 → 3 → 4 → 5 → 6 → 7

Oto pseudokod przejścia po zamówieniu:

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

wdrożenie w 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) & gt;
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)

Wyjście:

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

Implementacja w 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);
}