二叉树是一种非常神奇的树,由于其在查找排序等某些方面的优越性,应用范围非常广。

大学的时候老师讲过二叉树,当时被各种遍历搞的 N 脸蒙蔽,在我幼小的心灵中留下过非常严重的阴影。今天回过头来重新学习二叉树。真的是验证了那句老话:

不是不报,时候未到,试看苍天绕过谁?

什么是二叉树

二叉树简单的说就是字面意思,一种最多有两个分叉的树状结构。

组成部分

二叉树主要有三部分组成: 树根、树枝、树叶。

对应起来如下图:

二叉树

红色的为树根(根节点) 绿色的为树叶(对应子节点) 树根与树叶之间的连线为树枝。

二叉树的知识点很多:

等等等等,今天这里只讨论遍历这一个知识点。

二叉树的遍历

二叉树的遍历中分为:

等以上几种。这里我们分开来探讨。

首先我们需要有一颗二叉树用于下边的所有例子。

二叉树例子

接下来我们使用代码创造图中的二叉树。

节点类

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val) {
        this.val = val;
    }
}

构造二叉树

public TreeNode bulidTree() {
    TreeNode root = new TreeNode(1);
    TreeNode n2 = new TreeNode(2);
    TreeNode n3 = new TreeNode(3);
    TreeNode n4 = new TreeNode(4);
    TreeNode n5 = new TreeNode(5);
    root.left = n2;
    root.right = n3;
    n2.left = n4;
    n2.right = n5;
    return root;
}

到此就按照图中构造了一颗二叉树。

前序遍历

所谓前序遍历就是按照 父节点 -> 左节点 -> 右节点 的顺序进行遍历。

那么按照这个顺序遍历下来,结果应该是:

1 2 4 5 3

写程序有一个既定的套路,一般存在规律并且可扩展的问题,使用递归是最简单的方法。这里我们就使用递归来解决问题。

public void preOrder(TreeNode node) {
    if (node != null) {
        System.out.println(node.val);
        preOrder(node.left);
        preOrder(node.right);
    }
}

执行方法,可以打印出结果为:

1
2
4
5
3

跟我们预期的结果一致。

中序遍历

中序遍历的顺序为 左节点 > 跟节点 > 右节点

同样,先把中序遍历的预期结果写出来。

4 2 5 1 3

public void inOrder(TreeNode node) {
    if (node != null) {
        inOrder(node.left);
        System.out.println(node.val);
        inOrder(node.right);
    }
}

运行结果:

4
2
5
1
3

后序遍历

后续序遍历的顺序为 左节点 > 右节点 > 根节点

同样,先把中序遍历的预期结果写出来。

4 5 2 3 1

public void postOrder(TreeNode node) {
    if (node != null) {
        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.val);
    }
}

运行结果:

4
5
2
3
1

层次遍历

层次遍历是按照层级来遍历,先遍历第一层然后第二层然后第三层,以此类推。

那么这里的例子使用层次遍历的结果理论上应该为:

1 2 3 4 5

对于这个需求,使用递归就不太好使了,原因是递归适合深度优先的遍历方法。抓住一条线索一直往下挖,知道到底为止。

这里我们使用队列来解决层次遍历的问题。

public void level(TreeNode node) throws InterruptedException {
    if (node == null) {
        return;
    }
    BlockingQueue<TreeNode> nodes = new ArrayBlockingQueue<TreeNode>(10);
    nodes.put(node);
    while (!nodes.isEmpty()) {
        TreeNode tmp = nodes.poll();
        System.out.println(tmp.val);
        if (tmp.left != null) {
            nodes.put(tmp.left);
        }
        if (tmp.right != null) {
            nodes.put(tmp.right);
        }
    }
}

运行结果如下:

1
2
3
4
5