# 樹的遍歷 - 中序，前序和后序 > 原文： [https://www.programiz.com/dsa/tree-traversal](https://www.programiz.com/dsa/tree-traversal) #### 在本教程中，您將學習不同的樹遍歷技術。 此外，您還將找到 C，C++ ，Java 和 Python 中不同的樹遍歷方法的工作示例。 遍歷樹意味著訪問樹中的每個節點。 例如，您可能想在樹中添加所有值或找到最大的值。 對于所有這些操作，您將需要訪問樹的每個節點。 線性數據結構（例如數組，[棧](/data-structures/stack)，[隊列](/data-structures/queue)和[鏈表](/data-structures/linked-list)）只有一種讀取數據的方法。 但是可以以不同的方式遍歷分層數據結構，例如[樹](/data-structures/trees)。  樹的遍歷 讓我們考慮一下如何讀取上圖所示的樹元素。 從上到下，從左到右 ``` 1 -> 12 -> 5 -> 6 -> 9 ``` 從底部開始，從左到右 ``` 5 -> 6 -> 12 -> 9 -> 1 ``` 盡管此過程有些容易，但它不考慮樹的層次結構，而僅考慮節點的深度。 相反，我們使用考慮樹的基本結構的遍歷方法，即 ``` struct node { int data; struct node* left; struct node* right; } ``` 由`left`和`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) ``` 讓我們可視化順序遍歷。 我們從根節點開始。  左右子樹 我們首先遍歷左子樹。 我們還需要記住，完成樹后，訪問根節點和正確的子樹。 讓我們將所有這些放入[棧](/data-structures/stack)中，以便我們記住。  棧 現在我們遍歷指向棧頂部的子樹。 同樣，我們遵循相同的有序規則 ``` Left subtree -> root -> right subtree ``` 遍歷左子樹后，我們剩下  最終棧 由于節點“5”沒有任何子樹，因此我們直接打印它。 之后，我們先打印其父級“12”，然后打印正確的子級“6”。 將所有內容放到棧上很有幫助，因為現在遍歷了根節點的左子樹，我們可以將其打印并轉到右子樹。 遍歷所有元素之后，我們得到的有序遍歷為 ``` 5 -> 12 -> 6 -> 1 -> 9 ``` 我們不必自己創建棧，因為遞歸可以為我們保持正確的順序。 * * * ## Python，Java 和 C/C++ 示例 ```py # 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("\nPreorder traversal ") preorder(root) print("\nPostorder traversal ") postorder(root) ``` ```java // 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("\nPreorder traversal "); tree.preorder(tree.root); System.out.println("\nPostorder traversal"); tree.postorder(tree.root); } } ``` ```c // Tree traversal in C #include <stdio.h> #include <stdlib.h> 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 \n"); inorderTraversal(root); printf("\nPreorder traversal \n"); preorderTraversal(root); printf("\nPostorder traversal \n"); postorderTraversal(root); } ``` ```cpp // Tree traversal in C++ #include <iostream> 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 << node->data << "->"; preorderTraversal(node->left); preorderTraversal(node->right); } // Postorder traversal void postorderTraversal(struct Node* node) { if (node == NULL) return; postorderTraversal(node->left); postorderTraversal(node->right); cout << node->data << "->"; } // Inorder traversal void inorderTraversal(struct Node* node) { if (node == NULL) return; inorderTraversal(node->left); cout << node->data << "->"; inorderTraversal(node->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 << "\nPreorder traversal "; preorderTraversal(root); cout << "\nPostorder traversal "; postorderTraversal(root); ```