第52章 完全二叉树和二叉排序树

完全二叉树和二叉排序树是两种具有特殊性质的二叉树，在数据存储和查找领域应用广泛。完全二叉树因其结构规整，适合高效的数组存储和层次遍历；二叉排序树则通过定义节点间的有序关系，支持高效的动态查找、插入和删除操作。

52.1 完全二叉树

52.1.1 定义与结构特性

完全二叉树是一种特殊的二叉树，其结构满足： 除最后一层外，其余各层的节点数均达到最大值，即第$i$层有$2^{i-1}$个节点，$i ≥ 1$。 最后一层的节点从左到右连续排列，且不存在右边的节点无左兄弟的情况（即若最后一层有缺失节点，缺失的节点只能在右侧）。

示例： 深度为$3$的完全二叉树：第$1$层$1$个节点，第$2$层$2$个节点，第$3$层最多$4$个节点（若最后一层有$3$个节点，则必须是左起前$3$个）。 非完全二叉树：最后一层的节点不连续（如第$3$层有节点但中间存在空缺），或非最后一层的节点数未达最大值。

52.1.2 性质

节点编号特性：若对完全二叉树的节点按层次顺序（从根节点开始，自上至下、自左至右）编号为$1,2,...,n$，则对任意编号为$i$的节点。

• 若$i>1$，则其父节点编号为$i/2$。
• 若$2i ≤ n$，则其左子节点编号为$2i$。
• 若$2i+1 ≤ n$，则其右子节点编号为$2i+1$。

叶子节点位置：深度为$h$的完全二叉树，叶子节点只可能在第$h$层或第$h-1$层。

节点总数与深度关系：若完全二叉树有$n$个节点，深度为$h$，则

叶子节点与非叶子节点数量：

• 若 $n$ 为偶数，叶子节点数为 $n/2$，非叶子节点数为 $n/2$；
• 若 $n$ 为奇数，叶子节点数为 $(n+1)/2$，非叶子节点数为 $(n-1)/2$。

52.1.3 存储方式

完全二叉树的节点编号具有规律性，因此最适合用数组存储，无需额外存储指针，节省空间： 数组下标从$1$开始（与节点编号对应），下标$i$存储编号为$i$的节点数据。 根节点存储在下标$1$，左子节点在$2i$，右子节点在$2i+1$，父节点在$i/2$。

#define MAX_SIZE 100
//完全二叉树的数组存储
typedef struct{
int data[MAX_SIZE];//存储节点数据(下标1开始)
int n;//节点总数
} CompleteBinaryTree;

52.1.4 构造与遍历

构造：按层次顺序将节点数据填入数组即可，无需手动维护父子关系（通过编号规则自动确定）。

//初始化完全二叉树
void initCompleteBT(CompleteBinaryTree &tree, int arr[], int size){
tree.n = size;
for (int i=0;i<size;i++){
tree.data[i+1] = arr[i];//下标1对应第一个元素
}
}

遍历：支持二叉树的所有遍历方式（前序、中序、后序、层次），其中层次遍历可直接按数组顺序访问：

//层次遍历(按数组顺序输出)
void levelOrder (CompleteBinaryTree &tree) {
for (int i=1;i<=tree.n;i++){
printf("%d", tree.data[i]);
}
}

52.2 二叉排序树

52.2.1 定义与有序性

二叉排序树(Binary SearchTree,BST)又称二叉查找树，是一种满足以下有序性的二叉树：

1. 若左子树不为空，则左子树上所有节点的关键字均小于根节点的关键字。
2. 若右子树不为空，则右子树上所有节点的关键字均大于根节点的关键字。
3. 左、右子树本身也分别是二叉排序树（递归定义）。

特性：中序遍历二叉排序树可得到一个严格递增的关键字序列。 示例：根节点为$5$，左子树节点均小于$5$（如$3、2、4$），右子树节点均大于$5$（如$7、6、8$），中序遍历结果为$2,3,4,5,6,7,8$。

52.2.2 节点结构

二叉排序树通常采用二叉链表存储，每个节点包含数据、左子树指针和右子树指针：

//二叉排序树节点
typedef struct BSTNode {
int key;//关键字(用于比较)
struct BSTNode *left;//左子树
struct BSTNode *right;//右子树
//构造函数(C++)
BSTNode (int k): key (k), left (NULL), right (NULL) 
} BSTNode, *BSTree;

52.2.3 核心操作

52.2.3.1 查找

根据二叉排序树的有序性，查找过程类似二分查找：

1. 若树为空，查找失败。
2. 若目标值等于根节点关键字，查找成功。
3. 若目标值小于根节点关键字，递归查找左子树。
4. 若目标值大于根节点关键字，递归查找右子树。

//查找关键字为key的节点,返回节点指针(非递归实现,效率更高)
BSTNode* search (BSTree root, int key) {
while (root != NULL) {
if (root->key == key){
return root;//找到节点
} else if(key<root->key){
root=root->left;//向左子树查找
}else{
root=root->right;//向右子树查找
}
}
return NULL;//查找失败
}

52.2.3.2 插入

插入操作需保持二叉排序树的有序性，步骤如下：

1. 若树为空，直接创建新节点作为根节点。
2. 若目标值小于当前节点关键字，递归插入左子树；若左子树为空，则新节点作为左孩子。
3. 若目标值大于当前节点关键字，递归插入右子树；若右子树为空，则新节点作为右孩子。
4. 若目标值等于当前关键字，通常不插入（避免重复）。

