Fa bejárása

Ebben az oktatóanyagban megismerkedhet a különböző fák bejárási technikáival. Emellett működő példákat talál a fa, a C, C ++, a Java és a Python különböző faátjárási módjairól.

A fán való áthaladás azt jelenti, hogy meglátogatja a fa minden csomópontját. Például fel szeretné venni a fa összes értékét, vagy megtalálni a legnagyobbat. Mindezen műveleteknél meg kell látogatnia a fa minden csomópontját.

A lineáris adatstruktúráknak, például tömböknek, halmoknak, soroknak és a kapcsolt listának csak egyetlen módja van az adatok olvasására. De egy hierarchikus adatszerkezet, mint egy fa, különböző módon haladható át.

Fa bejárása

Gondoljuk át, hogyan olvashatnánk a fa elemeit a fenti képen.

Fentről indulva, balról jobbra

 1 -> 12 -> 5 -> 6 -> 9

Alulról indulva, balról jobbra

 5 -> 6 -> 12 -> 9 -> 1

Bár ez a folyamat kissé egyszerű, nem tartja tiszteletben a fa hierarchiáját, csak a csomópontok mélységét.

Ehelyett bejárási módszereket alkalmazunk, amelyek figyelembe veszik a fa alapszerkezetét, azaz

 struct node ( int data; struct node* left; struct node* right; )

A balra és jobbra mutató struktúracsomópontnak lehetnek más bal és jobb gyermekei, ezért részfákként kell gondolnunk rájuk alcsomópontok helyett.

E szerkezet szerint minden fa kombinációja

  • Adatot hordozó csomópont
  • Két alfa
Bal és Jobb részfa

Ne feledje, hogy célunk az egyes csomópontok meglátogatása, ezért meg kell látogatnunk az alfa összes csomópontját, meg kell látogatnunk a gyökércsomópontot, és meg kell látogatnunk a jobb részfa összes csomópontját is.

Ennek sorrendjétől függően háromféle áthaladás lehet.

Belső átjárás

  1. Először keresse fel a bal alfa összes csomópontját
  2. Ezután a gyökércsomópont
  3. Látogassa meg a jobb részfa összes csomópontját
 inorder(root->left) display(root->data) inorder(root->right)

Előrendelés bejárása

  1. Látogassa meg a gyökércsomópontot
  2. Látogassa meg a bal alfa összes csomópontját
  3. Látogassa meg a jobb részfa összes csomópontját
 display(root->data) preorder(root->left) preorder(root->right)

Postai bejárás

  1. Látogassa meg a bal alfa összes csomópontját
  2. Látogassa meg a jobb részfa összes csomópontját
  3. Látogassa meg a gyökércsomópontot
 postorder(root->left) postorder(root->right) display(root->data)

Vizualizáljuk a sorrendben történő bejárást. A gyökércsomópontból indulunk ki.

Bal és Jobb részfa

Először a bal alfát járjuk át. Arra is emlékeznünk kell, hogy meglátogassuk a gyökércsomópontot és a jobb alfát, amikor ez a fa elkészült.

Tegyük mindezt egy verembe, hogy emlékezzünk.

Kazal

Most átmegyünk a verem tetején mutatott részfáig.

Ismét ugyanazt a belső rendszabályt követjük

 Bal alfa -> gyökér -> jobb alfa

A bal részfán való áthaladás után maradunk

Végső verem

Mivel az "5" csomópontnak nincsenek részfái, közvetlenül kinyomtatjuk. Ezt követően kinyomtatjuk a szülőjét "12", majd a megfelelő gyermeket "6".

A verembe rakás mindent hasznos volt, mert most, hogy a gyökércsomópont bal-alfája áthaladt, kinyomtathatjuk és a jobb alfához léphetünk.

Miután minden elemet átéltünk, megkapjuk a belső bejárást as

 5 -> 12 -> 6 -> 1 -> 9

Nem kell magunknak létrehoznunk a verem, mert a rekurzió fenntartja számunkra a megfelelő sorrendet.

Példák Python, Java és C / C ++

