图解二叉树

>>强大,10k+点赞的 SpringBoot 后台管理系统竟然出了详细教程!

图解二叉树

二叉树定义:二叉树是每个结点最多有两个子树的树结构。

二叉树的特点:

  1. 每个节点最多有两个子节点,即二叉树不存在大于2的节点;

  2. 二叉树的子树有左右之分,其子树的次序不能颠倒。

二叉树的结构:

图解二叉树
二叉树

二叉树的性质:

  1. 在非空二叉树中,第 i 层的节点总数不超过 2 i-1,i >= 1;

  2. 深度为 h 的二叉树最多有 2 h - 1 个节点(h>=1),最少有 h 个节点;

  3. 对于任意一棵二叉树,如果其叶节点总数为 n1,而度数为2的节点总数为 n2,则 n1 = n2+1;

  4. 具有 n 个节点的完全二叉树的深度为 (Log2n) +1;

  5. 对于任意一个根节点,如果根节点的下标为n,那么它的左节点下标为 2n+1,右节点下标为 2n+2,根据这点可以很方便的用数组来保存二叉树的节点。

实现二叉树:

 1import java.util.ArrayList;
2import java.util.List;
3
4class BinaryTree<E{
5    // 根节点
6    private Node<E> _root;
7    // 用列表暂时保存下节点
8    private List<Node<E>> nodes = new ArrayList<>();
9
10    public void createTree(E[] array) {
11        if (array.length == 0) {
12            return;
13        }
14        for (E e : array) {
15            nodes.add(new Node<>(nullnullnull, e));
16        }
17        // 获取根节点
18        if (nodes.get(0) != null) {
19            _root = nodes.get(0);
20        }
21        // 根据二叉树的特性5来确定每个节点的左右子节点
22        for (int i = 0; i < nodes.size(); i++) {
23            if ((i * 2 + 1) < nodes.size() && nodes.get(i * 2 + 1) != null) {
24                nodes.get(i).left = nodes.get(i * 2 + 1);
25            }
26            if ((i * 2 + 2) < nodes.size() && nodes.get(i * 2 + 2) != null) {
27                nodes.get(i).right = nodes.get(i * 2 + 2);
28            }
29        }
30    }
31
32    // 节点类
33    static class Node<E{
34        // 父节点暂时没有用到
35        Node<E> parent;
36        // 左节点
37        Node<E> left;
38        // 右节点
39        Node<E> right;
40        // 节点中存储的数据
41        E data;
42
43        Node(Node<E> parent, Node<E> left, Node<E> right, E data) {
44            this.data = data;
45            this.parent = parent;
46            this.left = left;
47            this.right = right;
48        }
49
50        @Override
51        public String toString() {
52            return data.toString();
53        }
54    }
55
56    public static void main(String[] args) {
57        Integer[] array = {012345678};
58        BinaryTree<Integer> binaryTree = new BinaryTree<>();
59        binaryTree.createTree(array);
60    }
61}

实现二叉树的代码很简单,主要就是通过上述的性质5来确定每一个节点的左右子节点,一层一层的绑定关系,最终就可以将所有的节点联系完整。下面是二叉树生成的整个顺序:

图解二叉树
二叉树生成过程

二叉树的遍历:

前面我们生成了一棵二叉树,虽然生成了,但是却不知道如果去遍历二叉树输出每个节点对应的数据,那就等于拿到了某件东西却不会使用,这也是不希望看到的一种情况,下面就看看如果遍历一棵二叉树吧!

  1. 先序遍历: 首先访问根节点,这也就是为什么上面创建二叉树的时候要保存根节点的用处,根节点访问之后在访问其左子树,最后再访问右子树;在访问左右子树的时候依旧是按照先根然左后右的顺序。文字想必大家都看的模棱两可的,下面看顺序图吧,更直观,更清晰:

    图解二叉树
    图解二叉树
    图解二叉树
    图解二叉树
    图解二叉树
    image.png


    以上就是整个先序遍历的流程,这九个步骤大家应该一眼就能看的懂,用代码更加容易实现:

 1    /**
2     * 先序遍历,访问根节点的操作发生在遍历其左右节点之前
3     *
4     * @param node 某个根节点
5     */

6    public void preOrder(Node<E> node) {
7        if (node == null) {
8            return;
9        }
10        System.out.print(node + " ");
11        preOrder(node.left);
12        preOrder(node.right);
13    }
  1. 中序遍历:首先访问根节点的左子树,直到左子树访问完,回过头来访问根节点,最后访问左子树,这里便不在贴流程图了,简单的把实现代码贴出来:

 1    /**
2     * 中序遍历,访问根节点的操作发生在遍历左右节点中间
3     *
4     * @param node 某个根节点
5     */

6    public void inOrder(Node<E> node) {
7        if (node == null) {
8            return;
9        }
10        inOrder(node.left);
11        System.out.print(node + " ");
12        inOrder(node.right);
13    }
  1. 后序遍历:首先访问根节点的左子树,直到左子树访问完,回到根节点的右子树,访问完,最后访问根节点,照样贴上实现代码:

 1    /**
2     * 后序遍历,访问根节点的操作发生在遍历左右节点之后
3     *
4     * @param node 某个根节点
5     */

6    public void postOrder(Node<E> node) {
7        if (node == null) {
8            return;
9        }
10        postOrder(node.left);
11        postOrder(node.right);
12        System.out.print(node + " ");
13    }

至此为止,二叉树的内容就结束了,整个的源码可以扫描下方的二维码,我会将源码奉上,切记多敲几遍,这样就才能在脑海中加深印象,不然看过觉得理解了,三天之后就又抛之脑后了!

如果本文章你发现有不正确或者不足之处,欢迎你在下方留言或者扫描下方的二维码留言也可!

图解二叉树
公众号.png

原文始发于微信公众号(Taonce):图解二叉树