树（Tree）这种数据结构真的很像我们现实生活中的树，这里面每个元素我们叫做“节点”；用来连接相邻节点之间的关系，我们叫做“父子关系”。如下图所示，A 节点是 B 节点的父节点，B 节点是 A 节点的子节点。B、C、D 这三个节点的父节点是同一节点，所以它们之间互称为兄弟节点。我们把没有父节点的节点叫做根节点，也就是节点 E。我们把没有子节点的节点叫做叶子节点，比如图中的 G、H、I、J、K、L 都是叶子节点。
除此之外，关于树，还有三个比较相似的概念：高度（Height）、深度（Depth）、层（Level）：
- 节点的高度：节点到叶子节点的最长路径（边数）
- 节点的深度：根节点到这个节点所经历的边的个数
- 节点的层数：节点的深度 + 1
- 树的高度：根节点的高度
要记住这几个概念，我们可以类比“高度”“深度”“层”这几个名词在生活中的含义。在日常生活中，“高度”这个概念，其实就是从下往上度量，比如我们要度量第 10 层楼的高度、第 13 层楼的高度，起点都是地面。所以，树这种数据结构的高度也是一样，从最底层开始计数，并且计数的起点是 0。“深度”这个概念在生活中是从上往下度量的，比如水中鱼的深度，是从水平面开始度量的。所以，树这种数据结构的深度也是类似的，从根结点开始度量，并且计数起点也是 0。“层数”跟深度的计算类似，但计数起点是 1，也就是说根节点位于第 1 层。
二叉树
树结构多种多样，不过我们最常用还是二叉树（Binary Tree）。二叉树，顾名思义，每个节点最多有两个子节点，分别是左子节点和右子节点。不过，二叉树并不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点。如下图所示的几个树，都属于二叉树。
- 其中编号 2 的二叉树中，叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点，这种二叉树就叫做满二叉树。
- 其中编号 3 的二叉树中，叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫做完全二叉树。
满二叉树很好理解，也很好识别，但是完全二叉树不太容易区分。下图中画了几个完全二叉树和非完全二叉树的例子，可以对比着看看。
1. 如何表示一棵二叉树？
想要表示（或存储）一棵二叉树，我们有两种方法，一种是基于指针或引用的二叉链式存储法，一种是基于数组的顺序存储法。我们先来看比较简单、直观的链式存储法
链式存储法
从图中可以很清楚地看到，每个节点有三个字段，其中一个存储数据，另外两个是指向左右子节点的指针。我们只要拎住根节点，就可以通过左右子节点的指针，把整棵树都串起来。这种存储方式是比较常用的，大部分二叉树代码都是通过这种结构来实现的。
顺序存储法
我们把根节点存储在下标 i = 1 的位置，那左子节点存储在下标 2 i = 2 的位置，右子节点存储在 2 i + 1 = 3 的位置。以此类推，B 节点的左子节点存储在 2 i = 2 2 = 4 的位置，右子节点存储在 2 i + 1 = 2 2 + 1 = 5 的位置。具体示例如下图所示：
即如果节点 X 存储在数组中下标为 i 的位置，下标为 2i 的位置存储的就是左子节点，下标为 2i + 1 的位置存储的就是右子节点。反过来，下标为 i/2 的位置存储就是它的父节点。通过这种方式，我们只要知道根节点存储的位置（一般为方便计算子节点，根节点会存储在下标为 1 的位置）就可以通过下标计算，把整棵树串起来。
不过，上面举的例子是一棵完全二叉树，所以仅仅“浪费”了一个下标为 0 的存储位置。如果是非完全二叉树，其实会浪费比较多的数组存储空间。
所以，如果某棵二叉树是一棵完全二叉树，那用数组存储无疑是最节省内存的一种方式。因为数组的存储方式并不需要像链式存储法那样，要存储额外的左右子节点的指针。这也是为什么完全二叉树会单独拎出来的原因，也是为什么完全二叉树要求最后一层的子节点都靠左的原因。
2. 如何遍历一颗二叉树？
遍历二叉树的方法有经典的三种：前序遍历、中序遍历和后序遍历。其中，前、中、后序，表示的是节点与它的左右子树节点遍历打印的先后顺序。
- 前序遍历：对于树中的任意节点，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。
- 中序遍历：对于树中的任意节点，先打印它的左子树，然后再打印它本身，最后打印它的右子树。
- 后序遍历：对于树中的任意节点，先打印它的左子树，然后再打印它的右子树，最后打印这个节点。
实际上，二叉树的前、中、后序遍历就是一个递归的过程。比如，前序遍历，其实就是先打印根节点，然后再递归地打印左子树，最后递归地打印右子树。所以，我们可以把前、中、后序遍历的递推公式都写出来。
前序遍历的递推公式：preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)中序遍历的递推公式：inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)后序遍历的递推公式：postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r
代码实现：
/**
* 前序遍历
*/
public void preOrder(TreeNode root) {
if (root == null) {
return;
}
System.out.println(root.value);
preOrder(root.left);
preOrder(root.right);
}
/**
* 中序遍历
*/
public void inOrder(TreeNode root) {
if (root == null) {
return;
}
inOrder(root.left);
System.out.println(root.value);
inOrder(root.right);
}
/**
* 后序遍历
*/
public void postOrder(TreeNode root) {
if (root == null) {
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.println(root.value);
}
从前面画的前、中、后序遍历的顺序图，可以看出来，每个节点最多会被访问两次，所以遍历操作的时间复杂度跟节点的个数 n 成正比，也就是说二叉树遍历的时间复杂度是 O(n)。
二叉查找树
二叉查找树（Binary Search Tree）是二叉树中最常用的一种类型，也叫二叉搜索树，最大的特点是支持动态数据集合的快速插入、删除、查找操作。而要做到这些，需要依赖于二叉查找树的特殊结构。二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。 下图为二叉查找树的几个例子：
1. 查找
首先，我们看如何在二叉查找树中查找一个节点。我们先取根节点，如果它等于我们要查找的数据，那就返回。如果要查找的数据比根节点的值小，那就在左子树中递归查找；如果要查找的数据比根节点的值大，那就在右子树中递归查找。
代码实现：
public TreeNode findNode(int data) {
// root为树的根节点
return findNodeInternal(root, data);
}
private TreeNode findNodeInternal(TreeNode node, int data) {
if (node == null) {
return null;
}
if (node.value == data) {
return node;
}
if (node.value < data) {
return findNodeInternal(node.right, data);
} else {
return findNodeInternal(node.left, data);
}
}
2. 插入
二叉查找树的插入过程和查找类似。新插入的数据一般都是在叶子节点上，所以我们只需要从根节点开始，依次比较要插入的数据和节点的大小关系。如果要插入的数据比节点的数据大，并且节点的右子树为空，就将新数据直接插到右子节点的位置；如果不为空，就再递归遍历右子树，查找插入位置。同理，如果要插入的数据比节点数值小，并且节点的左子树为空，就将新数据插入到左子节点的位置；如果不为空，就再递归遍历左子树，查找插入位置。
代码实现：
public void insertNode(int data) {
// root为树的根节点
if (root == null) {
root = new TreeNode(data);
return;
}
insertNodeInternal(root, data);
}
private void insertNodeInternal(TreeNode node, int data) {
if (node.value < data) {
if (node.right == null) {
node.right = new TreeNode(data);
} else {
insertNodeInternal(node.right, data);
}
} else {
if (node.left == null) {
node.left = new TreeNode(data);
} else {
insertNodeInternal(node.left, data);
}
}
}
3. 删除
二叉查找树的删除操作比较复杂，针对要删除节点的子节点个数的不同，我们分为以下三种情况：
- 如果目标节点大于当前节点值，则去右子树中删除；
- 如果目标节点小于当前节点值，则去左子树中删除；
- 如果目标节点就是当前节点，分为以下三种情况：
- 其无左子：其右子顶替其位置，删除了该节点；
- 其无右子：其左子顶替其位置，删除了该节点；
- 其左右子节点都有：其左子树转移到其右子树的最左节点的左子树上，然后右子树顶替其位置，由此删除了该节点。
代码实现：
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) {
return null;
}
if (key > root.val) {
root.right = deleteNode(root.right, key);
} else if (key < root.val) {
root.left = deleteNode(root.left, key);
} else {
if (root.left == null) {
return root.right;
} else if (root.right == null) {
return root.left;
} else {
TreeNode node = root.right;
// 寻找待删除节点右子树的最左节点
while (node.left != null) {
node = node.left;
}
// 将待删除节点的左子树成为其右子树的最左节点的左子树
node.left = root.left;
// 待删除节点的右子顶替其位置，节点被删除
root = root.right;
}
}
return root;
}
除了查找、插入、删除操作外，二叉查找树中还可以支持快速地查找最大节点和最小节点。此外还有一个重要特性，就是中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度是 O(n)，非常高效。因此，二叉查找树也叫二叉排序树。
4. 重复数据的存储
前面讲二叉查找树时，我们默认树中节点存储的都是数字。但在实际开发中，我们在二叉查找树中存储的，是一个对象。我们利用对象的某个字段作为键值来构建二叉查找树。那想存储的两个对象键值相同该怎么处理呢？
第一种方法
二叉查找树中每一个节点不只存储一个数据，我们通过链表或支持动态扩容的数组等数据结构，把值相同的数据都存储在同一个节点上。
第二种方法
每个节点仍然只存储一个数据。在查找插入位置的过程中，如果碰到一个节点的值，与要插入数据的值相同，我们就将这个要插入的数据放到这个节点的右子树，也就是把这个新插入的数据当作大于这个节点的值来处理。
当要查找数据的时候，遇到值相同的节点，我们并不停止查找操作，而是继续在右子树中查找，直到遇到叶子节点，才停止。这样就可以把键值等于要查找值的所有节点都找出来。
对于删除操作，我们也需要先查找到每个要删除的节点，然后再按上面讲的删除操作的方法，依次删除。
5. 时间复杂度分析
实际上，二叉查找树的形态各式各样。在下图中，对同一组数据构造了三种二叉查找树。它们的查找、插入、删除操作的执行效率都是不一样的。图中第一种二叉查找树，根节点的左右子树极度不平衡，已经退化成了链表，所以二叉查找树的最坏情况时间复杂度就是 O(n)。
我们现在来分析一个最理想的情况，二叉查找树是一棵完全二叉树（或满二叉树）。此时，插入、删除、查找的时间复杂度其实都跟树的高度成正比，也就是 O(height)。因此问题就转变成了如何求一棵包含 n 个节点的完全二叉树的高度？
分析树的高度
树的高度就等于最大层数减一，为了方便计算，我们转换成层来表示。包含 n 个节点的完全二叉树中，第一层包含 1 个节点，第二层包含 2 个节点，依次类推，下面一层节点个数是上一层的 2 倍，第 K 层包含的节点个数就是 2(K-1)。不过对于完全二叉树来说，最后一层包含的节点个数在 1 个到 **2(L-1)** 个之间（我们假设最大层数是 L）。如果我们把每一层的节点个数加起来就是总的节点个数 n。也就是说，如果节点的个数是 n，那么 n 满足这样一个关系：
n >= 1+2+4+8+...+2^(L-2)+1
n <= 1+2+4+8+...+2^(L-2)+2^(L-1)
借助等比数列的求和公式，计算得出 L 的范围是 [log2(n+1), log2n+1]。因此，完全二叉树的层数小于等于 log2n+1，也就是说，完全二叉树的高度小于等于 log2n。所以插入、删除、查找操作的平均时间复杂度就是 O(logn)。
6. 相比散列表的优势
散列表的插入、删除、查找操作的时间复杂度可以做到常量级的 O(1)，非常高效。而二叉查找树在比较平衡的情况下，插入、删除、查找操作时间复杂度才是 O(logn)，相对散列表，好像并没有什么优势，那我们为什么还要用二叉查找树呢？原因有以下几个：
- 散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序。而对于二叉查找树来说，我们只需要中序遍历，就可以在 O(n) 的时间复杂度内，输出有序的数据序列。
- 散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定，尽管二叉查找树的性能不稳定，但是在工程中，我们最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在 O(logn)。
- 笼统地来说，尽管散列表的查找等操作的时间复杂度是常量级的，但因为哈希冲突的存在，这个常量不一定比 logn 小。加上哈希函数的耗时，也不一定就比平衡二叉查找树的效率高。
- 散列表的构造比二叉查找树要复杂，需要考虑的东西很多。比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一个问题。
- 为了避免过多的散列冲突，散列表装载因子不能太大，特别是基于开放寻址法解决冲突的散列表，不然会浪费一定的存储空间。
平衡二叉查找树
上面讲了，二叉查找树支持快速插入、删除、查找操作，各个操作的时间复杂度跟树的高度成正比，理想情况下的时间复杂度是 O(logn)。但二叉查找树在频繁的动态更新过程中可能会出现树的高度远大于 log2n 的情况，从而导致各个操作的效率下降。极端情况下甚至会退化为链表，时间复杂度会退化到 O(n)。要解决这个复杂度退化的问题，我们就需要设计一种平衡二叉查找树。
平衡二叉树的严格定义是这样的：二叉树中任意一个节点的左右子树的高度相差不能大于 1。
平衡二叉查找树不仅满足上面平衡二叉树的定义，还满足二叉查找树的特点。最先被发明的平衡二叉查找树是AVL 树，它严格符合平衡二叉查找树的定义，即任何节点的左右子树高度相差不超过 1，是一种高度平衡的二叉查找树。但是很多平衡二叉查找树其实并没有严格符合这个定义，比如红黑树，它从根节点到各个叶子节点的最长路径，有可能会比最短路径大一倍。
我们学习数据结构和算法是为了应用到实际的开发中的，所以，我们没必要去死抠定义。对于平衡二叉查找树这个概念，我们要从这个数据结构的由来，去理解“平衡”的意思。发明平衡二叉查找树这类数据结构的初衷是为了解决二叉查找树在频繁插入、删除等动态更新的情况下，出现时间复杂度退化的问题。
所以，平衡二叉查找树中“平衡”的意思就是让整棵树左右看起来比较对称，不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。所以，只要平衡二叉查找树的高度不比 log2n 大很多，尽管并不严格符合平衡二叉查找树的定义，但它仍是一个合格的平衡二叉查找树。
若有收获，就点个赞吧
0 人点赞
