Puude läbimine (järjekorras, ettetellimisel ja järeltellimusel) koos näidetega
Mis on Tree Traversal?
Puu andmestruktuuris tähendab läbimine sõlmede külastamist mingil kindlal viisil. Seal on nodes2 tüüpi läbisõite. Üldiselt põhineb selline läbimine kahendpuul. Binaarne puu tähendab, et igal sõlmel võib olla maksimaalselt 2 sõlme.
Binaarne puu on hästi tuntud andmestruktuur. Samuti on olemas binaarne otsingupuu (BST). Seda tüüpi läbimist kasutatakse erinevatel eesmärkidel. Tasemejärjestuse läbimine, seda kasutatakse kahe sõlme vahelise sügavuse arvutamiseks. On veel üks puuliik, mida nimetatakse AVL-iks, mille puhul on vaja sõlme kõrgust arvutada. Võime esindada massiivi binaarpuud, kuid mälu optimeerimiseks kasutame struktuuri ja kursorit järgmisele sõlmele viitamiseks.
Puude läbimise tüübid
Nagu me rääkisime kahendpuud, käsitleme nüüd üksikuid läbisõidutüüpe. Sõltuvalt tüübist on kahte tüüpi läbimist. Varem oleme maininud tasemejärjestuse ehk Breadth-First Traversal'i vajalikkust. Nüüd Sügavus-esimene läbimine nagu postikorraldust kasutatakse sõlme kustutamiseks (me käsitleme seda hiljem), eeltellimust kasutatakse binaarpuu kopeerimiseks ja "inorder" läbib puu mittekahaneval viisil.
- Breadth-First Traversal
- Sügavus-esimene läbimine
- Ettetellimisel läbisõit
- Järeltellimus läbimine
- Järjekorras läbisõit
Breadth-First Traversal
Seda tuntakse ka kui taseme-järjestuse läbimist. Vaatleme järgmist puud tasemejärjestuse läbimise demonstreerimiseks.
Niisiis, alustame juursõlmest “1”. See märgitakse 1. tasemeks. Seejärel läheb algoritm kõigile praeguse sõlme lastele. Külastame nüüd sõlme 2 ja 3. Need märgitakse 2. tasemeks.
Pärast seda, kuna meil on 2. tasemel 2 sõlme, külastame ka nende lapsi. Niisiis, me külastame 5,6,8,7, 3, XNUMX, XNUMX ja märgime need XNUMX. tasemele. Siin on asi, mida ei mainita,
Sõlme tase = emasõlme tase + 1
1. tase: 1
Tase 2: 2 3
3. tase: 5 6 8 7
Sarnast algoritmi kasutatakse ka BFS (Breadth-First-Search).
Siin on tasemetellimuse läbimise pseudokood:
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
Toome sama näite, mis enne. Seda tüüpi läbimise puhul külastame esmalt vasakut alampuud, seejärel juurt ja pärast seda paremat alampuud. Meenutamise hõlbustamiseks võime öelda, et järjekord läheb nagu vasak-juur-parem.
Oletame, et kogu puu juur on 1. Nüüd järgneb algoritm:
- Külastage sõlme 1 vasakut alampuud.
- Praegune sõlm on 2 (kuna see on 1 vasakpoolne alampuu)
- Külastage vasakut alampuud 2. Praegune sõlm on seekord 5.
- Kolides 5. juurde, sellel pole lapsi, seega märgitakse sõlm 5 külastatuks. See naaseb vanemsõlme; mis on 2.
- Kuna külastatakse 2 vasakut alampuud, siis nüüd külastatakse ka 2.
- . algoritm liigutab praeguse sõlme 2. sõlme parempoolsesse alampuusse, mis on sõlm 6. Pärast sõlme 6 külastamist liigub see ülemsõlme 2.
- Kuna külastatakse sõlme 2, siis nüüd külastame 2. vanemat; mis on sõlm 1.
- Pärast seda külastame õiget alampuud.
Nii et lõplik läbimine näeb välja selline:
Järjestus: 5 → 2 → 6 → 1 → 8 → 3 → 7
Siin on järjekorras läbimise pseudokood:
InOrder(node): if node is not null: InOrder(node.left) print node.value InOrder(node.right)
See on järjestuse läbimise rekursiivne algoritm. jaoks Binaarne otsingupuu (BST), Inorder traversal annab sorteeritud väärtuste massiivi.
Tellimusejärgne läbimine
Selles läbimises läbime kõigepealt vasakpoolseima alampuu, seejärel juure järel kõige parempoolsema alampuu. Kõik läbisõidud on järeltellimusel. Toome näite:
Siin juur = 1,
- Me läheme kõigepealt vasakpoolsesse alampuusse. Nii et juurest saab 2.
- Siis on 2 lahkunud alampuust, seega läheme sõlme 5. Nüüd on juur 5.
- Sellel pole vasakut alampuud ega ka paremat alampuud. Nüüd märgime sõlme 5 külastatuks ja läheme selle emasõlme juurde.
- Nüüd on juur 2 ja selle vasak alampuu on täielikult külastatud. Liigume nüüd selle paremasse alampuusse. Nii et juur muutub 6-ks.
- Kuna sõlmel 6 pole vasakut ja paremat alampuud, märgime sõlme 6 külastatuks ja liigume selle emasõlme 2 juurde.
- Nüüd külastatakse sõlme 2 jaoks nii vasakut kui ka paremat alampuud. Ka see märgitakse külastatuks.
- Liigume 2. sõlme emale, mis on sõlm 1.
- Vasakpoolset alampuud külastatakse juur 1 jaoks. Nüüd külastame samamoodi ka paremat alampuud.
Märgitud ring on parempoolne alampuu. Nüüd külastame paremat alampuud, nagu me külastasime vasakut alampuud. Pärast seda külastame sõlme. Nii et viimane läbimine on järgmine:
Järeltellimus: 5 → 6 → 2 → 8 → 7 → 3 → 1
Siin on tellimusejärgse läbimise pseudokood:
PostOrder(node): if node is not null: PostOrder(node.left) PostOrder(node.right) print node.value
Ettetellige läbimine
Eeltellimuse läbimise jaoks külastab algoritm kõigepealt juursõlme, seejärel liigub see vastavalt vasakule ja paremale alampuule. Arusaadavuse hõlbustamiseks võime mõelda ettetellitavatele läbisõidukülastustele nagu juur → vasak-parem.
Niisiis, valime juureks sõlme 1.
- Algoritmi kohaselt avastatakse kõigepealt juur, seejärel vasak ja seejärel parem alampuu.
- Niisiis, me külastame juurt 1. Seejärel liigume selle vasakpoolsesse alampuusse. Juurest saab 2.
- Külastame sõlme 2 ja liigume selle vasakpoolsesse alampuusse. Niisiis, juur muutub 3-ks.
- Külastame sõlme 3, seejärel liigume selle ülemsõlme. Nüüd külastatakse sõlme 2 ja selle vasakut alampuud. Aeg külastada õiget alampuud.
- Liigume paremale alampuule, juureks saab 4. Külastame 4. Kuna 4-l ei ole alampuud, liigume selle vanema juurde.
- Nüüd on juur 2 ja seda külastatakse koos selle vasaku ja parema alampuuga. Nii et liigume selle emasõlme juurde. Nüüd saab juurtest 1.
- Samamoodi külastame õiget alampuud.
Ettetellimine: 1 → 2 → 3 → 4 → 5 → 6 → 7
Siin on tellimusejärgse läbimise pseudokood:
PreOrder(node): if node is not null: print node.value PreOrder(node.left) PreOrder(node.right)
Rakendamine sisse 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äljund:
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
Rakendamine C-s
#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äljund:
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
Programmi rakendamine C++ (Kasutades taseme järjestuse jaoks std:järjekorda)
#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