数据结构—二叉树(BinaryTree)的入门原理以及Jav

发表于

「这是我参与11月更文挑战的第17天，活动详情查看：2021最后一次更文挑战」。

本文详细介绍了二叉树的基本概念，以及各种二叉树，以及二叉树的Java实现方式，包括顺序结果和链式结构的实现。

二叉树是一种特殊的树，其定义为：二叉树是n(n>=0)个节点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树组成。

1 二叉树的定义

二叉树是一种特殊的树，其定义为：二叉树是n(n>=0)个节点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树组成。 如果不是太清楚树的的概念的，可以看这篇文章：数据结构—树(Tree)的入门原理以及Java实现案例。

如下图，就是一颗二叉树：
在这里插入图片描述

2 二叉树的特性

三个特性：

  1. 每个节点最多有两棵子树，所以二叉树中不存在度大于2的节点。注意不是只有两棵子树，而是最多有。没有子树或者有一棵子树都是可以的。
  2. 左子树和右子树是有顺序的，次序不能任意颠倒。
  3. 即使树中某节点只有一棵子树，也要区分它是左子树还是右子树。

如下案例：一个3个节点树，对于普通的树和二叉树，分别有几种形态？
在这里插入图片描述
普通树，首先有树1形态，而后续四种情况对于普通树是没有区分的，因此只有两种情况；而对于二叉树，则以五种情况都有。

3 特殊的二叉树

3.1 斜二叉树

所有的节点都只有左子树的二叉树叫左斜树。所有节点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。

左斜树：

在这里插入图片描述

右斜树：

在这里插入图片描述

3.2 满二叉树

在一棵二叉树中，如果所有分支节点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树，又称完美二叉树。
在这里插入图片描述

满二叉树的特点：

  1. 叶子只能出现在最下一层。出现在其他层就不可能达成平衡。
  2. 非叶子节点的度一定是2。否则就是“缺胳膊少腿”了。
  3. 在同样深度的二叉树中，满二叉树的节点个数最多，叶子数最多。

3.3 完全二叉树

完全二叉树：除去最后一层叶子节点，就是一颗满二叉树，并且最后一层的节点只能集中在左侧，满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。
在这里插入图片描述
完全二叉树的特点：

  1. 叶子节点只能出现在最下两层。
  2. 最下层的叶子一定集中在左部连续位置。
  3. 倒数二层，若有叶子节点，一定都集中在右部连续位置。
  4. 如果节点度为1，则该节点只有左孩子，即不存在只有右子树的情况。
  5. 同样节点数的二叉树，完全二叉树的深度最小。

3.4 平衡二叉树

平衡二叉树又被称为AVL树（区别于AVL算法），它是具有如下性质：

  1. 它一定是一棵二叉排序树；
  2. 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

平衡二叉树作为重点和难点，此处不多赘述，后面的文章会单独讲。

4 二叉树的性质

共有大概六条性质，这些性质可以被直接用来实现二叉树：

  1. 在二叉树的第i层上至多有2^(i-1)个节点（i≥1）；
  2. 深度为k的二叉树至多有2^k-1个节点（k≥1），最少有k个节点；
  3. 对于任意一棵二叉树，如果其叶子节点数为N0，且度数为2的节点总数为N2，则N0=N2+1；
  4. 具有n个节点的完全二叉树的深度为|log2n+1|（|x|表示不大于x的最大整数）。
  5. 有N个节点的完全二叉树各节点如果用顺序方式存储，若I为节点编号（从1开始），则节点之间有如下关系：
1. 如果 I = 1，则节点I是二叉树的根；I > 1，则其父节点的编号为 I/2，左子节点编号为 2 \* I （如果存在），右子节点编号为 2 \* I + 1（如果存在）；
2. 如果 2 \* I <= N，则其左孩子（即左子树的根节点）的编号为 2 \* I ；若 2 \* I > N，则无左右孩子；
3. 如果 2 \* I + 1 <= N，则其右孩子的节点编号为 2 \* I + 1；若 2 \* I + 1 > N，则无右孩子。
  1. 有N个节点的完全二叉树各节点如果用顺序方式存储，若I为节点编号（从0开始），则节点之间有如下关系：
