Обхід дерева

У цьому підручнику ви дізнаєтесь про різні техніки обходу дерев. Крім того, ви знайдете робочі приклади різних методів обходу дерев на C, C ++, Java та Python.

Подорож по дереву означає відвідування кожного вузла на дереві. Наприклад, ви можете додати всі значення у дереві або знайти найбільше. Для всіх цих операцій вам потрібно буде відвідати кожен вузол дерева.

Лінійні структури даних, такі як масиви, стеки, черги та зв’язаний список, мають лише один спосіб зчитування даних. Але ієрархічну структуру даних, як дерево, можна обходити різними способами.

Обхід дерева

Давайте подумаємо над тим, як ми можемо прочитати елементи дерева на зображенні, показаному вище.

Починаючи зверху, зліва направо

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

Починаючи знизу, зліва направо

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

Хоча цей процес дещо простий, він не поважає ієрархію дерева, лише глибину вузлів.

Натомість ми використовуємо методи обходу, які враховують основну структуру дерева, тобто

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

Вузол struct, на який вказують ліворуч та праворуч, може мати інших лівих та правих дочірніх організацій, тому ми повинні вважати їх піддеревами, а не підвузлами.

Відповідно до цієї структури, кожне дерево є поєднанням

  • Вузол, що несе дані
  • Два піддерева
Ліве та праве піддерево

Пам'ятайте, що наша мета - відвідати кожен вузол, тому нам потрібно відвідати всі вузли в піддереві, відвідати кореневий вузол і також відвідати всі вузли у правому піддереві.

Залежно від порядку, в якому ми це робимо, може бути три типи обходу.

Внутрішній обхід

  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);

Цікаві статті...