Traverz stromu

V tomto výučbe sa dozviete o rôznych technikách prechodu stromov. Nájdete tiež pracovné príklady rôznych metód prechodu stromov v jazykoch C, C ++, Java a Python.

Prechod stromom znamená navštíviť každý uzol na strome. Možno budete chcieť pridať všetky hodnoty do stromu alebo nájsť najväčšiu. Pri všetkých týchto operáciách budete musieť navštíviť každý uzol stromu.

Lineárne dátové štruktúry ako polia, komíny, fronty a prepojený zoznam majú iba jeden spôsob čítania údajov. Ale hierarchickú dátovú štruktúru ako strom je možné prechádzať rôznymi spôsobmi.

Traverz stromu

Zamyslime sa nad tým, ako môžeme čítať prvky stromu na obrázku vyššie.

Začínajúc zhora, zľava doprava

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

Začínajúc zdola, zľava doprava

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

Aj keď je tento proces trochu ľahký, nerešpektuje hierarchiu stromu, iba hĺbku uzlov.

Namiesto toho používame metódy prechodu, ktoré berú do úvahy základnú štruktúru stromu, tj

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

Štruktúrny uzol, na ktorý ukazuje ľavá a pravá strana, môže mať ďalšie ľavé a pravé deti, takže by sme ich mali považovať za sub-stromy namiesto poduzlov.

Podľa tejto štruktúry je každý strom kombináciou

  • Uzol nesúci dáta
  • Dva podstromy
Ľavý a pravý podstrom

Pamätajte, že našim cieľom je navštíviť každý uzol, takže musíme navštíviť všetky uzly v podstrome, navštíviť koreňový uzol a tiež navštíviť všetky uzly v pravom podstrome.

Podľa toho, v akom poradí to robíme, môžu existovať tri typy prechodu.

Traverz inorder

  1. Najskôr navštívte všetky uzly v ľavom podstrome
  2. Potom koreňový uzol
  3. Navštívte všetky uzly v pravom podstrome
 inorder(root->left) display(root->data) inorder(root->right)

Predobjednajte si prechod

  1. Navštívte koreňový uzol
  2. Navštívte všetky uzly v ľavom podstrome
  3. Navštívte všetky uzly v pravom podstrome
 display(root->data) preorder(root->left) preorder(root->right)

Prechod po poradí

  1. Navštívte všetky uzly v ľavom podstrome
  2. Navštívte všetky uzly v pravom podstrome
  3. Navštívte koreňový uzol
 postorder(root->left) postorder(root->right) display(root->data)

Poďme si vizualizovať prechod v poradí. Vychádzame z koreňového uzla.

Ľavý a pravý podstrom

Najprv prechádzame ľavým podstromom. Keď je tento strom hotový, musíme nezabudnúť navštíviť koreňový uzol a pravý podstrom.

Toto všetko dajme do stohu, aby sme si to pamätali.

Stoh

Teraz prechádzame k podstromu nasmerovanému na vrchol zásobníka.

Opäť sa riadime rovnakým pravidlom inorder

 Ľavý podstrom -> koreň -> pravý podstrom

Po prechode ľavým podstromom nám ostáva

Final Stack

Pretože uzol "5" nemá žiadne podstromy, vytlačíme ho priamo. Potom vytlačíme jeho nadradený znak „12“ a potom pravé dieťa „6“.

Umiestnenie všetkého do stohu bolo užitočné, pretože teraz, keď bol prekonaný ľavý podstrom koreňového uzla, môžeme ho vytlačiť a prejsť do pravého podstromu.

Po prejdení všetkých prvkov dostaneme inorder traversal ako

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

Zásobník si nemusíme vytvárať sami, pretože rekurzia pre nás udržuje správne poradie.

Príklady jazyka Python, Java a 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);

Zaujímavé články...