1. 如果 I = 0，则节点 I 是二叉树的根；I > 0，则其父节点的编号为 (I-1)/2，左子节点编号为 2 \* I + 1（如果存在），右子节点编号为 2 \* I + 2（如果存在）；
2. 如果 2 \* I + 1 <= N，则其左孩子（即左子树的根节点）的编号为 2 \* I +1 ；若 2 \* I + 1 > N，则无左右孩子；
3. 如果 2 \* I + 2 <= N，则其右孩子的节点编号为 2 \* I + 2；若 2 \* I + 2 > N，则无右孩子。

在这里插入图片描述

上图是已经编号了的完全二叉树，具有N=10个节点，设I从1开始，下面来验证各个特性：

  1. I = 1 的节点，确实是根节点；如果 I = 5 > 0，那么父节点编号为5/2，即2。
  2. 如果I=5，2 * 5 = 10，5编号的节点的左孩子为2 * 5 = 10编号；如果I=6，2 * 6 > 10，6编号的节点的无左孩子。
  3. 如果 I = 4，2 * 4 + 1 < 10，4编号的节点的右孩子为2 * 4 + 1 = 9 编号；如果I=5，2 * 5 + 1 > 10，5编号的节点的无右孩子。

最后一个特性：给定n个节点，能构成f(n)种不同的二叉树。f(n)为卡特兰数的第N项：

在这里插入图片描述

5 二叉树的存储结构

5.1 顺序存储结构

5.1.1 顺序存储结构的概述

顺序存储结构对树这种一对多的关系结构实现起来是比较困难的。但是二叉树是一种特殊的树，由于它的特殊性，使得用顺序存储结构也可以实现。

二叉树的顺序存储结构就是用一维数组存储二叉树中的节点，并且节点的存储位置，也就是数组的下标要能体现节点之间的逻辑关系，比如双亲与孩子的关系，左右兄弟的关系等。

此时，完全二叉树的规律性和优越性就显现了出来：

在这里插入图片描述

由于完全二叉树的特性，可以将上图的完全二叉树从上到下，从左到右的遍历，然后顺序存放进数组对应索引的位置中：

在这里插入图片描述

对于一般的二叉树，则可以 “借用” 完全二叉树的的思路，将空出来的节点位置置空：

在这里插入图片描述

如上图的普通二叉树，存储时，将其“转换”为完全二叉树，不存在的节点使用null填充：

在这里插入图片描述

极端情况下，一棵深度为k的右斜树，它只有k个结点，却需要分配2^k-1个存储单元空间,这明显会浪费很多空间。

在这里插入图片描述

因此，顺序存储结构只适用于完全二叉树或者满二叉树。

5.1.2 顺序存储结构的简单实现

提供一个二叉树的顺序存储结构的简单实现，节点不允许为null。

可以看到，子节点和父节点的添加、获取，都是依靠的二叉树性质的第五条的公式，这里把要被实现的二叉树看成了完全二叉树，还是比较简单的，但是可能会浪费内存空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
java复制代码/**
 * 二叉树的顺序存储结构的简单实现
 */
public class ArrayBinaryTree<E> {

    /**
     * 深度
     */
    private int deep;
    /**
     * 容量,也是节点数量
     */
    private int capacity;
    /**
     * 底层数组
     */
    private Object[] elements;

    /**
     * 节点真正数量
     */
    private int size;


    /**
     * 指定树的深度，初始化数组
     *
     * @param deep 树深度
     */
    public ArrayBinaryTree(int deep) {
        this.deep = deep;
        this.elements = new Object[capacity = (int) Math.pow(2, deep) - 1];
    }

    /**
     * 指定树的深度和根节点
     *
     * @param deep
     * @param root
     */
    public ArrayBinaryTree(int deep, E root) {
        this(deep);
        addRoot(root);
    }


