二叉树前序、中序、后序遍历

二叉树

二叉树是一种非常重要的数据结构，非常多其他数据结构都是基于二叉树的基础演变而来的。对于二叉树，有深度遍历和广度遍历，深度遍历有前序、中序以及后序三种遍历方法，广度遍历即我们寻常所说的层次遍历。由于树的定义本身就是递归定义，因此採用递归的方法去实现树的三种遍历不仅简单理解并且代码非常简洁，而对于广度遍历来说，须要其他数据结构的支撑。比方队列。所以。对于一段代码来说，可读性有时候要比代码本身的效率要重要的多。

遍历方式

前序遍历：根结点 ---> 左子树 ---> 右子树
中序遍历：左子树 ---> 根结点 ---> 右子树
后序遍历：左子树 ---> 右子树 ---> 根结点

前序遍历：1 2 4 5 7 8 3 6
中序遍历：4 2 7 5 8 1 3 6
后序遍历：4 7 8 5 2 6 3 1

代码实现

Java

Java 实现

public class BinaryTree {

    public int data;
    public BinaryTree left;
    public BinaryTree right;

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

    public static void PreorderTraversal(BinaryTree node) { // 先序遍历
        if (node == null) {
            return;
        }
        System.out.print(node.data);
        PreorderTraversal(node.left);
        PreorderTraversal(node.right);
    }

    public static void InorderTraversal(BinaryTree node) { // 中序遍历
        if (node == null) {
            return;
        }
        InorderTraversal(node.left);
        System.out.print(node.data);
        InorderTraversal(node.right);
    }

    public static void PostorderTraversal(BinaryTree node) { // 后序遍历
        if (node == null) {
            return;
        }
        PostorderTraversal(node.left);
        PostorderTraversal(node.right);
        System.out.print(node.data);
    }

    public static void main(String[] args) {
        BinaryTree root = new BinaryTree(1);
        BinaryTree node2 = new BinaryTree(2);
        BinaryTree node3 = new BinaryTree(3);
        BinaryTree node4 = new BinaryTree(4);
        BinaryTree node5 = new BinaryTree(5);
        BinaryTree node6 = new BinaryTree(6);
        BinaryTree node7 = new BinaryTree(7);
        BinaryTree node8 = new BinaryTree(8);
        root.left = node2;
        root.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.right = node6;
        node5.left = node7;
        node5.right = node8;

        PreorderTraversal(root); // 12457836
        System.out.println();
        InorderTraversal(root); // 42758136
        System.out.println();
        PostorderTraversal(root); // 47852631
    }
}

Python

Python 实现

class BinaryTree:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right


def PreorderTraversal(node):  # 先序遍历
    if node is None:
        return
    print(node.data, end='')
    PreorderTraversal(node.left)
    PreorderTraversal(node.right)


def InorderTraversal(node):  # 中序遍历
    if node is None:
        return
    InorderTraversal(node.left)
    print(node.data, end='')
    InorderTraversal(node.right)


def PostorderTraversal(node):  # 后序遍历
    if node is None:
        return
    PostorderTraversal(node.left)
    PostorderTraversal(node.right)
    print(node.data, end='')


if __name__ == '__main__':
    root = BinaryTree(1)
    node2 = BinaryTree(2)
    node3 = BinaryTree(3)
    node4 = BinaryTree(4)
    node5 = BinaryTree(5)
    node6 = BinaryTree(6)
    node7 = BinaryTree(7)
    node8 = BinaryTree(8)
    root.left = node2
    root.right = node3
    node2.left = node4
    node2.right = node5
    node3.right = node6
    node5.left = node7
    node5.right = node8

    PreorderTraversal(root)  # 12457836
    print()
    InorderTraversal(root)  # 42758136
    print()
    PostorderTraversal(root)  # 47852631

Go

Go 实现

package main

import "fmt"

type BinaryTree struct {
    data  int
    left  *BinaryTree
    right *BinaryTree
}

func PreorderTraversal(node *BinaryTree) { // 先序遍历
    if node == nil {
        return
    }
    fmt.Print(node.data)
    PreorderTraversal(node.left)
    PreorderTraversal(node.right)
}

func InorderTraversal(node *BinaryTree) { // 中序遍历
    if node == nil {
        return
    }
    InorderTraversal(node.left)
    fmt.Print(node.data)
    InorderTraversal(node.right)
}

func PostorderTraversal(node *BinaryTree) { // 后序遍历
    if node == nil {
        return
    }
    PostorderTraversal(node.left)
    PostorderTraversal(node.right)
    fmt.Print(node.data)
}

func main() {
    root := BinaryTree{data: 1}
    node2 := BinaryTree{data: 2}
    node3 := BinaryTree{data: 3}
    node4 := BinaryTree{data: 4}
    node5 := BinaryTree{data: 5}
    node6 := BinaryTree{data: 6}
    node7 := BinaryTree{data: 7}
    node8 := BinaryTree{data: 8}
    root.left = &node2
    root.right = &node3
    node2.left = &node4
    node2.right = &node5
    node3.right = &node6
    node5.left = &node7
    node5.right = &node8

    PreorderTraversal(&root) // 12457836
    fmt.Println()
    InorderTraversal(&root) // 42758136
    fmt.Println()
    PostorderTraversal(&root) // 47852631
}