Binary Tree related algorithms

这是一个二叉树相关的算法项目，implements by Java.

二叉树介绍

1. 定义

二叉树（Binary Tree）是一种有限层次的数据结构，其中每个节点最多只能有两个子节点。这两个子节点通常被称为左子节点（left child）和右子节点（right child）。二叉树的每个节点可以是一个独立的子树。

2. 基本概念（节点、子树、根节点、叶子节点、深度、高度等）

节点（Node）： 二叉树中的每个元素称为节点，它包含数据和指向其子节点的引用。

子树（Subtree）： 节点的子节点和其后代节点组成的集合被称为子树。

根节点（Root Node）： 没有父节点的节点称为根节点，整棵树由根节点开始。

叶子节点（Leaf Node）： 没有子节点的节点被称为叶子节点。

深度（Depth）： 节点的深度是从根节点到该节点的唯一路径上的边的数量，根节点的深度为0。

高度（Height）： 节点的高度是从该节点到其最远叶子节点的最长路径上的边的数量。叶子节点的高度为0。

3. 类型（普通二叉树、完全二叉树、满二叉树、平衡二叉树等）

普通二叉树： 任意的二叉树，没有特殊约束。

完全二叉树（Complete Binary Tree）： 除了最后一层之外，其他每一层的节点数都达到最大值，且最后一层的节点都连续集中在左侧。

满二叉树（Full Binary Tree）： 每一层的节点数都达到最大值，即所有层的节点数均为2的幂次方减一。

平衡二叉树（Balanced Binary Tree）： 对于树中的每个节点，其左子树和右子树的高度差的绝对值不超过1。这样的树可以保证较好的查询性能。

4. 应用场景

搜索算法： 二叉搜索树（BST）可以实现高效的搜索、插入和删除操作。

排序算法： 二叉树可以用于实现诸如归并排序、堆排序等排序算法。

优先队列： 二叉堆是一种特殊的二叉树，可以用于实现优先队列。

文件系统和数据库： B树、B+树和R树等多路平衡查找树是二叉树的扩展，广泛应用于文件系统和数据库的索引结构中，以提高查询效率。

编译器： 抽象语法树（AST）是编译器中的一种关键数据结构，用于表示源代码的语法结构。

表达式求值： 二叉树可以用于表示和求解算术表达式。

数据压缩： 霍夫曼树（Huffman Tree）是一种带权路径最短的二叉树，用于实现数据的无损压缩。

网络路由： 二叉字典树（Binary Trie）可以用于实现高效的IP路由查找。

图形学： kd树（k-dimensional tree）是一种特殊的二叉搜索树，用于高维空间的搜索问题，如最近邻搜索、范围查询等。

二叉树遍历

二叉树遍历是访问二叉树中所有节点的过程。根据访问节点的顺序，二叉树遍历可以分为前序遍历、中序遍历、后序遍历和层次遍历。这些遍历方法可以通过递归或非递归的方式实现。

1. 前序遍历

前序遍历遵循以下访问顺序：

a. 访问根节点。
b. 前序遍历左子树。
c. 前序遍历右子树。

2. 中序遍历

中序遍历遵循以下访问顺序：

a. 中序遍历左子树。
b. 访问根节点。
c. 中序遍历右子树。

3. 后序遍历

后序遍历遵循以下访问顺序：

a. 后序遍历左子树。
b. 后序遍历右子树。
c. 访问根节点。

4. 层次遍历

层次遍历是按照树的层次从上到下访问每一层的节点，同一层中，从左到右的顺序访问节点。

二叉树相关算法

a. 插入

b. 删除

c. 查找

d. 深度/高度计算

e. 二叉树的镜像

f. 最近公共祖先

g. 判断平衡二叉树

h. 从前序与中序遍历构造二叉树

i. 从后序与中序遍历构造二叉树

特殊类型二叉树及其算法

二叉搜索树（BST）

定义

BST（Binary Search Tree，二叉搜索树）是一种特殊的二叉树数据结构，它具有以下性质：

1. 每个节点的值都大于或等于其左子树中所有节点的值。
2. 每个节点的值都小于或等于其右子树中所有节点的值。
3. 递归地，每个子树也必须满足以上两个条件。

这些性质使得二叉搜索树具有一些有趣的特点，例如：

• 搜索特定值的时间复杂度为 O(log n)，其中 n 是树中节点的数量。这是因为在每次比较时，我们都可以排除掉一半的候选节点。
• 对于中序遍历（左子树 - 根节点 - 右子树），输出的值将按照升序排列。

BST 常用于实现搜索算法、动态排序和范围查询等操作，因为它可以在较短的时间复杂度内完成这些操作。例如，以下操作可以在 O(log n) 的时间内完成：

• 查找：通过递归或迭代方式比较节点值来搜索特定值。
• 插入：在找到适当的位置之后，插入新值作为叶子节点。
• 删除：删除节点时，需要考虑三种情况。1) 被删除节点没有子节点；2) 被删除节点有一个子节点；3) 被删除节点有两个子节点。对于第三种情况，可以寻找被删除节点的前驱（左子树的最大值）或后继（右子树的最小值）来替换被删除节点。

二叉搜索树（BST）的性能取决于其高度：

1. 最佳情况：在最佳情况下，BST 是完全平衡的，也就是说，每个节点的左子树和右子树具有相同数量的节点（或最多相差一个节点）。在这种情况下，BST 的高度是 O(log n)，其中 n 是树中节点的数量。这意味着搜索、插入和删除操作都可以在 O(log n) 的时间内完成。完全平衡的 BST 通常是采用已排序好的数组构建。

2. 最坏情况：在最坏情况下，BST 变得非常不平衡，类似于一个链表。这种情况通常发生在插入已排序或逆序数组时。在这种情况下，BST 的高度将成为 O(n)，其中 n 是树中节点的数量。这意味着搜索、插入和删除操作的时间复杂度都将变为 O(n)，性能明显下降。

为了解决不平衡 BST 带来的性能问题，可以使用一些特殊类型的 BST，例如 AVL 树或红黑树。这些树在执行插入和删除操作时会自动进行调整以保持平衡，从而确保性能始终接近于最佳情况。

平衡二叉搜索树（AVL树、红黑树等）

TODO