V tomto kurzu se dozvíte o různých technikách procházení stromů. Také najdete pracovní příklady různých metod pro procházení stromů v C, C ++, Java a Python.
Procházet stromem znamená navštívit každý uzel ve stromu. Můžete například chtít přidat všechny hodnoty do stromu nebo najít největší. U všech těchto operací budete muset navštívit každý uzel stromu.
Lineární datové struktury, jako jsou pole, komíny, fronty a propojený seznam, mají pouze jeden způsob, jak číst data. Ale hierarchickou datovou strukturu, jako je strom, lze procházet různými způsoby.
Traverz stromu
Pojďme se zamyslet nad tím, jak můžeme číst prvky stromu na obrázku výše.
Počínaje shora, zleva doprava
1 -> 12 -> 5 -> 6 -> 9
Počínaje zdola, zleva doprava
5 -> 6 -> 12 -> 9 -> 1
Ačkoli je tento proces poněkud snadný, nerespektuje hierarchii stromu, pouze hloubku uzlů.
Místo toho používáme traversální metody, které berou v úvahu základní strukturu stromu, tj
struct node ( int data; struct node* left; struct node* right; )
Strukturální uzel, na který ukazuje levá a pravá strana, může mít další levé a pravé děti, takže bychom o nich měli uvažovat jako o dílčích stromech místo o dílčích uzlech.
Podle této struktury je každý strom kombinací
- Uzel nesoucí data
- Dva podstromy
Levý a pravý podstrom
Nezapomeňte, že naším cílem je navštívit každý uzel, takže musíme navštívit všechny uzly v podstromu, navštívit kořenový uzel a také navštívit všechny uzly v pravém podstromu.
V závislosti na pořadí, ve kterém to děláme, mohou existovat tři typy průchodu.
Inorder traversal
- Nejprve navštivte všechny uzly v levém podstromu
- Pak kořenový uzel
- Navštivte všechny uzly v pravém podstromu
inorder(root->left) display(root->data) inorder(root->right)
Předobjednejte si traversal
- Navštivte kořenový uzel
- Navštivte všechny uzly v levém podstromu
- Navštivte všechny uzly v pravém podstromu
display(root->data) preorder(root->left) preorder(root->right)
Postorder traversal
- Navštivte všechny uzly v levém podstromu
- Navštivte všechny uzly v pravém podstromu
- Navštivte kořenový uzel
postorder(root->left) postorder(root->right) display(root->data)
Pojďme si představit traversal v pořadí. Začneme od kořenového uzlu.
Levý a pravý podstrom
Nejprve projdeme levým podstromem. Po dokončení tohoto stromu také musíme pamatovat na návštěvu kořenového uzlu a pravého podstromu.
Dejme to všechno do hromádky, abychom si to pamatovali.
Zásobník
Nyní přejdeme k podstromu namířenému na vrchol zásobníku.
Opět se řídíme stejným pravidlem neuspořádanosti
Levý podstrom -> kořen -> pravý podstrom
Po projetí levým podstromem nám zbývá
Final Stack
Protože uzel "5" nemá žádné podstromy, vytiskneme jej přímo. Poté vytiskneme jeho nadřazený „12“ a poté pravé podřízené „6“.
Umístit vše do zásobníku bylo užitečné, protože teď, když byl překročen levý podstrom kořenového uzlu, můžeme to vytisknout a přejít do pravého podstromu.
Poté, co projdeme všemi prvky, dostaneme inorder traversal jako
5 -> 12 -> 6 -> 1 -> 9
Zásobník nemusíme vytvářet sami, protože rekurze pro nás udržuje správné pořadí.
Python, Java a C / C ++ příklady
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);
