Fák bejárása (sorrend, előrendelés és utánrendelés) példákkal
Mi az a Tree Traversal?
A fa adatszerkezetében a bejárás a csomópontok valamilyen meghatározott módon történő meglátogatását jelenti. Nodes2 típusú bejárások léteznek. Általában ez a fajta bejárás a bináris fán alapul. A bináris fa azt jelenti, hogy minden csomópontnak maximum 2 csomópontja lehet.
A bináris fa egy jól ismert adatstruktúra. Van egy bináris keresési fa (BST). Ezt a fajta bejárást különféle célokra használják. A szintrend bejárása, két csomópont közötti mélység kiszámítására szolgál. Létezik egy másik fafajta, az „AVL”, ahol egy csomópont magasságának kiszámítása szükséges. A tömbben egy bináris fát is ábrázolhatunk, de a memória optimalizálásához struktúrát és mutatót használunk a következő csomópontra való hivatkozáshoz.
A fa bejárásának típusai
Ahogy megbeszéltük bináris fák, most az egyes bejárástípusokat tárgyaljuk. A típustól függően kétféle bejárás létezik. Korábban már említettük a szintrend vagy a Breadth-First Traversal szükségességét. Most Mélység-első bejárás hasonlóan a post order egy csomópont törlésére szolgál (erről később lesz szó), az előrendelés a bináris fa másolására szolgál, az „inorder” pedig nem csökkenő módon halad át a fán.
- Breadth-First Traversal
- Mélység-első bejárás
- Előrendelési bejárás
- Utólagos bejárás
- Rend szerinti bejárás
Breadth-First Traversal
Szintrendű bejárásnak is nevezik. Tekintsük a következő fát a szintrend bejárás bemutatására.
Tehát az „1” gyökércsomópontból indulunk ki. 1. szintként lesz megjelölve. Ekkor az algoritmus az aktuális csomópont összes gyermekéhez megy. Most meglátogatjuk a 2. és 3. csomópontot. 2-es szintként lesznek megjelölve.
Ezt követően, mivel 2 csomópontunk van a 2. szinten, meglátogatjuk a gyerekeiket is. Tehát meglátogatjuk az 5,6,8,7, 3, XNUMX, XNUMX-et, és XNUMX-as szintként jelöljük meg őket.
Csomópont szintje = szülőcsomópont szintje + 1
1. szint: 1
2. szint: 2 3
3. szint: 5 6 8 7
Hasonló algoritmust használnak a BFS (Breadth-First-Search).
Íme a szintrend bejárásának pszeudokódja:
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
Vegyünk egy példát, mint korábban. Ennél a bejárástípusnál először a bal oldali részfát keressük fel, majd a gyökeret, majd ezt követően a jobb oldali részfát. Az emlékezés megkönnyítésére azt mondhatjuk, hogy a sorrend úgy megy, mint bal-gyökér-jobb.
Tegyük fel, hogy a teljes fa gyökere 1. Most az algoritmus a következő:
- Látogassa meg az 1. csomópont bal oldali részfáját.
- Az aktuális csomópont 2 (mivel az 1 bal oldali részfája)
- Látogassa meg a 2 bal oldali részfáját. Az aktuális csomópont ezúttal 5 lesz.
- Az 5-ösre költözve nincs gyermeke, így az 5-ös csomópont látogatottként lesz megjelölve. Visszatér a szülőcsomóponthoz; ami a 2.
- Mivel a 2 bal oldali részfa meg van látogatva, most a 2 is meg lesz látogatva.
- A algoritmus áthelyezi az aktuális csomópontot a 2. csomópont jobb oldali részfájába, amely a 6. csomópont. A 6. csomópont meglátogatása után. A 2. szülőcsomópontra lép.
- Mivel a 2. csomópont látogatott, most meglátogatjuk a 2 szülőjét; ami az 1. csomópont.
- Ezt követően meglátogatjuk a megfelelő részfát.
Tehát a végső bejárás így fog kinézni:
Sorrendben: 5 → 2 → 6 → 1 → 8 → 3 → 7
Íme az In-order bejárás pszeudokódja:
InOrder(node): if node is not null: InOrder(node.left) print node.value InOrder(node.right)
Ez az inorder bejárás rekurzív algoritmusa. A Bináris keresőfa (BST), Az Inorder bejárás megadja az értékek rendezett tömbjét.
Rendelés utáni bejárás
Ebben a bejárásban először a bal szélső részfán fogjuk bejárni, majd a gyökér után a jobb szélső részfán. Minden bejárás utólagos rendelésben történik. Mutassunk egy példát:
Itt gyökér = 1,
- Először a bal oldali részfához megyünk. Tehát a gyökér 2 lesz.
- Ekkor a 2 elhagyta a részfát, így az 5-ös csomópontra megyünk. Most a gyökér 5.
- Nincs bal oldali részfája, és nincs jobb oldali részfája sem. Tehát most az 5-ös csomópontot meglátogatottként jelöljük meg, és áttérünk a szülőcsomópontjára.
- Most a gyökér 2, és a bal oldali részfája teljesen fel van látogatva. Most áttérünk a jobb oldali részfájára. Tehát a gyökér 6 lesz.
- Mivel a 6. csomópontnak nincs bal- és jobboldali részfája, a 6. csomópontot meglátogatottnak jelöljük, és áttérünk a 2. szülőcsomópontra.
- Most a 2. csomópont bal és jobb oldali részfáját is meglátogatják. Ez is látogatottként lesz megjelölve.
- Áttérünk a 2. csomópont szülőjére, amely az 1. csomópont.
- A bal oldali részfa meglátogatása az 1. gyökér számára. Most hasonlóképpen meglátogatjuk a jobb oldali részfát.
A jelölt kör a jobb oldali részfa. Most meglátogatjuk a jobb oldali részfát, ahogy a bal oldali részfát. Ezt követően meglátogatjuk a csomópontot. Tehát a végső bejárás a következő lesz:
Utólagos rendelés: 5 → 6 → 2 → 8 → 7 → 3 → 1
Íme a rendelés utáni bejárás pszeudokódja:
PostOrder(node): if node is not null: PostOrder(node.left) PostOrder(node.right) print node.value
Előrendelési bejárás
Az előrendelési bejárásnál az algoritmus először a gyökércsomópontot keresi fel, majd ezt követően a bal, illetve a jobb oldali részfába lép. A könnyebb érthetőség kedvéért gondolhatunk előrendelhető bejárási látogatásokra, mint pl gyökér → bal-jobb.
Tehát válasszuk az 1-es csomópontot gyökérként.
- Az algoritmus szerint először a gyökér kerül felfedezésre, majd a bal, majd a jobb oldali részfa.
- Tehát meglátogatjuk a gyökér 1-et. Ezután áttérünk a bal oldali részfájára. A gyökér 2 lesz.
- Meglátogatjuk a 2. csomópontot, és áttérünk a bal oldali részfájára. Tehát a gyökér 3 lesz.
- Meglátogatjuk a 3. csomópontot, majd áttérünk a szülőcsomópontjára. Most a 2. csomópont és annak bal oldali részfája kerül megtekintésre. Ideje meglátogatni a megfelelő részfát.
- A megfelelő részfára lépünk, a gyökér 4 lesz. Meglátogatjuk a 4-et. Mivel a 4-nek nincs gyermek csomópontja, áttérünk a szülőjére.
- Most a gyökér 2, és a bal és a jobb oldali részfával együtt felkeresik. Tehát áttérünk a szülőcsomópontra. Most a gyökér 1 lesz.
- Hasonlóképpen meglátogatjuk a megfelelő részfát.
Előrendelés: 1 → 2 → 3 → 4 → 5 → 6 → 7
Íme a rendelés utáni bejárás pszeudokódja:
PreOrder(node): if node is not null: print node.value PreOrder(node.left) PreOrder(node.right)
Végrehajtás 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)
output:
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
Megvalósítás C-ben
#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); }
Kimenet:
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
Végrehajtása C++ (std:queue használata a szintrendhez)
#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