原文： https://www.programiz.com/dsa/tree-traversal

在本教程中，您将学习不同的树遍历技术。 此外，您还将找到 C，C++ ，Java 和 Python 中不同的树遍历方法的工作示例。

遍历树意味着访问树中的每个节点。 例如，您可能想在树中添加所有值或找到最大的值。 对于所有这些操作，您将需要访问树的每个节点。

线性数据结构（例如数组，栈，队列和链表）只有一种读取数据的方法。 但是可以以不同的方式遍历分层数据结构，例如树。

树的遍历 - 中序，前序和后序 - 图1

树的遍历

让我们考虑一下如何读取上图所示的树元素。

从上到下，从左到右

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

从底部开始，从左到右

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

尽管此过程有些容易，但它不考虑树的层次结构，而仅考虑节点的深度。

相反，我们使用考虑树的基本结构的遍历方法，即

  1. struct node {
  2.     int data;
  3.     struct node* left;
  4.     struct node* right;
  5. }

由left和right指向的结构节点可能还有其他左右子级，因此我们应该将它们视为子树而不是子节点。

根据这种结构，每棵树都是

  • 承载数据的节点
  • 两个子树

树的遍历 - 中序，前序和后序 - 图2

左右子树

请记住，我们的目标是访问每个节点，因此我们需要访问子树中的所有节点，访问根节点以及访问右子树中的所有节点。

根据执行顺序，可以有三种遍历类型。

中序遍历

  1. 首先，访问左侧子树中的所有节点
  2. 然后是根节点
  3. 访问右侧子树中的所有节点
  1. inorder(root->left)
  2. display(root->data)
  3. inorder(root->right)

前序遍历

  1. 访问根节点
  2. 访问左侧子树中的所有节点
  3. 访问右侧子树中的所有节点
  1. display(root->data)
  2. preorder(root->left)
  3. preorder(root->right)

后序遍历

  1. 访问左侧子树中的所有节点
  2. 访问右侧子树中的所有节点
  3. 访问根节点
  1. postorder(root->left)
  2. postorder(root->right)
  3. display(root->data)

让我们可视化顺序遍历。 我们从根节点开始。

树的遍历 - 中序，前序和后序 - 图3

左右子树

我们首先遍历左子树。 我们还需要记住，完成树后，访问根节点和正确的子树。

让我们将所有这些放入栈中，以便我们记住。

树的遍历 - 中序，前序和后序 - 图4

栈

现在我们遍历指向栈顶部的子树。

同样，我们遵循相同的有序规则

  1. Left subtree -> root -> right subtree

遍历左子树后，我们剩下

树的遍历 - 中序，前序和后序 - 图5

最终栈

由于节点“5”没有任何子树，因此我们直接打印它。 之后，我们先打印其父级“12”，然后打印正确的子级“6”。

将所有内容放到栈上很有帮助，因为现在遍历了根节点的左子树，我们可以将其打印并转到右子树。

遍历所有元素之后，我们得到的有序遍历为

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

我们不必自己创建栈，因为递归可以为我们保持正确的顺序。