    /**
     * 添加根节点
     *
     * @param root 根节点数据
     */
    public void addRoot(E root) {
        checkNullData(root);
        elements[0] = root;
        size++;
    }


    /**
     *
     * 添加子节点
     *
     * @param parentIndex 父节点索引
     * @param data        节点数据
     * @param left        是否是左子节点,true 是;false 否
     * @return 添加成功后子节点的索引
     */
    public int addChild(int parentIndex, E data, boolean left) {
        checkParentIndex(parentIndex);
        checkNullData(data);
        int childIndex;
        if (left) {
            childIndex = parentIndex * 2 + 1;
        } else {
            childIndex = parentIndex * 2 + 2;
        }
        addChild(childIndex, data);
        size++;
        return childIndex;
    }

    /**
     * 添加子节点
     *
     * @param childIndex 子节点索引
     * @param data       子节点数据
     */
    private void addChild(int childIndex, E data) {
        if (elements[childIndex] != null) {
            throw new IllegalStateException("该父节点已经存在该子节点");
        }
        elements[childIndex] = data;
    }


    /**
     * 是否是空树
     *
     * @return true 是 ;false 否
     */
    public boolean isEmpty() {
        return elements[0] == null;
    }


    /**
     * 返回节点数
     *
     * @return 节点数
     */
    public int size() {
        return size;
    }


    /**
     * 获取索引为index的节点的父节点
     *
     * @param index 索引
     * @return 父节点数据
     */
    public E getParent(int index) {
        if (index == 0) {
            return null;
        }
        return (E) elements[(index - 1) / 2];
    }

    /**
     * 获取索引为index的节点的右子节点
     *
     * @param index 索引
     * @return 右子节点数据
     */
    public E getRight(int index) {
        if (2 * index + 1 >= capacity) {
            return null;
        }
        return (E) elements[index * 2 + 2];
    }

    /**
     * 获取索引为index的节点的左子节点
     *
     * @param index 索引
     * @return 左子节点
     */
    public E getLeft(int index) {
        if (2 * index + 1 >= capacity) {
            return null;
        }
        return (E) elements[2 * index + 1];
    }


    /**
     * 获取根节点
     *
     * @return 根节点数据
     */
    public E getRoot() {
        return (E) elements[0];
    }

