树遍历 - 中序、前序和后序
提示
- 树遍历的概念：树遍历是指访问树中的每个节点，通常用于计算总和或查找最大值等操作。
- 遍历类型：三种主要的树遍历方式包括中序遍历（先左子树，再根节点，最后右子树），前序遍历（先根节点，再左子树，最后右子树），和后序遍历（先左子树，再右子树，最后根节点）。
- 遍历方法的应用：这些遍历方法不仅考虑到节点的深度，还考虑树的层次结构，适用于不同的场景和需求，如求和、搜索或打印树结构。
遍历一棵树意味着访问树中的每个节点。例如，你可能想要计算树中所有值的总和或者找到最大的值。对于所有这些操作，你都需要访问树的每个节点。
像数组、栈、队列 和 链表 这样的线性数据结构只有一种读取数据的方式。但像 树 这样的层次化数据结构可以用不同的方式遍历。
让我们思考一下如何阅读上图中树的元素。
从上到下，从左到右
1 -> 12 -> 5 -> 6 -> 9
从下到上，从左到右
5 -> 6 -> 12 -> 9 -> 1
尽管这个过程相对简单，但它没有尊重树的层次结构，只考虑了节点的深度。
相反，我们使用考虑到树的基本结构的遍历方法，即
struct node {
int data;
struct node* left;
struct node* right;
}
被 left 和 right 指向的 struct node 可能有其他的左右子节点，所以我们应该将它们视为子树而不是子节点。
根据这个结构，每棵树是由以下部分组合而成的：
- 携带数据的节点
- 两个子树
记住我们的目标是访问每个节点，所以我们需要访问左子树中的所有节点，访问根节点，以及访问右子树中的所有节点。
根据我们执行这些操作的顺序，可以有三种类型的遍历。
中序遍历
- 首先，访问左子树中的所有节点
- 然后访问根节点
- 访问右子树中的所有节点
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)
让我们来可视化中序遍历。我们从根节点开始。
我们首先遍历左子树。我们还需要记住在这棵树遍历完后访问根节点和右子树。
让我们把这些都放入一个栈中，以便记住。
现在我们遍历栈顶指向的子树。
Again, we follow the same rule of inorder
Left subtree -> root -> right subtree
After traversing the left subtree, we are left with
Since the node "5" doesn't have any subtrees, we print it directly. After that we print its parent "12" and then the right child "6".
Putting everything on a stack was helpful because now that the left-subtree of the root node has been traversed, we can print it and go to the right subtree.
After going through all the elements, we get the inorder traversal as
5 -> 12 -> 6 -> 1 -> 9
We don't have to create the stack ourselves because recursion maintains the correct order for us.
Python, Java and C/C++ Examples
# 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 中的树遍历
class Node {
int item;
Node left, right;
public Node(int key) {
item = key;
left = right = null;
}
}
class BinaryTree {
// 二叉树的根
Node root;
BinaryTree() {
root = null;
}
void postorder(Node node) {
if (node == null)
return;
// 遍历左子树
postorder(node.left);
// 遍 历右子树
postorder(node.right);
// 遍历根节点
System.out.print(node.item + "->");
}
void inorder(Node node) {
if (node == null)
return;
// 遍历左子树
inorder(node.left);
// 遍历根节点
System.out.print(node.item + "->");
// 遍历右子树
inorder(node.right);
}
void preorder(Node node) {
if (node == null)
return;
// 遍历根节点
System.out.print(node.item + "->");
// 遍历左子树
preorder(node.left);
// 遍历右子树
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("中序遍历");
tree.inorder(tree.root);
System.out.println("\n前序遍历 ");
tree.preorder(tree.root);
System.out.println("\n后序遍历");
tree.postorder(tree.root);
}
}
// C 语言中的树遍历
#include <stdio.h>
#include <stdlib.h>
struct node {
int item;
struct node* left;
struct node* right;
};
// 中序遍历
void inorderTraversal(struct node* root) {
if (root == NULL) return;
inorderTraversal(root->left);
printf("%d ->", root->item);
inorderTraversal(root->right);
}
// 前序遍历
void preorderTraversal(struct node* root) {
if (root == NULL) return;
printf("%d ->", root->item);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
// 后序遍历
void postorderTraversal(struct node* root) {
if (root == NULL) return;
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ->", root->item);
}
// 创建新节点
struct node* createNode(value) {
struct node* newNode = malloc(sizeof(struct node));
newNode->item = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// 在节点的左侧插入
struct node* insertLeft(struct node* root, int value) {
root->left = createNode(value);
return root->left;
}
// 在节点的右侧插入
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("中序遍历 \n");
inorderTraversal(root);
printf("\n前序遍历 \n");
preorderTraversal(root);
printf("\n后序遍历 \n");
postorderTraversal(root);
}
// C++ 中的树遍历
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
Node(int data) {
this->data = data;
left = right = NULL;
}
};
// 前序遍历
void preorderTraversal(struct Node* node) {
if (node == NULL)
return;
cout << node->data << "->";
preorderTraversal(node->left);
preorderTraversal(node->right);
}
// 后序遍历
void postorderTraversal(struct Node* node) {
if (node == NULL)
return;
postorderTraversal(node->left);
postorderTraversal(node->right);
cout << node->data << "->";
}
// 中序遍历
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 << "中序遍历 ";
inorderTraversal(root);
cout << "\n前序遍历 ";
preorderTraversal(root);
cout << "\n后序遍历 ";
postorderTraversal(root);
}