Python，Java 和 C/C++ 示例

  1. # Tree traversal in Python
  3. class Node:
  4.     def __init__(self, item):
  5.         self.left = None
  6.         self.right = None
  7.         self.val = item
  9. def inorder(root):
  11.     if root:
  12.         # Traverse left
  13.         inorder(root.left)
  14.         # Traverse root
  15.         print(str(root.val) + "->", end='')
  16.         # Traverse right
  17.         inorder(root.right)
  19. def postorder(root):
  21.     if root:
  22.         # Traverse left
  23.         postorder(root.left)
  24.         # Traverse right
  25.         postorder(root.right)
  26.         # Traverse root
  27.         print(str(root.val) + "->", end='')
  29. def preorder(root):
  31.     if root:
  32.         # Traverse root
  33.         print(str(root.val) + "->", end='')
  34.         # Traverse left
  35.         preorder(root.left)
  36.         # Traverse right
  37.         preorder(root.right)
  39. root = Node(1)
  40. root.left = Node(2)
  41. root.right = Node(3)
  42. root.left.left = Node(4)
  43. root.left.right = Node(5)
  45. print("Inorder traversal ")
  46. inorder(root)
  48. print("\nPreorder traversal ")
  49. preorder(root)
  51. print("\nPostorder traversal ")
  52. postorder(root)
  1. // Tree traversal in Java
  3. class Node {
  4.   int item;
  5.   Node left, right;
  7.   public Node(int key) {
  8.   item = key;
  9.   left = right = null;
  10.   }
  11. }
  13. class BinaryTree {
  14.   // Root of Binary Tree
  15.   Node root;
  17.   BinaryTree() {
  18.   root = null;
  19.   }
  21.   void postorder(Node node) {
  22.   if (node == null)
  23.     return;
  25.   // Traverse left
  26.   postorder(node.left);
  27.   // Traverse right
  28.   postorder(node.right);
  29.   // Traverse root
  30.   System.out.print(node.item + "->");
  31.   }
  33.   void inorder(Node node) {
  34.   if (node == null)
  35.     return;
  37.   // Traverse left
  38.   inorder(node.left);
  39.   // Traverse root
  40.   System.out.print(node.item + "->");
  41.   // Traverse right
  42.   inorder(node.right);
  43.   }
  45.   void preorder(Node node) {
  46.   if (node == null)
  47.     return;
  49.   // Traverse root
  50.   System.out.print(node.item + "->");
  51.   // Traverse left
  52.   preorder(node.left);
  53.   // Traverse right
  54.   preorder(node.right);
  55.   }
  57.   public static void main(String[] args) {
  58.   BinaryTree tree = new BinaryTree();
  59.   tree.root = new Node(1);
  60.   tree.root.left = new Node(12);
  61.   tree.root.right = new Node(9);
  62.   tree.root.left.left = new Node(5);
  63.   tree.root.left.right = new Node(6);
  65.   System.out.println("Inorder traversal");
  66.   tree.inorder(tree.root);
  68.   System.out.println("\nPreorder traversal ");
  69.   tree.preorder(tree.root);
  71.   System.out.println("\nPostorder traversal");
  72.   tree.postorder(tree.root);
  73.   }
  74. }
  1. // Tree traversal in C
  3. #include <stdio.h>
  4. #include <stdlib.h>
  6. struct node {
  7.   int item;
  8.   struct node* left;
  9.   struct node* right;
  10. };
  12. // Inorder traversal
  13. void inorderTraversal(struct node* root) {
  14.   if (root == NULL) return;
  15.   inorderTraversal(root->left);
  16.   printf("%d ->", root->item);
  17.   inorderTraversal(root->right);
  18. }
  20. // preorderTraversal traversal
  21. void preorderTraversal(struct node* root) {
  22.   if (root == NULL) return;
  23.   printf("%d ->", root->item);
  24.   preorderTraversal(root->left);
  25.   preorderTraversal(root->right);
  26. }
  28. // postorderTraversal traversal
  29. void postorderTraversal(struct node* root) {
  30.   if (root == NULL) return;
  31.   postorderTraversal(root->left);
  32.   postorderTraversal(root->right);
  33.   printf("%d ->", root->item);
  34. }
  36. // Create a new Node
  37. struct node* createNode(value) {
  38.   struct node* newNode = malloc(sizeof(struct node));
  39.   newNode->item = value;
  40.   newNode->left = NULL;
  41.   newNode->right = NULL;
  43.   return newNode;
  44. }
  46. // Insert on the left of the node
  47. struct node* insertLeft(struct node* root, int value) {
  48.   root->left = createNode(value);
  49.   return root->left;
  50. }
  52. // Insert on the right of the node
  53. struct node* insertRight(struct node* root, int value) {
  54.   root->right = createNode(value);
  55.   return root->right;
  56. }
  58. int main() {
  59.   struct node* root = createNode(1);
  60.   insertLeft(root, 12);
  61.   insertRight(root, 9);
  63.   insertLeft(root->left, 5);
  64.   insertRight(root->left, 6);
  66.   printf("Inorder traversal \n");
  67.   inorderTraversal(root);
  69.   printf("\nPreorder traversal \n");
  70.   preorderTraversal(root);
  72.   printf("\nPostorder traversal \n");
  73.   postorderTraversal(root);
  74. }
  1. // Tree traversal in C++
  3. #include <iostream>
  4. using namespace std;
  6. struct Node {
  7.   int data;
  8.   struct Node *left, *right;
  9.   Node(int data) {
  10.     this->data = data;
  11.     left = right = NULL;
  12.   }
  13. };
  15. // Preorder traversal
  16. void preorderTraversal(struct Node* node) {
  17.   if (node == NULL)
  18.     return;
  20.   cout << node->data << "->";
  21.   preorderTraversal(node->left);
  22.   preorderTraversal(node->right);
  23. }
  25. // Postorder traversal
  26. void postorderTraversal(struct Node* node) {
  27.   if (node == NULL)
  28.     return;
  30.   postorderTraversal(node->left);
  31.   postorderTraversal(node->right);
  32.   cout << node->data << "->";
  33. }
  35. // Inorder traversal
  36. void inorderTraversal(struct Node* node) {
  37.   if (node == NULL)
  38.     return;
  40.   inorderTraversal(node->left);
  41.   cout << node->data << "->";
  42.   inorderTraversal(node->right);
  43. }
  45. int main() {
  46.   struct Node* root = new Node(1);
  47.   root->left = new Node(12);
  48.   root->right = new Node(9);
  49.   root->left->left = new Node(5);
  50.   root->left->right = new Node(6);
  52.   cout << "Inorder traversal ";
  53.   inorderTraversal(root);
  55.   cout << "\nPreorder traversal ";
  56.   preorderTraversal(root);
  58.   cout << "\nPostorder traversal ";
  59.   postorderTraversal(root);