二叉树遍历的规则

1. 根据根节点（父节点）的位置在最前面、在左子节点、右子节点中间、最后面，分为前序、中序、后序。

2. 除了根（父节点）特殊以外，都是先左节点、后右节点。

前序遍历

1. 一个子树一个子树的看

2. 前序：根（父）--> 左子节点--->子树  .....    -->右子节点

第1个子树：ABC组成，前序是ABC

因为B又是一个树（节点数大于1,右BDE组成），因此子树前序是BDE,替换后是ABDEC

因为C又是一个数，其前序：CF，替换后ABDECF

因此此树前序遍历为：ABDECF

中序遍历

与前序遍历的逻辑是一样的。

1. 第1个子树(包含根节点的)的中序遍历是：BAC

2. 因为B又是一个子树（由BDE节点组成）其中序遍历是:DBE,替换第1步骤的结果BAC的中即为DBEAC

3.因为C又是一个子树（由CF节点组成），其中序遍历是CF（没有左节点就直接根节点），替换步骤1中的C，最终中序遍历:DBEACF

后序遍历

与前序、中序的遍历逻辑一样

第1步: 根节点组成的树:ABC,其后序遍历:BCA

第2步:B又是一个树（BDE组成），其后序遍历:DEB,替换第1步骤的结果中的B:DEBCA

第3步:因C也是一个树（CF组成），其后序遍历: FC，替换步骤1的C，结果为DEBFCA

Java前中后序遍历示例

1. 树节点

定义一个类表示树节点，记录当前节点存储的数据以及其左右节点。

public class TreeNode {
    // 数据
    int data;
    // 左子节点
    TreeNode left;
    // 右子节点
    TreeNode right;
    public TreeNode(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

2. 树对象

定义一个类表示树本身，要记录根节点以及新增节点。

import java.util.LinkedList;
import java.util.Queue;

/**
 * 树类即一个BinaryTree对象代表一个树
 */
public class BinaryTree {

    TreeNode root;

    public BinaryTree(int data) {
        this.root = new TreeNode(data);
    }

    public void insert(int data) {
        TreeNode newNode = new TreeNode(data);
        if (root == null) {
            root = newNode;
            return;
        }
        // 每次都需要遍历，塑造树
        // 0. 创建一个容器，记录需要处理左右子节点的树节点
        Queue<TreeNode> queue = new LinkedList<>();
        // 1. 根入链
        queue.offer(root);
        // 2. 遍历 : 塑造树
        while (!queue.isEmpty()) {
            // 2.1 遍历所有节点，判断左右子节点是否为空，顺序先左后右
            TreeNode current = queue.poll();
            // 2.2 左子节点为空，当前插入节点作为其左节点
            if (current.left == null) {
                current.left = newNode;
                return;
            } else {
                // 2.2 左子节点不为空，入链塑造树（在以后的循环为其塑造左右节点）
                queue.offer(current.left);
            }
            // 2.3 遍历所有节点，判断右子节点是否为空
            //  为空，当前插入节点作为其右子节点
            if (current.right == null) {
                current.right = newNode;
                return;
            } else {
                // 不为空，入链，塑造树（在以后的循环为其塑造左右节点）
                queue.offer(current.right);
            }
        }
    }
}

测试类

public class Main {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree(1);
        binaryTree.insert(2);
        binaryTree.insert(3);
        binaryTree.insert(4);
        binaryTree.insert(5);
        System.out.println("Binary Tree traversal:");
        traversalBinaryTree(binaryTree.root);
        System.out.println();
        inorderTraversal(binaryTree.root);
        System.out.println();
        postorderTraversal(binaryTree.root);
    }

    // 前序遍历树
    public static void traversalBinaryTree(TreeNode root) {
        if (root != null) {
            System.out.print(root.data + " ");
            traversalBinaryTree(root.left);
            traversalBinaryTree(root.right);
        }
    }

    // 中序
    public static void inorderTraversal(TreeNode root) {
        if (root != null) {
            inorderTraversal(root.left);
            System.out.print(root.data + " ");
            inorderTraversal(root.right);
        }
    }

    // 后序
    public static void postorderTraversal(TreeNode root) {
        if (root != null) {
            postorderTraversal(root.left);
            postorderTraversal(root.right);
            System.out.print(root.data + " ");
        }
    }


}

输出结果:

Binary Tree traversal:
1 2 4 5 3 
4 2 5 1 3 
4 5 2 3 1 

Python前中后序遍历示例

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


class BinaryTree:

    def __init__(self, value):
        self.root = TreeNode(value)

    def insert(self, data):
        # 创建节点
        insertNode = TreeNode(data)
        if self.root is None:
            self.root = insertNode
        # 存储节点，用于遍历
        arr = [self.root]
        while len(arr) > 0:
            tmp = arr.pop(0)  # pop不指定索引，默认删除最后1个元素
            if tmp.left is None:
                tmp.left = insertNode
                return
            else:
                arr.append(tmp.left)
            if tmp.right is None:
                tmp.right = insertNode
                return
            else:
                arr.append(tmp.right)


'''
前序遍历
'''


def preorder_traversal(node):
    if node:
        print(node.value, end=" ")
        preorder_traversal(node.left)
        preorder_traversal(node.right)


'''
中序遍历
'''


def inorder_traversal(node):
    if node:
        inorder_traversal(node.left)
        print(node.value, end=" ")
        inorder_traversal(node.right)


'''
后序遍历
'''


def postorder_traversal(node):
    if node:
        postorder_traversal(node.left)
        postorder_traversal(node.right)
        print(node.value, end=" ")


tree = BinaryTree(1)
tree.insert(2)
tree.insert(3)
tree.insert(4)
tree.insert(5)
preorder_traversal(tree.root)
print()
inorder_traversal(tree.root)
print()
postorder_traversal(tree.root)

输出：

1 2 4 5 3 
4 2 5 1 3 
4 5 2 3 1