树的基础概念
树的定义
树 (Tree) 是一个由 n (n >= 0) 个节点组成的有限集合，节点即树中的元素。当 n=0 时，树称为空树；当 n>0 时，树 T 符合以下两个条件：
- 有一个特殊的节点称为根 (Root) 节点，它只有后继节点，没有前驱节点。
- 除根节点之外的其他节点可以分为
m (0 <= m < n) 个互不相交的集合 T0、T1、...Tm-1，其中每个集合 Ti (0 <= i < m) 也具有树结构，并称为根节点的子树。
树是递归定义的。节点是树的基本单位，若干个节点组成一棵子树，若干个互不相交的子树组成一棵树。树中的每个节点都是该树中某一棵子树的根。因此，树是由节点组成的、节点之间具有层次关系的非线性结构。
空树、1 个节点和 n 个节点的树如下图所示，节点与其子树根的连线表示节点之间的层次关系。
对于上图中的树 (c)：
A 为树的根节点，其他节点组成 3 个相互不相交的子集 T0、T1、T2 作为 A 的子树。- $T_0=[B,E,F]$，$T_1=[C,G]$，$T_2=[D,H,I,J]$，3 棵子树的根节点分别为
B、C、D。
树的相关术语
父、子、兄弟节点
- 在一棵树中，一个节点的子树根节点称为其子 (Child) 节点；相应地，该节点是其子节点的父 (Parent) 节点。只有根节点没有父节点，其他节点有且只有一个父节点。
- 拥有同一个父节点的多个节点之间互称兄弟 (Sibling) 节点。
- 节点的祖先 (Ancestor) 是指其父节点，以及父节点的父节点等，直至根节点。节点的后代 (Descendant) 是指其所有子节点，以及子节点的子节点，直至叶子节点。
度、叶子节点、分支节点
- 节点的度 (Degree) 是指节点所拥有的子树数量。
- 度为 0 的节点称为叶子 (Leaf) 节点，又称终端节点。树中除叶子节点之外的其他节点称为分支节点，又称非叶节点。
- 一棵树的度指的是树中各节点的度的最大值。
节点层次、树的深度
- 节点的层次 (Level) 属性反映节点处于树中的层次位置。约定根节点的层次为 1，其他节点的层次是其父节点的层数加 1。兄弟节点的层次相同。
- 树的深度 (Depth) 或高度 (Height) 是指树中节点的最大层次数。
边、路径
- 设树中
X 节点是 Y 节点的父节点，有序对儿 (X,Y) 称为连接这两个节点的分支，也称为边 (Edge)。 - 设
(X0,X1,... Xk) (0 < k < n) 是由树中节点组成的一个序列，且 (Xi, Xi+1) (0 <= i < k) 都是树中的边，则称该序列为从 X0 到 Xk 的一条路径 (Path)。路径长度 (Path Length) 为路径上的边数。
无序树、有序树
- 无序树即节点的子树 $(T_0, T_1, \dots, T_{m-1})$ 之间没有次序，可以交换位置的树。
- 如果节点的子树 $(T_0, T_1, \dots, T_{m-1})$ 从左至右是有次序的，不能交换位置，则称该树为有序树（Ordered Tree）。
森林
森林 (Forest) 是 $m$ ($m \geq 0$) 棵互不相交的树的集合。给森林加上一个根节点就会变成一棵树，将树的根节点删除就会变成森林。
树的抽象数据类型
树的操作主要有创建树、获得父/子/兄弟节点、遍历、插入和删除等。声明树的抽象数据类型如下：
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
| /**
* 树的抽象数据类型
* @param <T> 节点元素类型
*/
public abstract class AbstractTree<T> {
//树的根节点
AbstractTreeNode<T> root;
//判断是否是空树
abstract boolean isEmpty();
//返回关键字为 key 节点所在的层次
abstract int level(T key);
//返回树的节点数
abstract int size();
//返回树的深度
abstract int depth();
//输出树的先根次序遍历结果
abstract void preOrder();
//输出树的后根次序遍历结果
abstract void postOrder();
//输出树的层次遍历结果
abstract void levelOrder();
//插入 x 元素作为根节点并返回
abstract AbstractTreeNode<T> insert(T x);
//插入 x 作为 p 节点的第 i 个子节点并返回
abstract AbstractTreeNode<T> insert(AbstractTreeNode<T> p, T x, int i);
//先序遍历查找首个关键字为 key 的节点
abstract AbstractTreeNode<T> search(T key);
//判断是否包含关键字为 key 的元素
abstract boolean contains(T key);
//删除以 key 节点为根的子树
abstract T remove(T key);
//删除 p 节点的第 i 棵子树
abstract void remove(AbstractTreeNode<T> p, int i);
//删除树的所有节点
abstract void clear();
}
|
其中，树的节点抽象类型如下：
1
2
3
4
5
6
7
8
9
10
| /**
* 树节点抽象类
* @param <T> 节点元素类型
*/
public abstract class AbstractTreeNode<T> {
//数据域
public T data;
//节点的所有子节点
List<AbstractTreeNode<T>> children;
}
|
尽管在无序树中，子节点没有固定的次序，但是实际存储时会给子节点指定一个序号（children 集合的下标）来标识它们的顺序。因此，对子节点的获取、插入、删除等操作都会使用序号 $i$（0 ≤ $i$ < 子节点数）作为标识。如果 $i$ 指定的序号超出了子节点的范围，则抛出序号越界异常。
二叉树的原理与实现
二叉树的定义
二叉树 (Binary Tree) 是由 $n$ ($n \geq 0$) 个节点组成的有限集合，当 $n=0$ 时称为空二叉树；$n>0$ 的二叉树由一个根节点和两棵互不相交的、分别称为左子树和右子树的子二叉树构成。二叉树也是递归定义的，在树中定义的度、层次等术语，同样适用于二叉树。
二叉树有 5 种基本形态，如下图所示：
二叉树的性质
性质 1: 设根节点的层次为 1，二叉树第 $i$ 层最多有 $2^{i-1}$ ($i \geq 1$) 个节点。
证明：（归纳法）
- 根是 $i=1$ 层唯一的节点，故 $2^{i-1} = 2^{0} = 1$，命题成立；
- 当 $i>1$ 时，代入公式可得 $i-1$ 层最多有 $2^{i-2}$ 个节点，由于二叉树中每个节点的度最多为 2，所以第 $i$ 层最多有 $2 \times 2^{i-2}=2^{i-1}$ 个节点，命题成立。
性质 2: 在高度为 $h$ 的二叉树中，最多有 $2^{h}-1$ 个节点 ($h>0$)。
证明：由性质 1 可知，高度为 $h$ 的二叉树中，节点数最多为 $\displaystyle\sum_{i = 1}^{h}2^{i-1}=2^k-1$。
性质 3：设一棵二叉树的叶子（度为 0）节点数为 $n_0$，度为 2 的节点数为 $n_2$，则 $n_0=n_2+1$。
证明：
- 设二叉树节点数为 $n$，度为 1 的节点数为 $n_1$，则有 $n=n_0+n_1+n_2$。
- 因为度为 1 的节点只有一个子，度为 2 的节点有两个子，叶子节点没有子，根节点不是任何节点的子，所以 $n=0\times n_0 + 1 \times n_1 + 2 \times n_2 +1$。
综合上述两式，可得 $n_0=n_2+1$。
性质 4：一颗具有 $n$ 个节点的完全二叉树，其高度 $h=[\log_2n]+1$。
满二叉树和完全二叉树
一棵高度为 $h$ 的满二叉树 (Full Binary Tree) 是具有 $2^h-1$ ($h \geq 0$) 个节点的二叉树。
由定义可知，满二叉树中每一层的节点数目都达到最大值。对满二叉树的节点进行连续编号，约定根节点的序号为 0，从根节点开始，自上而下，每层自左至右编号，如下中的树 (a) 所示：
一棵具有 $n$ 个节点高度为 $h$ 的二叉树，如果它的每个节点都与高度为 $h$ 的满二叉树中序号为 $0$ ~ $n-1$ 的节点一一对应，则称这棵二叉树为完全二叉树 (Complete Binary Tree)，如上图中的树 (b) 所示。
满二叉树是完全二叉树，而完全二叉树不一定是满二叉树。完全二叉树的第 1 ~ $h-1$ 层是满二叉树，第 $h$ 层不强求满，并且该层所有节点都必须集中在该层左边的若干位置上。上图中的树 (c) 就不是完全二叉树。
证明：对于一棵有 $n$ 个节点高度为 $h$ 的完全二叉树，有 $2^{h-1}-1 < n \leq 2^h-1$，对不等式移项并求对数，有 $h-1 < \log_2{(n+1)} \leq h$，由于二叉树的高度 $h$ 只能是整数，所以取 $h=[\log_2n]+1$。
- 性质 5：一棵具有 $n$ 个节点的完全二叉树，对序号为 $i$ ($0 \leq i < n$) 的节点，有：
- 若 $i=0$，则 $i$ 为根节点，无父节点；若 $i>0$，则 $i$ 的父节点序号为 $[(i-1) / 2]$。
- 若 $2i+1<n$，则 $i$ 的左子节点序号为 $2i+1$；否则 $i$ 无左子。
- 若 $2i+2<n$，则 $i$ 的右子节点序号为 $2i+2$；否则 $i$ 无右子。
二叉树的遍历规则
尽管二叉树是非线性结构，但其遍历方式访问节点的顺序是线性的，其遍历规则有深度优先和广度优先两种：
- 深度优先遍历（也称为子优先遍历）按照深度优先的原则，遍历完当前节点的所有子节点之后再回溯到父节点继续遍历，其中又分为先序遍历、中序遍历和后序遍历三种方式。
- 广度优先遍历（也称为兄弟优先遍历、层次遍历）按照广度优先的原则，从上到下，从左到右逐层遍历每个节点。
深度优先遍历
已知 3 个元素共有 6 种排列方式，由 3 个元素 A、B、C 构成的一棵二叉树，如下所示：
1
2
3
4
| | 先遍历左子树 | 先遍历右子树
A | 1. 先根次序：ABC | CBA
/ \ | 2. 中根次序：BAC | CAB
B C | 3. 后根次序：BCA | ACB
|
观察上述序列可知，前 3 个序列的共同特点是，B 在 C 之前，即先遍历左子树，后遍历右子树；后 3 个序列分别与前 3 个序列的次序相反。实际上先遍历左子树还是先遍历右子树在算法设计上没有本质区别，因此约定遍历子树的次序是先左后右。
二叉树深度优先的遍历次序有以下 3 种，遍历规则也是递归的，先遍历左子树，再遍历右子树，三者之间的差别仅在于访问节点的时机不同：
- 先根次序 (PreOrder): 访问根节点，遍历左子树，遍历右子树。
- 中根次序 (InOrder): 遍历左子树，访问根节点，遍历右子树。
- 后根次序 (PostOrder): 遍历左子树，遍历右子树访问根节点。
下面分别举一个例子：
一棵二叉树的先根次序遍历顺序为：ABDGCEFH，先访问根节点 A，再访问 A 的左子树，最后访问 A 的右子树：
中根次序遍历顺序为：DGBAECHF，左、右子树上的所有节点，分别在根节点 A 访问前、后访问：
后根次序遍历顺序为：GDBEHFCA，最后访问根节点 A：
广度优先遍历
二叉树的广度优先遍历是按层次进行的，遍历过程从根节点开始，逐层深入，从左至右依次访问完当前层的所有节点再访问下一层。
一棵二叉树的先根次序遍历顺序为：ABCDEFG，如下图所示：
二叉树的抽象数据类型
二叉树的主要操作有：创建二叉树、获得父或子节点、遍历、插入和删除等。
首先我们声明二叉树的抽象节点类 AbstractNode<T>:
1
2
3
4
5
6
7
8
| /**
* 二叉树节点的抽象数据类型
* @param <T> 元素类型
*/
public abstract class AbstractNode<T> {
//数据域
T data;
}
|
- 这里我们只声明了数据域
data，剩下的字段交由实现类补充。
二叉树的数据节点可以有多种实现方式，例如二叉链表、三叉链表，甚至是基于数组的静态链表。不同的实现方式需要的指针域各不相同，但它们都需要有最基本的数据域。
然后声明二叉树的抽象数据类型 AbstractBinaryTree<T>：
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
| /**
* 二叉树抽象数据类型
* @param <T> 节点元素类型
*/
public abstract class AbstractBinaryTree<T> {
//根节点
protected AbstractNode<T> root;
//判断是否是空树
protected boolean isEmpty() {
return root == null;
}
//返回树的节点数
protected int size() {
if (isEmpty()) {
return 0;
}
return size(root);
}
protected abstract int size(AbstractNode<T> node);
//返回树的深度
protected int depth() {
if (isEmpty()) {
return 0;
}
return depth(root);
}
protected abstract int depth(AbstractNode<T> node);
//返回关键字为 key 节点所在的层次
protected abstract int level(T key);
//输出树的先根次序遍历结果
protected abstract void preOrder();
//输出中根次序遍历序列
protected abstract void inOrder();
//输出树的后根次序遍历结果
protected abstract void postOrder();
//输出树的层次遍历结果
protected abstract void levelOrder();
//插入 x 元素作为根节点并返回
protected abstract AbstractNode<T> insert(T x);
//插入 x 元素作为 p 节点的左、右子并返回
protected abstract AbstractNode<T> insert(AbstractNode<T> p, T x, boolean leftChild);
//先序遍历查找首个关键字为 key 的节点
protected abstract AbstractNode<T> search(T key);
//判断是否包含关键字为 key 的元素
protected abstract boolean contains(T key);
//删除 p 节点的左、右子树
protected abstract void remove(AbstractNode<T> p, boolean leftChild);
//删除树的所有节点
protected void clear() {
root = null;
}
}
|
二叉树抽象类中维护了根节点，并实现了 isEmpty() 和 clear() 这两个简单的通用方法。其余的方法根据节点数据类型的不同，会交由特定的子类来实现。
二叉树的存储结构
二叉树主要采用链式存储结构，顺序存储结构仅适用于完全二叉树（满二叉树）。
顺序存储结构
二叉树的顺序存储结构是用数组来表示的，具体方法是将二叉树的节点按照**广度优先遍历（层次遍历）**的顺序依次存放在数组中，然后再根据数组下标的关系来确定节点之间的父子关系。
假设二叉树中的某个节点在数组中的下标为 $i$，则其左子节点在数组中的下标为 $2i + 1$，右子节点在数组中的下标为 $2i + 2$。其父节点在数组中的下标为 $[(i-1) / 2]$ （向下取整）。
顺序存储结构的优点是可以直接根据数组下标来访问节点，因此查找某个节点的效率很高。缺点是需要额外的存储空间来存放空节点（即二叉树中没有的节点），而且在插入和删除节点时需要移动大量的节点，效率较低。因此，顺序存储结构通常适用于节点数比较少、静态不变的二叉树。
以下是一棵 $n$ 个节点的完全二叉树及其顺序存储结构的示意图：
链式存储结构
链式存储结构是一种灵活的存储方式，因为每个节点只需存储自身数据和指向左、右子的指针，可根据情况动态分配内存。常见的链式存储结构有二叉链表、三叉链表和静态二/三叉链表等。
二叉链表
二叉树的二叉链表存储结构如下：
- 除了数据域之外，采用两个地址域分别指向左、右子节点。
采用二叉链表存储二叉树时，每个节点只存储了到其子节点的单向关系，没有存储到其父节点的关系。因此，要获得父节点需要从根节点开始进行二次查找，这将十分浪费性能。
三叉链表
二叉树的三叉链表存储结构如下：
其节点在二叉链表节点的基础上，增加一个地址域 parent 指向其父节点，这样便存储了父节点与子节点的双向关系
静态二/三叉链表
还有一种存储二叉树的方式是静态二/三叉链表，使用节点数组存储所有节点。每个节点都存储其左、右子节点下标，同时还可以（可选地）存储其父节点下标。节点间的关系通过下标表示，如果某个节点不存在，则使用 -1 表示。
下面是一个静态三叉链表的示意图：
基于二叉链表的二叉树实现
首先声明二叉树实现类 BinaryTree<T>，该类继承自二叉树抽象类 AbstractBinaryTree<T>。同时，在 BinaryTree<T> 类中创建内部节点类 BinaryTreeNode<T>，该内部节点类继承自二叉树的抽象节点类 AbstractNode<T>：
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
| /**
* 基于二叉链表的二叉树实现类
* @param <T> 节点元素类型
*/
public class BinaryTree<T> extends AbstractBinaryTree<T> {
/**
* 二叉链表节点类
* @param <T> 节点元素类型
*/
static class BinaryTreeNode<T> extends AbstractNode<T> {
//指针域，分别指向左右子节点
BinaryTreeNode<T> left, right;
//构造方法
public BinaryTreeNode(T data, BinaryTreeNode<T> left,
BinaryTreeNode<T> right) {
this.data = data;
this.left = left;
this.right = right;
}
//构造叶子节点
public BinaryTreeNode(T data) {
super.data = data;
}
@Override
public String toString() {
return super.data.toString();
}
//判断是否是叶子节点
public boolean isLeaf() {
return this.left == null && this.right == null;
}
}
}
|
然后开始实现抽象类定义的抽象方法。
获取二叉树深度
这里需要有两个获取深度的重载方法：depth() 和 depth(AbstractNode<T> node)。其中，depth() 的实现已经在抽象类中提供。depth() 方法会调用 depth(AbstractNode<T> node) 并传入 root 节点来计算深度。因此，我们需要计算从某个节点开始到叶子节点的最大深度：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| @Override
public int depth(AbstractNode<T> node) {
//递归退出条件
if (node == null) {
return 0;
}
int maxChildDepth = 0;
BinaryTreeNode<T> bNode = (BinaryTreeNode<T>) node;
//递归左子树最大深度
int leftChildDepth = depth(bNode.left);
//递归右子树最大深度
int rightChildDepth = depth(bNode.right);
if (leftChildDepth > maxChildDepth) {
maxChildDepth = leftChildDepth;
}
if (rightChildDepth > maxChildDepth) {
maxChildDepth = rightChildDepth;
}
//返回左右子树深度的较大值，然后加上 root 层本身深度
return maxChildDepth + 1;
}
|
获取二叉树节点数量
与获取深度类似，size 也有两个重载方法，其中一个已经在抽象类里实现，我们只需实现计算从某个节点的子树的节点数即可：
1
2
3
4
5
6
7
8
9
| @Override
public int size(AbstractNode<T> node) {
if (node == null) {
return 0;
}
BinaryTreeNode<T> bNode = (BinaryTreeNode<T>) node;
// 递归调用，返回左右子树节点数 + 自身节点数
return size(bNode.left) + size(bNode.right) + 1;
}
|
二叉树插入数据
由于本文介绍的二叉树是最基础的广义二叉树，因此对插入过程做了简化：插入节点时，被插入位置的原节点默认作为新节点的左子节点存在。
1
2
3
4
5
6
| @Override
public BinaryTreeNode<T> insert(T x) {
// 插入 x 作为根节点，原根节点作为 x 的左子，返回 x
BinaryTreeNode<T> oldRoot = (BinaryTreeNode<T>) this.root;
return (BinaryTreeNode<T>) (this.root = new BinaryTreeNode<>(x, oldRoot, null));
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| /**
* 插入 x 为 p 节点的左、右子，将 p 节点的原左、右子下移为 x 的左子
* @param p 目标节点
* @param x 待插入数据
* @param leftChild 待插入节点是否作为左子
* @return x == null，则不插入返回 null；p == null 则抛出异常；成功插入返回 x 节点
*/
@Override
public AbstractNode<T> insert(AbstractNode<T> p, T x, boolean leftChild) {
if (x == null)
return null;
BinaryTreeNode<T> bp = (BinaryTreeNode<T>) p;
if (leftChild) {
BinaryTreeNode<T> old = bp.left;
bp.left = new BinaryTreeNode<>(x, old, null);
return bp.left;
} else {
BinaryTreeNode<T> old = bp.right;
bp.right = new BinaryTreeNode<>(x, old, null);
return bp.right;
}
}
|
二叉树删除子树
在二叉树中删除一个节点，不仅要修改其父节点的 left 或 right 域，还要约定如何调整被删除节点子树结构的规则，即删除一个节点，原先以该节点为根的子树则变成由原左子树和原右子树组成的森林，需要约定一种规则使这个森林组成一棵子树。
由于本文介绍的二叉树是最基础的广义二叉树，因此无法约定左右子树的合并规则，只能直接删除以一个节点为根的一棵子树，然后交给 JVM 去回收空间。代码实现如下：
1
2
3
4
5
6
7
8
9
| @Override
public void remove(AbstractNode<T> p, boolean leftChild) {
BinaryTreeNode<T> bp = (BinaryTreeNode<T>) p;
if (leftChild) {
bp.left = null;
} else {
bp.right = null;
}
}
|
二叉树先根次序遍历
由于先根次序遍历规则是递归的，采用递归算法实现的递归方法必须有参数，通过不同的实际参数区别递归调用执行中的多个方法。而二叉树类必须提供从根节点开始遍历的成员方法，因此，每种递归的遍历算法由两个重载的成员方法实现。
BinaryTree<T> 类声明以下重载的成员方法，以先根次序遍历二叉树，采用递归算法实现递归的先根次序遍历规则：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| @Override
public void preOrder() {
//先从根节点开始遍历
preOrder((BinaryTreeNode<T>) this.root);
System.out.println("");
}
private void preOrder(BinaryTreeNode<T> p) {
//递归退出条件
if (p == null) {
return;
}
//先序调用根节点
System.out.print(p + " ");
//递归调用左子树
preOrder(p.left);
//递归调用右子树
preOrder(p.right);
}
|
二叉树中根次序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| @Override
public void inOrder() {
//先传入根节点
inOrder((BinaryTreeNode<T>) this.root);
System.out.println("");
}
private void inOrder(BinaryTreeNode<T> p) {
//递归退出条件
if (p == null) {
return;
}
//递归调用左子树
inOrder(p.left);
//中序遍历根节点
System.out.print(p + " ");
//递归调用右子树
inOrder(p.right);
}
|
二叉树后根次序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| @Override
public void postOrder() {
//先传入根节点
postOrder((BinaryTreeNode<T>) this.root);
System.out.println("");
}
private void postOrder(BinaryTreeNode<T> p) {
//递归退出条件
if (p == null) {
return;
}
//递归调用左子树
postOrder(p.left);
//递归调用右子树
postOrder(p.right);
//后序遍历根节点
System.out.print(p + " ");
}
|
二叉树层次遍历
层次遍历即广度优先遍历，这种算法的特点是通过一个先进先出的 Queue 来控制遍历进程：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| @Override
public void levelOrder() {
BinaryTreeNode<T> rootNode = (BinaryTreeNode<T>) this.root;
//判空
if (rootNode == null) {
return;
}
Queue<BinaryTreeNode<T>> queue = new LinkedList<>();
//先将 root 加入队列
queue.offer(rootNode);
while (!queue.isEmpty()) {
// 一弹二入
BinaryTreeNode<T> poll = queue.poll();
System.out.print(poll + " ");
if (poll.left != null) {
queue.offer(poll.left);
}
if (poll.right != null) {
queue.offer(poll.right);
}
}
System.out.println();
}
|
二叉树节点查询
查询涉及两个方法 search(T key) 和 contains(T key)，需要从根节点开始，遍历二叉树进行查询。
首先我们声明一个 search 的重载方法然后用递归实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| @Override
public AbstractNode<T> search(T key) {
return search((BinaryTreeNode<T>) root, key);
}
public AbstractNode<T> search(BinaryTreeNode<T> node, T key) {
if (node == null || key == null) {
return null;
}
//找到则返回
if (node.data.equals(key)) {
return node;
}
//递归左节点
AbstractNode<T> search = search(node.left, key);
if (search != null) {
return search;
}
//递归右节点
search = search(node.right, key);
return search;
}
|
然后 contains(T key) 方法直接调用 search(T key) 即可：
1
2
3
4
| @Override
public boolean contains(T key) {
return search(key) != null;
}
|
二叉树节点层数
获取节点层数与获取二叉树深度类似，都可以通过递归重载方法实现，找到了返回层数，找不到返回 -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
| @Override
public int level(T key) {
BinaryTreeNode<T> rootNode = (BinaryTreeNode<T>) this.root;
//判空
if (rootNode == null) {
return -1;
}
return level(rootNode, key, 1);
}
//重载方法
private int level(BinaryTreeNode<T> node, T key, int level) {
//判空
if (node == null) {
return -1;
}
//找到了，返回节点层数
if (node.data == key) {
return level;
}
//递归左子树
int levelLeft = level(node.left, key, level + 1);
if (levelLeft != -1) {
return levelLeft;
}
//递归右子树
return level(node.right, key, level + 1);
}
|
需要注意，我们给重载方法新增了一个参数 level 来保存当前节点的层数，这样递归实现起来就更加简便了。
二叉排序树的原理与实现
二叉排序树的性质
二叉排序树 (Binary Sort Tree)，又称为二叉搜索树 (Binary Search Tree)，它具有以下几个性质：
- 每个节点都有一个关键字 (key)，可以用来比较节点之间的大小，并且各节点的关键字互不相同。
- 对于每个节点，如果它的左子树不为空，那么左子树上所有节点的关键字都小于它的根节点；如果它的右子树不为空，那么右子树上所有节点的关键字都大于它的根节点。
- 每个节点的左、右子树也都是二叉排序树。
二叉排序树可以通过二分法加速查询，平均时间复杂度为 $O(\log n)$ ~ $O(n)$。
二叉排序树的数据类型
首先，我们声明一个表示二叉排序树的数据类型 BinarySortTree<K extends Comparable<K>, V>，其中的泛型 K 和 V 分别表示节点的键和值。
然后，我们在这个数据类型的内部声明一个数据节点类型 Node，该节点类型包含四个属性：key 表示节点的键，value 表示节点的值，left 和 right 分别表示节点的左子树和右子树。通过这个节点类型，我们可以表示二叉排序树中的节点。
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
| /**
* 二叉排序树数据结构
* @param <K> 节点 Key
* @param <V> 节点 Value
*/
public class BinarySortTree<K extends Comparable<K>, V> {
/**
* 数据节点内部类
*/
private class Node {
private K key;
private V value;
private Node left, right;
public Node(K key, V value) {
this.key = key;
this.value = value;
}
}
/**
* 根节点
*/
private Node root;
/**
* 节点总数
*/
private int count;
}
|
- 为了声明关键字
K 的可比较性，我们让关键字 K 继承了 Comparable<T> 接口。
二叉排序树插入操作
二叉排序树的插入过程通过递归地向下比较节点的关键字大小，直到找到一个空位置，然后将新节点插入该位置。如果新节点的关键字与已有节点的关键字相同，则执行更新操作。实现代码如下：
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
| public void insert(K key, V value) {
// 接收递归最外层返回的 root 节点
root = insertNode(root, key, value);
}
private Node insertNode(Node node, K key, V value) {
// 找到颗空位，创建新节点，并返回
if (node == null) {
++count;
return new Node(key, value);
}
int compare = key.compareTo(node.key);
if (compare < 0) {
// 如果新节点的 key 值小于当前节点，递归左子树
node.left = insertNode(node.left, key, value);
} else if (compare > 0) {
// 如果新节点的 key 值大于当前节点，递归右子树
node.right = insertNode(node.right, key, value);
} else {
// 如果新节点的 key 值与当前节点相等，更新节点的值
node.value = value;
}
// 如果当前位置不为空，则返回本身
return node;
}
|
二叉排序树查找操作
二叉排序树的查找操作包括 search 和 contain 两个方法，这两个方法的查找过程相同，只是返回的数据类型不同。
我们先来看 search 方法，该方法递归地查找二叉排序树中是否存在指定的关键字 key。在每个节点中，比较当前节点的关键字与要查找的关键字 key 的大小，根据大小关系向左或向右递归查找，直到找到对应的节点或查找到了一个空节点：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public Node search(K key) {
return searchNode(root, key);
}
private Node searchNode(Node node, K key) {
if (node == null) {
return null;
}
int compare = key.compareTo(node.key);
if (compare == 0) {
return node;
} else if (compare < 0) {
return searchNode(node.left, key);
} else {
return searchNode(node.right, key);
}
}
|
contain 方法的实现与 search 方法基本相同，只是 contain 方法返回一个布尔值，用于表示二叉排序树中是否存在给定的关键字：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public boolean contain(K key) {
return containNode(root, key);
}
private boolean containNode(Node node, K key) {
if (node == null) {
return false;
}
int compare = key.compareTo(node.key);
if (compare == 0) {
return true;
} else if (compare < 0) {
return containNode(node.left, key);
} else {
return containNode(node.right, key);
}
}
|
二叉排序树删除操作
二叉排序树的删除过程是通过递归地比较节点的 key 大小，直到找到目标节点，然后将其删除。
- 如果目标节点的 key 小于当前节点的 key，则递归删除当前节点的左子树中的节点；
- 如果目标节点的 key 大于当前节点的 key，则递归删除当前节点右子树中的节点；
- 如果目标节点的 key 等于当前节点的 key，则根据被删除的节点的子节点情况，进行不同的处理：
- 如果要删除的节点没有左右子树，则可以直接删除该节点；
- 如果要删除的节点只有左子树或右子树，则可以用它的左子树或右子树的根节点代替该节点。
- 如果要删除的节点既有左子树又有右子树，则可以用其右子树中最小的节点代替该节点，然后删除其右子树中最小的节点。
实现如下：
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
| public void remove(K key) {
root = deleteNode(root, key);
}
/**
* 递归删除目标节点
*/
private Node deleteNode(Node node, K key) {
if (node == null) {
return null;
}
int compare = key.compareTo(node.key);
if (compare < 0) {
// key 小于当前节点，递归左子树
node.left = deleteNode(node.left, key);
return node;
} else if (compare > 0) {
// key 大于当前节点，递归右子树
node.right = deleteNode(node.right, key);
return node;
} else {
// 找到了目标节点，开始删除
if (node.left == null && node.right == null) {
// 如果左右子树都为空，直接删除节点即可
--count;
return null;
} else if (node.left != null && node.right == null) {
// 如果只有左子树，把左子树整个移交给前驱节点即可
Node leftSubTreeRoot = node.left;
node.left = null;
--count;
return leftSubTreeRoot;
} else if (node.left == null) {
// 如果只有右子树，把右子树整个移交给前驱节点即可
Node rightSubTreeRoot = node.right;
node.right = null;
--count;
return rightSubTreeRoot;
} else {
// 如果 node 左右子树都存在，那么需要合并两个子树
// 根据性质，node 左子树所有节点，都小于其右子树中最小的节点，
// 因此我们可以将右子树中最小的节点提升到删除节点的位置
Node newNode = getMinNode(node.right);
// 摘下右子树中最小节点，然后作为新节点的右子树
newNode.right = removeMinNode(node.right);
// 左子树不动，直接作为新节点的左子树
newNode.left = node.left;
node.left = node.right = null;
return newNode;
}
}
}
|
当被删除节点的左右子树都存在时，我们可以还选择用其右子树中最小的节点或者其左子树中最大的节点来代替该节点。
二叉排序树遍历操作
二叉排序树的遍历操作也分为深度优先和广度优先两类，遍历方法与普通的二叉树完全一样，这里不再赘述。
二叉排序树的局限性
二叉排序树的主要局限性在于插入顺序会影响它的高度。例如，如果将有序序列插入到二叉排序树中，会得到一棵非常高的树，其高度接近于节点数量 $n$。这种情况会导致树的搜索效率变得非常低，甚至退化成链表，从而使时间复杂度退化为 $O(n)$，失去了二叉排序树的优势。
为了解决这个问题，人们发明了许多基于二叉排序树的改进算法，如 AVL 树、红黑树等。这些改进算法的目的是使树的高度始终保持在一个可控的范围内，从而保证二叉排序树的高效性。
AVL 树的原理与实现
AVL 树的性质
为了降低二叉排序树的高度，提高查询效率，前苏联数学家 G.M.Adelsen-Velskii 和 E.M.Landis 在 1962 年提出了一种高度平衡的二叉排序树，被称为 AVL 树 （又称平衡二叉排序树）。
AVL 树在保持二叉排序树性质的基础上，还需要满足以下两个性质：
- 节点的左子树和右子树都是平衡二叉树；
- 节点的左子树和右子树的高度差的绝对值不超过 1。
节点的左子树和右子树的高度差被称为平衡因子 (Balance Factor)，处于平衡态的 AVL 树中任意一个节点的平衡因子只可能是 -1、0 或 1。
如果一个节点的平衡因子的绝对值等于 2，那么以该节点为根的子树就被称为最小不平衡子树，它是失衡后需要调整的目标。
学习过程中我们可以通过使用该网站上的工具来加深理解：AVL Tree Visualization。
数据类型设定
首先，我们定义一个泛型类 AVLTree<K extends Comparable<K>, V> 表示 AVL 树，其中 K 表示节点键的类型，V 表示节点值的类型。该类包含 root、count 两个属性，分别用于表示根节点和节点数。然后再在这个类内部声明一个三叉节点类型 Node<K extends Comparable<K>, V>，该静态内部类型包含六个属性：key 表示节点的键，value 表示节点的值，left、right 和 parent 分别表示节点的左子节点、右子节点和父节点，height 表示节点的高度（用于计算平衡因子）。最后，在 AVLTree 中设置一些方便获取节点属性的静态方法（让后续的节点操作代码看起来更干净）。代码实现如下：
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
| public class AVLTree<K extends Comparable<K>, V> {
/**
* 根节点
*/
private Node<K, V> root;
/**
* 节点总数
*/
private int count;
/**
* 三叉节点类
*/
private static class Node<K extends Comparable<K>, V> {
K key;
V value;
Node<K, V> left, right, parent;
int height;
/**
* Node 构造方法，创建节点时，需要设置节点的父节点，和节点高度
*/
Node(K key, V value, Node<K, V> parent, int height) {
this.key = key;
this.value = value;
this.parent = parent;
this.height = height;
}
// getter setter ...
}
/**
* 获取左子节点
*/
private static <K extends Comparable<K>, V> Node<K, V> leftOf(Node<K, V> n) {
return n == null ? null : n.left;
}
/**
* 获取右子节点
*/
private static <K extends Comparable<K>, V> Node<K, V> rightOf(Node<K, V> n) {
return n == null ? null : n.right;
}
/**
* 获取父节点
*/
private static <K extends Comparable<K>, V> Node<K, V> parentOf(Node<K, V> n) {
return n == null ? null : n.parent;
}
/**
* 获取节点高度
*/
private static <K extends Comparable<K>, V> int heightOf(Node<K, V> n) {
return n == null ? 0 : n.height;
}
/**
* 设置节点高度
*/
private static <K extends Comparable<K>, V> void setHeight(Node<K, V> n, int height) {
if (n != null) {
n.height = height;
}
}
/**
* 更新节点高度，值为左右子树高度的较大值 + 1
*/
private static <K extends Comparable<K>, V> void updateHeight(Node<K, V> n) {
setHeight(n, Math.max(heightOf(n.left), heightOf(n.right)) + 1);
}
}
|
旋转操作
当插入或删除节点导致 AVL 树失衡后，需要通过旋转操作恢复平衡。所有类型的二叉排序树的旋转规则都是通用的。
左旋操作
设有两个节点：p 与 r，其中 r 是 p 的右子节点。二叉树的左旋操作就是将 p 与其右子节点 r 反转：右子节点 r 将成为 p 的父节点，而 p 将成为 r 的左子节点，同时原先 r 的左子节点也将依据二叉排序树的有序性成为 p 的右子节点。代码实现如下：
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
| /**
* 将 p、p->r 两个节点左旋，同时安置 r 的左子节点
* 示意图：
*
* pp pp pp
* \ \ \
* p r r
* / \ / \ / \
* l r ==> p rr ==> p rr
* / \ / / \
* rl rr l rl l rl
*/
private void rotateLeft(Node<K, V> p) {
if (p != null) {
// rl 需要左摆到 p 右子节点处，所以先缓存 r 引用
Node<K, V> r = p.right;
p.right = r.left;
if (r.left != null)
r.left.parent = p;
// 然后让 r 短接 p
r.parent = p.parent;
if (p.parent == null) {
// 如果 p 是根节点，则 r 将称为新的根节点
root = r;
} else if (p.parent.left == p) {
// 如果 p 是 p 父节点的左子，那么 r 也做它的左子
p.parent.left = r;
} else {
// 如果 p 是 p 父节点的右子，那么 r 也做它的右子
p.parent.right = r;
}
// 最终，颠倒 p 与 r 的关系
r.left = p;
p.parent = r;
}
}
|
右旋操作
右旋操作与左旋操作是镜像的，这里就不再展开了，代码实现如下：
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
| /**
* 将 p、p->r 两个节点左旋，同时安置 l 的右子节点
* 示意图：
*
* pp pp pp
* \ \ \
* p l l
* / \ / \ / \
* l r ==> ll p ==> ll p
* / \ \ / \
* ll lr lr r lr r
*/
private void rotateRight(Node<K, V> p) {
if (p != null) {
Node<K, V> l = p.left;
// rl 需要左摆到 p 右子节点处，所以先缓存 r 引用
p.left = l.right;
if (l.right != null)
l.right.parent = p;
// 然后用 l 短接 p
l.parent = p.parent;
if (p.parent == null) {
root = l;
} else if (p.parent.left == p) {
p.parent.left = l;
} else {
p.parent.right = l;
}
// 最后颠倒 l 与 p
p.parent = l;
l.right = p;
}
}
|
再平衡操作
上文说过，最小不平衡子树根节点的左右子树高度差为 2，因此我们需要以这个根节点为中心，往较矮子树的一侧旋转：
- 如果左子树的高度高于右子树，则将子树的根节点与其左节点向右旋转；
- 如果右子树的高度高于左子树，则将子树的根节点与其右节点向左旋转。
旋转完成后，还需要从原最小不平衡子树的根节点开始，向上遍历更新节点的高度，直到 root 节点。代码实现如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| /**
* 最小不平衡子树的再平衡操作
* @param n 最小不平衡子树的根节点
*/
private void rebalanced(Node<K, V> n) {
// 获取左右子树的高度
int lh = Math.abs(heightOf(leftOf(n)));
int rh = Math.abs(heightOf(rightOf(n)));
if (lh > rh) {
// 如果左子树深度大于右子树，右旋
rotateRight(n);
} else {
// 否则左旋
rotateLeft(n);
}
// 从 n 开始，向上遍历更新各节点高度，直到 root
Node<K, V> p = n;
do {
updateHeight(p);
p = parentOf(p);
} while (p != null);
}
|
插入节点
AVL 树插入节点的过程与二叉排序树相似，都是通过二分法查找空位并插入。只是向 AVL 树中插入节点时需要维护新节点所在链路的节点的高度，并且在插入完成后需要寻找最小不平衡子树并执行再平衡操作。代码实现如下：
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
| public void insert(K key, V value) {
Node<K, V> t = this.root;
if (t == null) {
// 空树，直接作为根节点插入
root = new Node<>(key, value, null, 1);
count = 1;
return;
}
// 递归查找插入位置，同二叉排序树
Node<K, V> p;
int compare;
do {
p = t;
compare = key.compareTo(t.key);
if (compare < 0) {
// 向左递归
t = t.left;
} else if (compare > 0){
// 向右递归
t = t.right;
} else {
// 执行更新操作
t.setValue(value);
return;
}
} while (t != null);
++count;
Node<K, V> e = new Node<>(key, value, p, 1);
if (compare < 0) {
// 作为左子节点插入
p.left = e;
} else {
// 作为右子节点插入
p.right = e;
}
// 从插入节点的父节点开始，向上寻找最小不平衡子树根节点
// 同时，更新一路上遇到的节点的高度
Node<K, V> n = null;
do {
updateHeight(p);
int lh = Math.abs(heightOf(leftOf(p)));
int rh = Math.abs(heightOf(rightOf(p)));
int balanceFactor = lh - rh;
if (balanceFactor > 1 || balanceFactor < -1) {
n = p;
break;
} else {
p = p.parent;
}
} while (p != null);
// 如果存在最小不平衡子树，则执行再平衡操作
if (n != null) {
rebalanced(n);
}
}
|
删除节点
AVL 树删除节点的过程也与二叉排序树相似，都是通过二分法找到目标节点并删除。只是在删除过程中，AVL 树需要维护节点的高度，并且删除完成后需要向上寻找最小不平衡子树的根节点，对其进行再平衡操作。代码实现如下：
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
| public V remove(K key) {
Node<K, V> n = this.root;
if (n == null) { //判空
return null;
}
// 递归查找删除位置，同二叉排序树
Node<K, V> t = null;
int compare;
do {
compare = key.compareTo(n.key);
if (compare < 0) {
n = n.left; // 向左递归
} else if (compare > 0) {
n = n.right; // 向右递归
} else {
// 找到了
t = n;
break;
}
} while (n != null);
if (t == null) { // 没找到目标节点
return null;
}
// 缓存旧值
V oldValue = t.value;
// 删除节点 t，如果失衡则进行再平衡
deleteNode(t);
return oldValue;
}
|
该方法找到 key 等于参数的节点后，会调用 deleteNode 方法完成后续工作。deleteNode 删除节点时会观察被删除节点的子节点情况：
- 如果被删除节点是叶子节点，则直接删除这个节点，并从被删节点的父节点开始向上寻找最小不平衡子树；
- 如果被删除节点存在唯一子节点，则用这个唯一的子节点代替被删除节点，然后从这个被挪上来的子节点开始，向上寻找最小不平衡子树；
- 如果被删除节点存在两个子节点，则用其左子树中的最大节点覆盖被删除节点，然后递归删除这个左子树中的最大节点。
也可以使用右子树中的最小节点
代码实现如下：
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
| private void deleteNode(Node<K, V> e) {
--count;
// 如果被删除节点的左右子节点均不为空，则使用左子树中的最大节点覆盖被删除的节点
if (e.left != null && e.right != null) {
Node<K, V> s = getMaxNode(e.left);
e.key = s.key;
e.value = s.value;
// 并将 e 引用指向左子树最大节点，准备删除
e = s;
}
if (e.left == null && e.right == null) {
// 如果 e 是叶子节点，直接删除即可
if (e.parent.left == e)
e.parent.left = null;
else
e.parent.right = null;
} else if (e.left != null) {
// 如果 e 存在左子节点，则用左子节点短接 e
if (e.parent.left == e)
e.parent.left = e.left;
else
e.parent.right = e.left;
} else {
// 如果 e 存在右子节点，则用右子节点短接 e
if (e.parent.left == e)
e.parent.left = e.right;
else
e.parent.right = e.right;
}
Node<K, V> p = e.parent; // 先缓存 e 的父节点
e.parent = null; // 彻底摘下 e
// 从被摘下节点 e 的父节点开始，向上寻找最小不平衡子树根节点
// 同时，更新一路上遇到的节点的高度
Node<K, V> n = null;
do {
updateHeight(p);
int lh = Math.abs(heightOf(leftOf(p)));
int rh = Math.abs(heightOf(rightOf(p)));
int balanceFactor = lh - rh;
if (balanceFactor > 1 || balanceFactor < -1) {
n = p;
break;
} else {
p = p.parent;
}
} while (p != null);
// 如果存在最小不平衡子树，则执行再平衡操作
if (n != null) {
rebalanced(n);
}
}
|
其中，获取左子树的最大节点的方法实现如下：
1
2
3
4
5
6
7
8
9
10
11
| /**
* 获取子树中的最大节点
* @param r 子树根节点
*/
private Node<K, V> getMaxNode(Node<K, V> r) {
if (r.right == null) {
return r;
} else {
return getMaxNode(r.right);
}
}
|
二叉堆的原理与应用
二叉堆是一种特殊的二叉树，通常用数组来实现。根据第一个元素是最大值还是最小值，可以将二叉堆分为大顶堆和小顶堆两种：
- 大顶堆：树的根节点是最大值，且父节点的值永远大于或等于其子节点的值。
- 小顶堆：树的根节点是最小值，且父节点的值永远小于或等于其子节点的值。
二叉堆的特点
二叉堆具有以下特点：
- 堆序性质：二叉堆满足堆序性质，即父节点的值要么大于等于（最大堆）其子节点的值，要么小于等于（最小堆）其子节点的值。
- 假设用数组实现，父节点和子节点之间的关系可以用数组索引来表示。具体来说，对于给定的节点
i：- 其父节点位于位置
(i-1)/2； - 其左子节点位于位置
2*i+1； - 其右子节点位于位置
2*i+2。
- 插入和删除操作的时间复杂度为 $O(\log n)$。
二叉堆在 PriorityQueue 中的应用
PriorityQueue 是 Java 类库中的一个优先队列，它的核心数据结构就是小顶堆。
优先队列是一种特殊的队列，它与普通队列的主要区别在于优先队列中的元素是按照优先级顺序排列的，而不是按照插入顺序。在优先队列中，具有更高优先级的元素会先被处理，而具有相同优先级的元素则可能按照其插入顺序处理。
这里我们观察其插入方法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length)
grow(i + 1);
size = i + 1;
if (i == 0)
queue[0] = e;
else
siftUp(i, e);
return true;
}
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
|
以通过默认比较器排序的实现为例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| // k 为当前队列元素的总数量，x 为待插入的数据
private void siftUpComparable(int k, E x) {
// key 即待插入元素的值
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
int parent = (k - 1) >>> 1; // 找到 k 位置的父节点
Object e = queue[parent];
if (key.compareTo((E) e) >= 0) // 如果已经比父节点大了，直接插入
break;
queue[k] = e; // 如果
k = parent;
}
queue[k] = key;
}
|
siftUpComparable 其实就是通过小顶堆选择合适的位置。该方法首先设想将待插入元素放入 k 索引处，然后循环遍历。每次循环都会寻找 k 索引位置的父节点：
- 如果
k 节点的值大于父节点，则插入返回； - 否则交换
k 与其父元素，继续下一轮判断，直到 x 大于其父节点或者到达根节点时结束。
可见，二叉堆模型上较二叉排序树宽松，它只需要保证每个父节点比他的两个子节点小即可，也就是 P(i) < P(2 * i + 1) && P(i) < P(2 * i + 2)。以子节点的视角来看，那就是每个子节点的值必须大于它的父节点，即 P(i) > P((i - 1) / 2)。
至此，二叉树家族的核心内容就介绍完毕了！
