二叉树与高级排序算法详解

### 二叉树与高级排序算法详解 #### 1. 二叉树基础 在二叉树的操作中，删除节点是一项重要操作。以下代码展示了删除节点的操作逻辑： ```java //R is pointing to the in-order successor of T; //P is its parent left(R) = left(T) left(P) = right(R) right(R) = right(T) return R } //end deleteNode ``` 假设以指向节点 L 的指针作为参数调用 `deleteNode` 函数，该函数会删除 L 并返回指向新树的指针。由于 L 是 H 的右子树，我们可以将 H 的右子树设置为指向这棵新树的根节点 N。 #### 2. 用数组表示二叉树 ##### 2.1 完全二叉树 完全二叉树是指每个非叶子节点都有两个非空子树，且所有叶子节点都在同一层的二叉树。对于高度为 n 的完全二叉树，节点数量为 2n - 1。 我们可以按层对节点进行编号，从根节点开始，每层从左到右依次编号。若节点编号为 n，其左子树编号为 2n，右子树编号为 2n + 1。 若将节点存储在数组 T[1..7] 中，则有以下规则： - T[1] 是根节点。 - 若 2i <= 7，T[i] 的左子树为 T[2i]，否则为 null。 - 若 2i + 1 <= 7，T[i] 的右子树为 T[2i + 1]，否则为 null。 - T[i] 的父节点为 T[i/2]（整数除法）。 基于这些规则，数组可以表示完全二叉树，给定数组就能轻松构建其代表的二叉树。 ##### 2.2 几乎完全二叉树 若数组元素数量为 2n – 1，则表示完全二叉树；若元素数量为其他值，则表示几乎完全二叉树。 几乎完全二叉树的特点如下： - 除最低层外，所有层都完全填满。 - 最低层的节点（均为叶子节点）尽可能靠左。 若按上述方式编号，所有叶子节点的编号为从 n/2 + 1 到 n 的连续数字，最后一个非叶子节点编号为 n/2。 例如，对于有十个节点的树，其叶子节点编号从 6 到 10。若 H 是 B 的右子树而非左子树，该树就不是“几乎完全”的，因为最低层的叶子节点没有“尽可能靠左”。 一般来说，若树由数组 T[1..n] 表示，则有： - T[1] 是根节点。 - 若 2i <= n，T[i] 的左子树为 T[2i]，否则为 null。 - 若 2i + 1 <= n，T[i] 的右子树为 T[2i + 1]，否则为 null。 - T[i] 的父节点为 T[i/2]（整数除法）。 几乎完全二叉树没有“空洞”，只能在最后一个节点之后添加新节点。 以下是对几乎完全二叉树进行中序遍历的代码： ```java public static void inOrder(int h, int n) { if (h <= n) { inOrder(h * 2, n); visit(h); //or visit(T[h]), if you wish inOrder(h * 2 + 1, n); } } //end inOrder ``` 我们也可以编写类似的函数进行前序和后序遍历。 #### 3. 二叉树相关练习 以下是一些与二叉树相关的练习： 1. 编写构建二叉树所需的声明，并编写创建空树的代码。 2. 编写函数返回给定节点 x 的中序、前序和后序后继节点，并使用这些函数进行二叉树的中序、前序和后序遍历。 3. 假设树存储在数组中，完成练习 2。 4. 编写函数删除二叉搜索树中的最小节点，并返回重构后树的根指针。 5. 编写函数删除二叉搜索树中的最大节点，并返回重构后树的根指针。 6. 编写函数删除二叉搜索树的根节点，并分别用其 中序后继和中序前驱替换根节点，返回重构后树的根指针。 7. 绘制一个五节点的非退化二叉树，使其前序和层序遍历结果相同。 8. 编写函数返回二叉树的宽度，即任意层的最大节点数。 9. 判断给定序列是否可能是在二叉搜索树中搜索数字 36 时检查的值序列，若不能，说明原因。 10. 按给定顺序插入键值，绘制二叉搜索树（BST），找出几乎完全的 BST，列出能生成该树的键值顺序，并编写递归函数按后序打印存储在一维数组中的几乎完全树的整数。 11. 计算二叉树中附加“外部”节点的数量，证明外部节点层和与内部节点层和的关系 E – I = 2n，并编写递归和非递归函数返回内部路径长度 I。 12. 根据给定的中序和后序遍历结果绘制二叉树。 13. 根据给定的前序和中序遍历结果绘制二叉树。 14. 绘制两棵不同的二叉树，使其前序和后序遍历结果相同。 15. 编写递归函数，使用前序、中序和后序遍历在二叉树中搜索给定键值，若找到返回包含该键值的节点，否则返回 null。 16. 将给定整数存储在数组 bst[1..15] 中，使其表示完全二叉搜索树。 17. 编写高效函数，返回二叉搜索树中大于给定键值的最小数字，若不存在则返回 -1。 18. 编写程序，输入 Java 程序，输出编号后的程序，并列出所有用户标识符及其出现的行号，排除 Java 保留字、字符串和注释中的单词。 #### 4. 高级排序算法 - 堆排序 ##### 4.1 堆的定义 堆排序将数组元素视为几乎完全二叉树。堆是一种几乎完全二叉树，根节点的值大于或等于左右子节点的值，且左右子树也是堆。根节点值最大的堆称为最大堆，根节点值最小的堆称为最小堆。 ##### 4.2 二叉树转换为最大堆 以下是将二叉树转换为最大堆的步骤： 1. 所有叶子节点都是堆，因为它们没有子节点。 2. 从最后一个非叶子节点开始，将以该节点为根的子树转换为最大堆。若节点值大于其子节点，则无需操作；否则，找到较大子节点并交换。 3. 依次处理每个非叶子节点，直到根节点。 例如，对于数组 `[37, 25, 43, 65, 48, 84, 73, 18, 79, 56, 69, 32]`，转换