Обхождане на дърво

В този урок ще научите за различни техники за обхождане на дървета. Също така ще намерите работни примери за различни методи за обхождане на дървета в C, C ++, Java и Python.

Преминаването през дърво означава посещение на всеки възел в дървото. Може например да искате да добавите всички стойности в дървото или да намерите най-голямата. За всички тези операции ще трябва да посетите всеки възел на дървото.

Линейните структури от данни като масиви, стекове, опашки и свързан списък имат само един начин за четене на данните. Но йерархична структура от данни като дърво може да бъде обходена по различни начини.

Обхождане на дърво

Нека помислим как можем да прочетем елементите на дървото в изображението, показано по-горе.

Започвайки отгоре, отляво надясно

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

Започвайки отдолу, отляво надясно

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

Въпреки че този процес е донякъде лесен, той не зачита йерархията на дървото, а само дълбочината на възлите.

Вместо това използваме методи за обхождане, които отчитат основната структура на дървото, т.е.

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

Структурният възел, посочен отляво и отдясно, може да има други леви и десни деца, така че трябва да ги мислим като поддървета вместо подвъзли.

Според тази структура всяко дърво е комбинация от

  • Възел, носещ данни
  • Две поддървета
Ляво и дясно поддърво

Не забравяйте, че нашата цел е да посетим всеки възел, така че трябва да посетим всички възли в поддървото, да посетим коренния възел и да посетим всички възли и в дясното поддърво.

В зависимост от реда, в който правим това, може да има три вида обхождане.

Вътрешно обръщане

  1. Първо посетете всички възли в лявото поддърво
  2. След това коренният възел
  3. Посетете всички възли в дясното поддърво
 inorder(root->left) display(root->data) inorder(root->right)

Обръщане на предварителна поръчка

  1. Посетете коренния възел
  2. Посетете всички възли в лявото поддърво
  3. Посетете всички възли в дясното поддърво
 display(root->data) preorder(root->left) preorder(root->right)

Обръщане на пощенска поръчка

  1. Посетете всички възли в лявото поддърво
  2. Посетете всички възли в дясното поддърво
  3. Посетете основния възел
 postorder(root->left) postorder(root->right) display(root->data)

Нека да визуализираме обхождане по ред. Започваме от кореновия възел.

Ляво и дясно поддърво

Първо прекосяваме лявото поддърво. Също така трябва да помним да посетим коренния възел и правилното поддърво, когато това дърво приключи.

Нека сложим всичко това в стек, така че да запомним.

Стек

Сега преминаваме към поддървото, посочено в горната част на стека.

Отново следваме същото правило на inorder

 Ляво поддърво -> корен -> дясно поддърво

След като обходим лявото поддърво, оставаме с

Финален стак

Тъй като възелът "5" няма поддървета, ние го отпечатваме директно. След това отпечатваме родителя му "12" и след това правилното дете "6".

Поставянето на всичко в стека беше полезно, защото сега, когато лявото поддърво на коренния възел беше обходено, можем да го отпечатаме и да отидем в дясното поддърво.

След като преминем през всички елементи, получаваме вътрешното обръщане като

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

Не е нужно да създаваме стека сами, защото рекурсията поддържа правилния ред за нас.

Примери за Python, Java и 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);

Интересни статии...