В этом руководстве вы узнаете о различных методах обхода дерева. Также вы найдете рабочие примеры различных методов обхода дерева в C, C ++, Java и Python.
Обход дерева означает посещение каждого узла в дереве. Например, вы можете захотеть сложить все значения в дереве или найти самое большое из них. Для всех этих операций вам нужно будет посетить каждый узел дерева.
У линейных структур данных, таких как массивы, стеки, очереди и связанный список, есть только один способ чтения данных. Но иерархическую структуру данных, такую как дерево, можно перемещать по-разному.
Обход дерева
Давайте подумаем, как мы можем читать элементы дерева на изображении, показанном выше.
Начиная сверху, слева направо
1 -> 12 -> 5 -> 6 -> 9
Начиная снизу, слева направо
5 -> 6 -> 12 -> 9 -> 1
Хотя этот процесс несколько прост, он не учитывает иерархию дерева, а только глубину узлов.
Вместо этого мы используем методы обхода, которые учитывают базовую структуру дерева, т.е.
struct node ( int data; struct node* left; struct node* right; )
Узел структуры, на который указывают левый и правый, может иметь других левых и правых потомков, поэтому мы должны думать о них как о поддеревьях, а не как о подузлах.
Согласно этой структуре каждое дерево представляет собой комбинацию
- Узел, несущий данные
- Два поддерева
Левое и правое поддерево
Помните, что наша цель - посетить каждый узел, поэтому нам нужно посетить все узлы в поддереве, посетить корневой узел и также посетить все узлы в правом поддереве.
В зависимости от порядка, в котором мы это делаем, может быть три типа обхода.
Обход
- Сначала посетите все узлы в левом поддереве
- Тогда корневой узел
- Посетите все узлы в правом поддереве
inorder(root->left) display(root->data) inorder(root->right)
Обход предзаказа
- Посетить корневой узел
- Посетите все узлы в левом поддереве
- Посетите все узлы в правом поддереве
display(root->data) preorder(root->left) preorder(root->right)
Поступорядоченный обход
- Посетите все узлы в левом поддереве
- Посетите все узлы в правом поддереве
- Посетите корневой узел
postorder(root->left) postorder(root->right) display(root->data)
Давайте визуализируем обход по порядку. Начнем с корневого узла.
Левое и правое поддерево
Сначала мы обходим левое поддерево. Мы также должны не забыть посетить корневой узел и правое поддерево, когда это дерево будет построено.
Сложим все это в стопку, чтобы запомнить.
Стек
Теперь мы переходим к поддереву, указанному на вершине стека.
Опять же, мы следуем тому же правилу порядка
Левое поддерево -> корень -> правое поддерево
После обхода левого поддерева у нас остается
Финальный стек
Поскольку узел «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);
