U ovom vodiču naučit ćete o različitim tehnikama zaokretanja stabala. Također ćete naći radne primjere različitih metoda prelaska stabla u C, C ++, Java i Python.
Preći drvo znači posjetiti svaki čvor na drvetu. Na primjer, možda želite dodati sve vrijednosti u stablo ili pronaći najveću. Za sve ove operacije morat ćete posjetiti svaki čvor stabla.
Linearne strukture podataka kao što su nizovi, hrpe, redovi i povezani popis imaju samo jedan način čitanja podataka. Ali hijerarhijska struktura podataka poput stabla može se prelaziti na različite načine.
Prelazak stabla
Razmislimo o tome kako možemo čitati elemente stabla na gornjoj slici.
Počevši od vrha, slijeva udesno
1 -> 12 -> 5 -> 6 -> 9
Počevši od dna, slijeva udesno
5 -> 6 -> 12 -> 9 -> 1
Iako je ovaj postupak pomalo lagan, ne poštuje hijerarhiju stabla, već samo dubinu čvorova.
Umjesto toga koristimo metode prelaska koje uzimaju u obzir osnovnu strukturu stabla, tj
struct node ( int data; struct node* left; struct node* right; )
Strukturni čvor na koji ukazuju lijevo i desno mogu imati drugu lijevu i desnu djecu, pa bismo o njima trebali razmišljati kao o podstablima, a ne o pod čvorovima.
Prema ovoj strukturi, svako je stablo kombinacija
- Čvor koji nosi podatke
- Dva podstabla
Lijevo i desno podstablo
Ne zaboravite da je naš cilj posjetiti svaki čvor, stoga moramo posjetiti sve čvorove u podstablu, posjetiti korijenski čvor i posjetiti sve čvorove u pravom podstablu.
Ovisno o redoslijedu kojim to radimo, mogu postojati tri vrste prijelaza.
Unutrašnja obilaznica
- Prvo posjetite sve čvorove u lijevom podstablu
- Zatim korijenski čvor
- Posjetite sve čvorove u desnom podstablu
inorder(root->left) display(root->data) inorder(root->right)
Prijelaz predbilježbe
- Posjetite korijenski čvor
- Posjetite sve čvorove u lijevom podstablu
- Posjetite sve čvorove u desnom podstablu
display(root->data) preorder(root->left) preorder(root->right)
Prijelaz postpokaza
- Posjetite sve čvorove u lijevom podstablu
- Posjetite sve čvorove u desnom podstablu
- Posjetite korijenski čvor
postorder(root->left) postorder(root->right) display(root->data)
Vizualizirajmo redoslijed prijelaza. Polazimo od korijenskog čvora.
Lijevo i desno podstablo
Prvo prelazimo lijevo podstablo. Također moramo imati na umu da posjetimo korijenski čvor i pravo podstablo kada je ovo stablo gotovo.
Stavimo sve ovo u hrpu da se sjetimo.
Stog
Sada prelazimo na podstablo usmjereno na VRH hrpe.
Opet, slijedimo isto pravilo inorder
Lijevo podstablo -> korijen -> desno poddrvo
Nakon prelaska lijevog podstabla, preostaje nam
Konačni stog
Budući da čvor "5" nema nijedno podstablo, ispisujemo ga izravno. Nakon toga ispisujemo njegov roditelj "12", a zatim pravo dijete "6".
Staviti sve u hrpu bilo je korisno jer sada, kada je pređeno lijevo podstablo korijenskog čvora, možemo ga ispisati i otići na desno podstablo.
Nakon prolaska kroz sve elemente, dobivamo zaobilaženje kao
5 -> 12 -> 6 -> 1 -> 9
Ne moramo sami stvarati stog jer rekurzija održava ispravan redoslijed za nas.
Primjeri Pythona, Java i 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);