//插入关键字key,返回新的根节点
BSTNode* insert(BSTree root, int key) {
if (root == NULL){
return new BSTNode (key);//空树,创建新节点
}
if (key <root->key){
root->left=insert(root->left,key);//插入左子树
} else if (key >root->key){
root->right=insert(root->right,key);//插入右子树
}
//相等时不插入
return root;
}

52.2.3.3 删除

删除操作需根据节点的子树情况调整，保证删除后仍有序，分三种情况：

1. 叶子节点（无左右子树）：直接删除，父指针置空。
2. 只有左/右单棵子树：删除后将子树接到父节点对应位置。
3. 同时存在左右子树：找到中序后继（右子树最小节点）或中序前驱（左子树最大节点），替换关键字后删除后继节点。

BSTNode* findMin (BSTree root){
//查找最小节点(用于找中序后继)
while (root->left!= NULL){
root = root->left;
}
return root;
}

//删除关键字为key的节点,返回新的根节点
BSTNode* remove (BSTree root, int key) {
if (root == NULL) return NULL;//树为空,无需删除
if (key<root->key){
root->left= remove (root->left,key);//左子树删除
} else if(key >root->key){
root->right= remove (root->right,key);//右子树删除
}else{
//找到待删除节点
if(root->left== NULL){//只有右子树或无子树
BSTNode *temp= root->right;
delete root;
return temp;
}else if(root->right==NULL){//只有左子树
BSTNode *temp= root->left;
delete root;
return temp;
}
//同时有左右子树,取右子树最小节点(中序后继)
BSTNode *temp = findMin (root->right);
root->key=temp->key;//替换关键字
root->right =remove (root->right,temp->key);//删除后继
}
return root;
}

52.2.4 性能分析

二叉排序树的查找、插入、删除操作的时间复杂度取决于树的高度：

1. 理想平衡树：树高为$\log n$，操作复杂度$O(\log n)$；
2. 最坏斜树（插入有序序列$1,2,3,4,5$）：退化为单链表，复杂度$O(n)$。

为规避最坏性能，工程中使用AVL树、红黑树等平衡二叉排序树，通过旋转维持平衡。

52.3 完全二叉树与二叉排序树的对比

52.4 应用场景

完全二叉树应用

1. 堆结构：堆是特殊完全二叉树，用于实现最大堆、最小堆、优先队列。
2. 数组静态二叉树：节点数量固定场景，利用下标快速访问父子节点。

二叉排序树应用

1. 动态查找表：通讯录、字典，支持实时增删查。
2. 数据库索引：B树、B+树的底层基础结构。
3. 排序辅助：中序遍历直接得到有序序列。

52.5 注意事项

完全二叉树数组存储

1. 数组下标推荐从$1$开始，简化$2i$、$2i+1$父子下标计算；
2. 需提前定义数组最大容量，防止下标越界。

二叉排序树实现

1. 连续有序数据插入会退化为斜树，性能暴跌；
2. 删除节点需区分三类情况，左右子树共存时必须处理中序后继/前驱；
3. 自定义数据类型存储关键字时，必须重载大小比较运算符。

遍历要点

1. 完全二叉树层次遍历直接遍历数组，效率最高；
2. 二叉排序核心特性为中序升序，是做题、业务开发重点。

练习题

1. 在按层次编号（从 1 开始）的完全二叉树中，编号为 $i$ 的节点，其左子节点的编号是（ ） A. $i+1$ B. $2i$ C. $2i+1$ D. $\lfloor i/2 \rfloor$

   答案与解析

   答案：B

   解析：完全二叉树采用数组（下标从 1 开始）存储时，节点 $i$ 的左子节点编号为 $2i$，右子节点为 $2i+1$，父节点为 $\lfloor i/2 \rfloor$。这正是完全二叉树能高效用数组存储的原因。

2. 对一棵二叉排序树（BST）进行中序遍历，得到的序列特征是（ ） A. 严格递减 B. 严格递增 C. 无序 D. 先递增后递减

   答案与解析

   答案：B

   解析：BST 满足"左子树所有值 < 根 < 右子树所有值"且递归成立。中序遍历顺序为"左—根—右"，因此会先访问最小值、最后访问最大值，得到严格递增序列。这一性质常用于"中序遍历即得有序序列"的排序辅助。

3. 关于完全二叉树，下列说法正确的是（ ） A. 最后一层的节点可以随意缺失，不需要连续 B. 除最后一层外，其余各层节点数都达到最大值，且最后一层节点从左向右连续排列 C. 完全二叉树一定是满二叉树 D. 完全二叉树不能用于数组存储

   答案与解析

   答案：B

   解析：完全二叉树要求除最后一层外各层节点数达到最大，且最后一层节点必须从左向右连续排列（右侧不能有空缺）。满二叉树是完全二叉树的特例，但完全二叉树不一定"满"。其规整性正是数组存储的基础。

4. 在二叉排序树中依次插入已按升序排列的序列 1,2,3,4,5，最终树会退化成（ ） A. 完全二叉树 B. 满二叉树 C. 只有右子节点的单链（斜树） D. 只有左子节点的单链

   答案与解析

   答案：C

   解析：每次插入都比当前节点大，新节点都会成为右孩子，于是形成一条只有右子节点的链（右斜树），查找复杂度退化为 $O(n)$。这正是实际中需要用 AVL 树、红黑树等平衡结构的原因。