Průchody stromů (inorder, preorder & postorder) s příklady
Co je to Tree Traversal?
Ve stromové datové struktuře znamená procházení určitým specifickým způsobem návštěvu uzlů. Existují uzly2 typy průchodů. Obecně je tento druh procházení založen na binárním stromu. Binární strom znamená, že každý uzel může mít maximálně 2 uzly.
Binární strom je dobře známá datová struktura. K dispozici je také strom binárního vyhledávání (BST). Tento typ průchodu se používá pro různé účely. Přechod úrovňového řádu, používá se pro výpočet hloubky mezi dvěma uzly. Existuje další druh stromu zvaný „AVL“, kde je nutný výpočet výšky uzlu. Můžeme reprezentovat binární strom v poli, ale pro optimalizaci paměti použijeme strukturu a ukazatel pro odkazování na další uzel.
Typy procházení stromů
Jak jsme projednali binární stromy, nyní probereme jednotlivé typy traverz. V závislosti na typech existují dva typy procházení. Dříve jsme se zmínili o nezbytnosti pořadí úrovní nebo procházení do šířky. Nyní Přechod do hloubky jako post order se používá pro smazání uzlu (probereme to později), preorder se používá pro kopírování binárního stromu a „inorder“ bude procházet strom neklesajícím způsobem.
- Přechod do šířky
- Přechod do hloubky
- Předobjednávkový průchod
- Přechod po objednávce
- Průjezd v pořadí
Přechod do šířky
Je také známý jako procházení úrovně. Podívejme se na následující strom pro demonstraci procházení řádu úrovně.
Začneme tedy od kořenového uzlu „1“. Bude označen jako úroveň 1. Poté algoritmus přejde ke všem potomkům aktuálního uzlu. Nyní navštívíme uzel 2 a 3. Budou označeny jako úroveň 2.
Poté, protože máme 2 uzly na úrovni 2, navštívíme také jejich děti. Takže navštívíme 5,6,8,7 a označíme je jako úroveň 3. Zde je věc, o které se nemluví,
Úroveň uzlu = úroveň nadřazeného uzlu + 1
Úroveň 1: 1
Úroveň 2: 2 3
Úroveň 3: 5 6 8 7
Podobný algoritmus se používá pro BFS (Breadth-First-Search).
Zde je Pseudokód pro průchod pořadím úrovní:
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)
Inorder Traversal Bianry Tree
Uveďme stejný příklad jako předtím. Při tomto typu procházení nejprve navštívíme levý podstrom, poté kořen a poté pravý podstrom. Pro snadnější zapamatování můžeme říci, že pořadí jde jako levá-kořenová-pravá.
Řekněme, že pro celý strom je kořen 1. Nyní bude algoritmus následovat:
- Navštivte levý podstrom uzlu 1.
- Aktuální uzel je 2 (protože je to levý podstrom 1)
- Navštivte levý podstrom 2. Aktuální uzel bude tentokrát 5.
- Přesunutím na 5 nemá žádné děti, takže uzel 5 bude označen jako navštívený. Vrátí se do nadřazeného uzlu; což je 2.
- Protože je navštíven levý podstrom 2, nyní budou navštíveny také 2.
- Jedno algoritmus přesune aktuální uzel do pravého podstromu uzlu 2, což je uzel 6. Po návštěvě uzlu 6 se přesune do svého nadřazeného uzlu 2.
- Protože byl navštíven uzel 2, navštívíme nyní nadřazeného uzlu 2; což je uzel 1.
- Poté navštívíme správný podstrom.
Takže konečný průchod bude vypadat takto:
V pořadí: 5 → 2 → 6 → 1 → 8 → 3 → 7
Zde je pseudokód pro průchod v pořadí:
InOrder(node): if node is not null: InOrder(node.left) print node.value InOrder(node.right)
Toto je rekurzivní algoritmus pro průchod v řádu. Pro Binární vyhledávací strom (BST), Inorder traversal dává seřazené pole hodnot.
Přechod po objednávce
V tomto procházení nejprve projdeme podstrom nejvíce vlevo a poté podstrom nejvíce vpravo za kořenem. Všechny průchody budou v Post-Order. Ukažme si příklad:
Zde pro kořen = 1,
- Nejprve přejdeme do levého podstromu. Kořen se tedy stane 2.
- Pak 2 opustil podstrom, takže přejdeme do uzlu 5. Nyní je kořen 5.
- Nemá žádný levý podstrom a také nemá žádný pravý podstrom. Nyní tedy označíme uzel 5 jako navštívený a přejdeme k jeho nadřazenému uzlu.
- Nyní je kořen 2 a jeho levý podstrom je zcela navštíven. Nyní se přesuneme do jeho pravého podstromu. Takže kořen se stane 6.
- Protože uzel 6 nemá žádný levý a pravý podstrom, označíme uzel 6 jako navštívený a přesuneme se do jeho nadřazeného uzlu 2.
- Nyní se pro uzel 2 navštěvuje levý i pravý podstrom. Bude také označen jako navštívený.
- Přesuneme se k nadřazenému uzlu 2, což je uzel 1.
- Levý podstrom je navštíven pro kořen 1. Nyní podobně navštívíme pravý podstrom.
Označený kruh je pravý podstrom. Nyní navštívíme pravý podstrom, jako jsme navštívili levý podstrom. Poté navštívíme uzel. Takže konečný průchod bude:
PostOrder: 5 → 6 → 2 → 8 → 7 → 3 → 1
Zde je pseudokód pro průchod po objednávce:
PostOrder(node): if node is not null: PostOrder(node.left) PostOrder(node.right) print node.value
Předobjednejte si Traversal
Při procházení předobjednávkou algoritmus nejprve navštíví kořenový uzel, poté se přesune do levého a pravého podstromu. Pro snazší pochopení můžeme uvažovat o předobjednávkových traverzálních návštěvách jako kořen → zleva doprava.
Vyberme tedy uzel 1 jako kořen.
- Podle algoritmu bude nejprve objeven kořen, poté levý a poté pravý podstrom.
- Navštívíme tedy kořen 1. Poté se přesuneme do jeho levého podstromu. Kořen se stává 2.
- Navštívíme uzel 2 a přesuneme se do jeho levého podstromu. Kořenem se tedy stává 3.
- Navštívíme uzel 3, poté se přesuneme do jeho nadřazeného uzlu. Nyní je navštíven uzel 2 a jeho levý podstrom. Čas na návštěvu správného podstromu.
- Přesuneme se do pravého podstromu, kořen se stane 4. Navštívíme 4. Protože 4 nemá žádný podřízený uzel, přesuneme se k jeho rodiči.
- Nyní je root 2 a je navštíven spolu s jeho levým a pravým podstromem. Přesuneme se tedy do jeho nadřazeného uzlu. Nyní se root stane 1.
- Podobně navštívíme správný podstrom.
Předobjednávka: 1 → 2 → 3 → 4 → 5 → 6 → 7
Zde je pseudokód pro průchod po objednávce:
PreOrder(node): if node is not null: print node.value PreOrder(node.left) PreOrder(node.right)
provádění 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)
Výstup:
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
Implementace v 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); }
Výstup:
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
Implementace C++ (Použití std:queue pro pořadí úrovní)
#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