Python Java C C + 
 # Tree traversal in Python class Node: def __init__(self, item): self.left = None self.right = None self.val = item def inorder(root): if root: # Traverse left inorder(root.left) # Traverse root print(str(root.val) + "->", end='') # Traverse right inorder(root.right) def postorder(root): if root: # Traverse left postorder(root.left) # Traverse right postorder(root.right) # Traverse root print(str(root.val) + "->", end='') def preorder(root): if root: # Traverse root print(str(root.val) + "->", end='') # Traverse left preorder(root.left) # Traverse right preorder(root.right) root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) print("Inorder traversal ") inorder(root) print("Preorder traversal ") preorder(root) print("Postorder traversal ") postorder(root)
 // Tree traversal in Java class Node ( int item; Node left, right; public Node(int key) ( item = key; left = right = null; ) ) class BinaryTree ( // Root of Binary Tree Node root; BinaryTree() ( root = null; ) void postorder(Node node) ( if (node == null) return; // Traverse left postorder(node.left); // Traverse right postorder(node.right); // Traverse root System.out.print(node.item + "->"); ) void inorder(Node node) ( if (node == null) return; // Traverse left inorder(node.left); // Traverse root System.out.print(node.item + "->"); // Traverse right inorder(node.right); ) void preorder(Node node) ( if (node == null) return; // Traverse root System.out.print(node.item + "->"); // Traverse left preorder(node.left); // Traverse right preorder(node.right); ) public static void main(String() args) ( BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(12); tree.root.right = new Node(9); tree.root.left.left = new Node(5); tree.root.left.right = new Node(6); System.out.println("Inorder traversal"); tree.inorder(tree.root); System.out.println("Preorder traversal "); tree.preorder(tree.root); System.out.println("Postorder traversal"); tree.postorder(tree.root); ) )
 // Tree traversal in C #include #include struct node ( int item; struct node* left; struct node* right; ); // Inorder traversal void inorderTraversal(struct node* root) ( if (root == NULL) return; inorderTraversal(root->left); printf("%d ->", root->item); inorderTraversal(root->right); ) // preorderTraversal traversal void preorderTraversal(struct node* root) ( if (root == NULL) return; printf("%d ->", root->item); preorderTraversal(root->left); preorderTraversal(root->right); ) // postorderTraversal traversal void postorderTraversal(struct node* root) ( if (root == NULL) return; postorderTraversal(root->left); postorderTraversal(root->right); printf("%d ->", root->item); ) // Create a new Node struct node* createNode(value) ( struct node* newNode = malloc(sizeof(struct node)); newNode->item = value; newNode->left = NULL; newNode->right = NULL; return newNode; ) // Insert on the left of the node struct node* insertLeft(struct node* root, int value) ( root->left = createNode(value); return root->left; ) // Insert on the right of the node struct node* insertRight(struct node* root, int value) ( root->right = createNode(value); return root->right; ) int main() ( struct node* root = createNode(1); insertLeft(root, 12); insertRight(root, 9); insertLeft(root->left, 5); insertRight(root->left, 6); printf("Inorder traversal "); inorderTraversal(root); printf("Preorder traversal "); preorderTraversal(root); printf("Postorder traversal "); postorderTraversal(root); )
 // Tree traversal in C++ #include using namespace std; struct Node ( int data; struct Node *left, *right; Node(int data) ( this->data = data; left = right = NULL; ) ); // Preorder traversal void preorderTraversal(struct Node* node) ( if (node == NULL) return; cout left); preorderTraversal(node->right); ) // Postorder traversal void postorderTraversal(struct Node* node) ( if (node == NULL) return; postorderTraversal(node->left); postorderTraversal(node->right); cout left); cout right); ) int main() ( struct Node* root = new Node(1); root->left = new Node(12); root->right = new Node(9); root->left->left = new Node(5); root->left->right = new Node(6); cout << "Inorder traversal "; inorderTraversal(root); cout << "Preorder traversal "; preorderTraversal(root); cout << "Postorder traversal "; postorderTraversal(root);

érdekes cikkek...