    /**
     * 获取节点出现的首个索引位置
     *
     * @param data 节点数据
     * @return 节点索引, 或者-1--不存在该节点
     */
    public int indexOf(E data) {
        for (int i = 0; i < capacity; i++) {
            if (elements[i].equals(data)) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 检查子节点是否已经存在
     *
     * @param message 消息
     */
    private void checkChild(int childIndex, String message) {
        if (elements[childIndex] == null) {
            throw new IllegalStateException(message);
        }
    }


    /**
     * 数据判null
     *
     * @param data 添加的数据
     */
    private void checkNullData(E data) {
        if (data == null) {
            throw new NullPointerException("数据不允许为null");
        }
    }

    /**
     * 检查父节点是否存在
     *
     * @param parentIndex 父节点索引
     */
    private void checkParentIndex(int parentIndex) {
        if (elements[parentIndex] == null) {
            throw new NoSuchElementException("父节点不存在");
        }
    }
}

5.2 链式存储结构

采用链式存储结构更加的灵活，为树节点设计一个数据域和两个引用变量，一个保存左子结点的引用，另一个保存右子节点的引用，我们称这样的链表叫做二叉链表。如果有需要还可在加在一个保存父节点引用变量。

5.2.1 链式存储结构的简单实现

下面是一个没有保存父节点引用的二叉树链式存储结构的简单实现，查找其父节点是比较困难的，需要遍历整个树，因此建议加上父节点的引用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
java复制代码/**
 * 二叉树的链式存储结构的简单实现
 */
public class LinkedBinaryTree<E> {

    /**
     * 外部保存根节点的引用
     */
    private BinaryTreeNode<E> root;

    /**
     * 树节点的数量
     */
    private int size;

    /**
     * 内部节点对象
     *
     * @param <E> 数据类型
     */
    public static class BinaryTreeNode<E> {

        //数据域
        E data;
        //左子节点
        BinaryTreeNode<E> left;
        //右子节点
        BinaryTreeNode<E> right;

        public BinaryTreeNode(E data) {
            this.data = data;
        }

        public BinaryTreeNode(E data, BinaryTreeNode<E> left, BinaryTreeNode<E> right) {
            this.data = data;
            this.left = left;
            this.right = right;
        }

        @Override
        public String toString() {
            return data.toString();
        }
    }

    /**
     * 空构造器
     */
    public LinkedBinaryTree() {
    }

    /**
     * 构造器,初始化root节点
     *
     * @param root 根节点数据
     */
    public LinkedBinaryTree(E root) {
        checkNullData(root);
        this.root = new BinaryTreeNode<>(root);
        size++;
    }

    /**
     * 添加子节点
     *
     * @param parent 父节点的引用
     * @param data   节点数据
     * @param left   是否是左子节点,true 是;false 否
     */
    public BinaryTreeNode<E> addChild(BinaryTreeNode<E> parent, E data, boolean left) {
        checkNullParent(parent);
        checkNullData(data);
        BinaryTreeNode<E> node = new BinaryTreeNode<>(data);
        if (left) {
            if (parent.left != null) {
                throw new IllegalStateException("该父节点已经存在左子节点,添加失败");
            }
            parent.left = node;
        } else {
            if (parent.right != null) {
                throw new IllegalStateException("该父节点已经存在右子节点,添加失败");
            }
            parent.right = node;
        }
        size++;
        return node;
    }

    /**
     * 是否是空树
     *
     * @return true 是 ;false 否
     */
    public boolean isEmpty() {
        return size == 0;
    }


    /**
     * 返回节点数
     *
     * @return 节点数
     */
    public int size() {
        return size;
    }

    /**
     * 获取根节点
     *
     * @return 根节点 ;或者null--表示空树
     */
    public BinaryTreeNode<E> getRoot() {
        return root;
    }

    /**
     * 获取左子节点
     *
     * @param parent 父节点引用
     * @return 左子节点或者null--表示没有左子节点
     */
    public BinaryTreeNode<E> getLeft(BinaryTreeNode<E> parent) {
        return parent == null ? null : parent.left;
    }

    /**
     * 获取右子节点
     *
     * @param parent 父节点引用
     * @return 右子节点或者null--表示没有右子节点
     */
    public BinaryTreeNode<E> getRight(BinaryTreeNode<E> parent) {
        return parent == null ? null : parent.right;
    }


    /**
     * 数据判null
     *
     * @param data 添加的数据
     */
    private void checkNullData(E data) {
        if (data == null) {
            throw new NullPointerException("数据不允许为null");
        }
    }


    /**
     * 检查父节点是否为null
     *
     * @param parent 父节点引用
     */
    private void checkNullParent(BinaryTreeNode<E> parent) {
        if (parent == null) {
            throw new NoSuchElementException("父节点不能为null");
        }
    }
}

6 总结

本文为大家介绍了二叉树的入门知识，比如二叉树的概念，特性，性质等，这些东西很多是死的，但是需要我们理解记忆，最后介绍了二叉树的存储结构，以及Java语言的简单实现，对于更加特殊的二叉树，比如红黑树，它们还有自己的独特实现，在后续文章中会介绍。

另外，在实现案例中，并没有树的遍历，以及整颗树的创建等操作，这部分内容较多，将在后续的文章中单独介绍，大家可以关注文章更新。最后，如果大家还不是太清楚树的的概念的，可以看这篇文章：数据结构—树(Tree)的入门原理以及Java实现案例。

相关文章：

  1. 《大话数据结构》
  2. 《算法》
  3. 《算法图解》

如果有什么不懂或者需要交流，可以留言。另外希望点赞、收藏、关注，我将不间断更新各种Java学习博客！

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%