用C语言实现的——一个完整的AVL树的交互式系统

一、知识要点

AVL树（Adelson-Velsky and Landis Tree）是一种自平衡二叉搜索树，由俄罗斯计算机科学家 Georgy Adelson-Velsky 和 Evgenii Landis 在 1962 年提出。它具备以下特点：

AVL树的性质

二叉搜索树（排序树）性质：每个节点的左子树只包含小于该节点的键值，右子树只包含大于该节点的键值，且左、右子树也分别为二叉搜索树。

高度平衡：对于任意节点，其左子树和右子树的高度差（平衡因子）的绝对值不超过1。这一性质确保了AVL树的高效性。 

AVL树的基本操作及时间复杂度

查找：
        过程：类似于普通二叉搜索树（排序树）的查找操作，从根节点开始，根据要查找的键值与当前节点的键值比较，决定向左子树还是右子树继续查找。

        时间复杂度：在最坏情况下为 O(logn) ，因为 AVL 树是平衡的，其高度为 O(logn) ，查找操作只需从根节点到目标节点的路径上的节点进行比较。

插入：
        过程：首先按照二叉搜索树的插入方式将新节点插入到合适的位置，然后从插入点向上检查各祖先节点的平衡因子，若发现不平衡，则在最小的非平衡树内进行旋转操作（左旋、右旋或双旋）来恢复平衡。

        时间复杂度：查找插入位置需要 O(logn) 时间，旋转操作的时间复杂度为 O(1) ，因此插入操作的总时间复杂度为 O(logn) 。

删除：
        过程：先找到要删除的节点。
       ①若该节点有两棵非空子树，则用其前驱或后继节点代替它；然后调整树的结构以保持二叉搜索树性质；最后从删除点向上检查各祖先节点的平衡因子，若不平衡则进行相应的旋转操作来恢复平衡。
        ②若要删除的节点是叶子节点（没有子节点），可以直接删除，不会对树的结构造成影响，只需更新其父节点的对应指针为NULL。
        ③若要删除的节点只有一个子节点（左子节点或右子节点），则可以用该子节点直接替换要删除的节点。即，将该节点的父节点的对应指针指向其子节点，并更新相关指针和平衡因子。
  
        时间复杂度：查找要删除的节点需要 O(logn) 时间，调整树结构和旋转操作的时间复杂度均为 O(logn) ，所以删除操作的总时间复杂度也为 O(logn) 。


AVL树的优缺点：

优点：

查找、插入和删除操作的时间复杂度在最坏情况下均为 O(logn)，这使得 AVL 树在需要频繁进行这些操作的场景下具有较高的效率。
自平衡特性保证了树的高度始终处于可控范围内，避免了树的性能退化。

缺点：

由于需要维护高度平衡，插入和删除操作时可能会频繁进行旋转调整，这会增加一定的额外开销。
相较于红黑树等其他平衡二叉搜索树，AVL 树的插入和删除效率可能稍低，因为 AVL 树的平衡条件更严格，导致旋转操作更频繁。

二、代码分析

1.AVL树结构体定义AVLNode

key：节点存储的键值，是节点的核心数据。

left和right：分别是节点的左孩子节点和右孩子节点的指针，用于构建树的结构，体现节点之间的逻辑关系。

height：节点的高度，用于计算平衡因子，维持AVL树的平衡。

parent：父节点指针，方便从子节点向上追溯父节点，新增此指针是为了便于实现查询节点前驱和后继的功能。

2.创建树节点函数createNode

①内存分配

使用 malloc 动态分配内存空间，大小为 AVLNode 结构体的字节长度。如果分配失败（返回 NULL），函数会立即返回 NULL，表示创建节点失败。
 

②初始化节点成员

key：赋值为传入的参数 key，表示节点存储的数据。

left 和 right：初始化为 NULL，表示新节点没有左右子节点。

height：初始化为 1，表示节点高度（新节点高度为1）。

parent：初始化为 NULL，表示新节点没有父节点。

最后返回节点指针

3. 获取AVL高度函数getHeight

①空节点检查

如果传入的节点指针为 NULL，说明该位置没有节点，按照AVL树的定义，空树的高度为0。因此，函数返回 0。

②返回节点高度

如果节点不为空，直接返回该节点的 height 成员值。height 表示节点在树中的高度，用于计算平衡因子和维护树的平衡。
 

③ 在完整程序中的作用

getHeight 函数是 AVL 树实现中的核心辅助函数之一，主要在以下场景中发挥作用：
插入操作：在插入新节点后，需要更新祖先节点的高度，并检查平衡因子以决定是否需要旋转。
删除操作：在删除节点后，同样需要更新祖先节点的高度，并检查平衡因子以恢复平衡。
平衡因子计算：getBalanceFactor 函数依赖 getHeight 来计算每个节点的平衡因子：

4. 更新节点高度函数updateHeight

①空节点检查

首先检查传入的节点是否为空。如果节点为空，函数直接返回，不执行任何操作。这是为了防止对空指针进行操作，避免程序崩溃。

②更新节点高度

如果节点不为空，则更新该节点的高度。
具体逻辑如下：

使用 getHeight 函数分别获取左子节点和右子节点的高度。
比较左右子节点的高度，取较大值。
将节点的高度更新为该较大值加1。

 背后的逻辑：

高度定义：节点的高度是该节点到最远叶子节点的路径上的边数。例如：

1. 叶子节点的高度为1（因为它到自己的路径有0条边，但根据定义，叶子节点的高度初始化为1）。

2. 父节点的高度为其左右子节点高度的最大值加1。

平衡维护：在AVL树中，每个节点的高度信息用于计算平衡因子（左子树高度减去右子树高度）。如果平衡因子的绝对值超过1，树就失去平衡，需要进行旋转操作来恢复平衡。

5. 计算平衡因子函数getBalanceFactor

①空节点检查：

如果传入的节点指针为 NULL，说明该位置没有节点，直接返回 0。空节点的平衡因子定义为 0，因为它们不会影响树的平衡。

②计算平衡因子：

如果节点不为空，函数返回该节点左子树高度减去右子树高度的值。这个值就是平衡因子。

背后的逻辑

a. 平衡因子的定义：平衡因子是AVL树的核心概念。它用于衡量节点左右子树的高度差异。根据AVL树的性质，平衡因子的绝对值不能超过1。如果超过1，树就会失去平衡，需要进行旋转操作来恢复平衡。

b. 旋转类型的判断：平衡因子的值不仅帮助判断树是否平衡，还可以指示需要进行哪种类型的旋转操作来恢复平衡：
平衡因子 > 1：左子树比右子树高，可能需要右旋或先左旋后右旋。
平衡因子 < -1：右子树比左子树高，可能需要左旋或先右旋后左旋。

6. 右旋操作rightRotate

①变量声明与初始化：

x 是 y 的左子节点。
T2 是 x 的右子节点。
 

②执行旋转：

将 x 的右子节点设置为 y。
将 y 的左子节点设置为 T2。
 

③更新父指针：

更新 y 的父指针为 x。

如果 T2 不为空，更新 T2 的父指针为 y。
 

④更新高度：

更新 y 和 x 的高度。旋转操作改变了树的结构，因此需要重新计算相关节点的高度。
 

⑤返回新的根节点：

返回 x 作为新的子树根节点。旋转后，x 成为原节点 y 的父节点，并且是新的子树根。

7. 左旋操作leftRotate

①变量声明与初始化

y 是 x 的右子节点。
T2 是 y 的左子节点。

②执行旋转：

将 y 的左子节点设置为 x。
将 x 的右子节点设置为 T2。
 

③更新父指针：

更新 x 的父指针为 y。
如果 T2 不为空，更新 T2 的父指针为 x。

④更新高度：

 更新 x 和 y 的高度。旋转操作改变了树的结构，因此需要重新计算相关节点的高度。
 

⑤返回新的根节点：

返回 y 作为新的子树根节点。旋转后，y 成为原节点 x 的父节点，并且是新的子树根。

8.查询函数insert

①执行标准BST插入

如果当前节点为空：创建并返回一个新节点。

如果输入值小于当前节点的键值：递归插入到左子树，并更新左子节点的父指针。

如果输入值大于当前节点的键值：递归插入到右子树，并更新右子节点的父指针。

如果键值等于当前节点的键值：不允许插入重复值，直接返回当前节点。

②更新高度

调用之前定义的 updateHeight 函数更新当前节点的高度，以反映树结构的变化。

③ 获取平衡因子

计算当前节点的平衡因子，用于判断树是否平衡。

④判断平衡情况并进行旋转

如果平衡因子大于1且新插入的输入键值小于左子节点的键值，说明是左左情况，需要进行右旋操作。

执行右旋操作后，更新新根节点的父指针，并返回新根节点。

如果平衡因子小于-1且新插入的键值大于右子节点的键值，说明是右右情况，需要进行左旋操作。

执行左旋操作后，更新新根节点的父指针，并返回新根节点。

如果平衡因子大于1且新插入的键值大于左子节点的键值，说明是左右情况，需要先对左子树进行左旋，再对当前节点进行右旋。

执行旋转操作后，更新新根节点的父指针，并返回新根节点。

 

如果平衡因子小于-1且新插入的键值小于右子节点的键值，说明是右左情况，需要先对右子树进行右旋，再对当前节点进行左旋。

执行旋转操作后，更新新根节点的父指针，并返回新根节点。

 

9. 查找节点search

①函数定义

参数：

root：指向AVL树根节点的指针。

key：要查找的键值。

返回值：返回指向具有指定键值的节点的指针；如果没有找到，则返回NULL。

②函数实现:

检查根节点是否为空或输入键值匹配：

如果当前节点为空（root == NULL），说明查找路径已到达树的末端，未找到目标节点，返回NULL。

如果当前节点的键值等于要查找的键值（root->key == key），返回当前节点。

递归查找左子树：

如果目标键值小于当前节点的键值，说明目标节点可能位于左子树中，递归调用search函数查找左子树。

递归查找右子树：

如果目标键值大于当前节点的键值，说明目标节点可能位于右子树中，递归调用search函数查找右子树。

10. 查找前驱节点findpredecessor

①函数定义：

 参数：

node：指向目标节点的指针。

返回值：返回指向目标节点前驱节点的指针；如果没有前驱节点，则返回NULL。

②空节点判断：

如果输入节点为空，直接返回NULL。

③情况一：节点有左子树：

如果目标节点有左子树，则其前驱节点必定是左子树中最右的节点。

初始化predecessor为节点的左孩子。

使用while循环不断向右遍历，直到找到最右节点，即为前驱节点。

④情况二：节点无左子树：

如果目标节点没有左子树，则其前驱节点必定是其祖先链中的某个节点。

初始化parent为节点的父节点。

使用while循环向上遍历祖先节点，直到找到一个节点是其父节点的右孩子的节点。

最终返回该节点的父节点，即为前驱节点。

具体示例:

      10
    /       \
   5        15
  /   \     /     \
 3   8  12  18

查找节点8的前驱：

1.初始状态：

· 目标节点是8。

·parent = node->parent：父节点是5。

2.进入循环：

• 检查 parent != NULL 和 node == parent->left：

  • parent 是5，不为空。

  • 节点8是5的右孩子，因此条件 node == parent->left 不成立。

• 循环终止。

3.返回父节点：

• 返回 parent，即节点5。

另一个示例：查找节点3的前驱

1.初始状态：

• 目标节点是3。

• parent = node->parent：父节点是5。

2.进入循环：

• 检查 parent != NULL 和 node == parent->left：

  • parent 是5，不为空。

  • 节点3是5的左孩子，条件成立。

3.更新当前节点和父节点：

• node = parent：当前节点变为5。

• parent = parent->parent：父节点变为10。

4.再次检查循环条件：

• parent != NULL：父节点是10，不为空。

• node == parent->left：节点5是10的左孩子，条件成立。

5.再次更新当前节点和父节点：

• node = parent：当前节点变为10。

• parent = parent->parent：父节点变为NULL。

6.循环终止：

• parent == NULL，循环终止。

7.返回父节点：

• 返回 parent，此时 parent 是NULL，表示节点3没有前驱节点。

11. 查找后驱节点findSuccessor

 ①函数定义和参数说明 

参数：node 是指向当前要查找后继节点的指针。

返回值：返回指向后继节点的指针；如果没有后继节点，则返回 NULL。

②空节点判断：

如果输入的节点为空，直接返回 NULL，表示没有后继节点。

③情况一：节点有右子树：

如果当前节点有右子树，则后继节点必定在右子树中，并且是右子树中最左的那个节点。

初始化 successor 为当前节点的右孩子。

使用 while 循环不断向左遍历，直到找到最左的节点，该节点即为后继节点。

⑤情况二：节点无右子树

如果当前节点没有右子树，则需要向上查找其祖先节点。

初始化 parent 为当前节点的父节点。

使用 while 循环向上遍历，直到找到一个节点是其父节点的左孩子的节点。

返回该父节点作为后继节点。

具体示例：参考前驱节点的示例，思路雷同。

12. 删除操作deleteNode

①函数定义：

参数：

root：指向AVL树根节点的指针。

key：要删除的键值。

返回值：返回删除操作后的新的根节点指针。

②函数实现：

1.空树判断：

 如果树为空，直接返回空。

2.查找并删除节点：

键值小于当前节点键值：

如果要删除的键值小于当前节点的键值，则递归调用 deleteNode 函数删除左子树中的节点。
root->left = deleteNode(root->left, key);：递归删除左子树中的节点。递归返回后，更新当前节点的左子节点指针。
if (root->left != NULL) { root->left->parent = root; }：如果左子节点不为空，更新其父指针为当前节点。这确保了树结构的完整性。

键值大于当前节点键值：

• 如果要删除的键值大于当前节点的键值，则递归调用 deleteNode 函数删除右子树中的节点。

• root->right = deleteNode(root->right, key);：递归删除右子树中的节点。递归返回后，更新当前节点的右子节点指针。

• if (root->right != NULL) { root->right->parent = root; }：如果右子节点不为空，更新其父指针为当前节点。这确保了树结构的完整性。

 具体示例：

删除节点3：

①初始调用：

• 调用 deleteNode(root, 3)，root 指向根节点10。

②递归查找：

• 3 < 10，递归调用 deleteNode(root->left, 3)，root->left 是节点5。

• 3 < 5，递归调用 deleteNode(root->left, 3)，root->left 是节点3。

③找到目标节点：

• 现在 root 指向节点3，键值相等，进入删除逻辑。

④删除节点3：

• 节点3是叶子节点（左右子树为空），直接删除。

• 更新节点5的左子节点为 NULL。

⑤返回并更新父指针：

递归返回到节点5，检查并更新其左子节点的父指针（现在为 NULL，无需更新）。

 ⑥检查平衡并调整：

• 删除节点后，更新相关节点的高度并检查平衡因子，必要时进行旋转操作以恢复平衡。

3.删除目标节点：

第一部分：处理左子树为空的情况

if (root->left == NULL)：如果当前节点的左子树为空，说明该节点要么是叶子节点（左右子树都为空），要么只有一个右子节点。

AVLNode* temp = root->right;：将当前节点的右子节点赋值给临时变量 temp。如果当前节点是叶子节点，temp 将为 NULL。

if (temp != NULL)

{ temp->parent = root->parent; }：如果 temp 不为空（即当前节点有一个右子节点），将 temp 的父指针更新为当前节点的父节点。这样可以维护树的结构，确保右子节点正确链接到父节点。

free(root);：释放当前节点的内存。

return temp;：返回左子节点，让其替代当前节点的位置。

第二部分：处理右子树为空的情况

else if (root->right == NULL)：如果当前节点的右子树为空，说明该节点只有一个左子节点。

AVLNode* temp = root->left;：将当前节点的左子节点赋值给临时变量 temp。

if (temp != NULL) { temp->parent = root->parent; }：如果 temp 不为空，将 temp 的父指针更新为当前节点的父节点。

free(root);：释放当前节点的内存。

return temp;：返回左子节点，让其替代当前节点的位置。

具体示例：

4. 有两个子节点的情况：

①调用 findPredecessor 函数找到当前节点（root）的前驱节点。前驱节点是中序遍历中位于当前节点之前的节点，即当前节点左子树中最右的节点。

②将当前节点的键值替换为前驱节点的键值。这一步的目的是用前驱节点的值来替代当前节点的值，这样当前节点的删除操作就转化为删除前驱节点的操作。

③递归调用 deleteNode 函数来删除前驱节点。由于前驱节点是当前节点左子树中最右的节点，它要么是叶子节点，要么只有一个左子节点，因此可以直接删除。

④如果删除操作后当前节点的左子节点不为空，则更新该左子节点的父指针为当前节点。这一步确保了树的结构完整性。

具体示例：

删除节点10：

1.查找前驱节点：

• 节点10的前驱节点是其左子树中最右的节点，即节点8。

 2.替换键值：

      将节点10的键值替换为节点8的键值。此时，树结构变为：

3. 删除前驱节点：

• 递归调用 deleteNode 函数删除节点8。节点8现在是节点5的右子节点。

4. 删除操作：

• 节点8是一个叶子节点（左右子树都为空），直接删除。

• 更新节点5的右子节点为 NULL

5.更新父指针：

• 删除操作后，节点5的右子节点变为 NULL，无需更新父指针。该叶子节点都已经是NULL，还更新父亲指针指向5干啥。只要有5这个右指针指向了NULL就可以了。

6.最终树结构：

这段代码通过找到前驱节点并用其值替代当前节点的值，将删除一个有两个子节点的节点的问题转化为删除一个最多有一个子节点的节点的问题。这样可以保持AVL树的平衡特性，并确保树结构的完整性。

5.更新高度和平衡因子

逻辑：更新节点高度并计算平衡因子。

原因：删除节点改变了树结构，需重新计算高度和平衡因子以判断是否需要平衡调整。

6. 平衡调整

逻辑：如果节点左子树过高且左子树平衡或左左高，右旋恢复平衡。

原因：右旋降低左子树高度，使树重新平衡。

逻辑：左子树过高但左子树右子高，先左旋左子树，再右旋当前节点。

原因：双旋调整结构，重新分布高度，恢复平衡。

逻辑：右子树过高且右子树平衡或右右高，左旋恢复平衡。

原因：左旋降低右子树高度，平衡树。

逻辑：右子树过高但右子树左子高，先右旋右子树，再左旋当前节点。

原因：双旋调整结构，重新分布高度，恢复平衡。

13. 树形展示操作printTree

参数：

root：指向 AVL 树的根节点的指针，用于指定要打印的树的起始节点。

level：表示当前节点所在的层次，用于控制打印时的缩进，以体现树的层次结构。

1.递归终止条件：

如果当前节点为空（root == NULL），则直接返回，不进行任何操作。
 

2.打印右子树：

递归调用 printTree 函数，传入当前节点的右子节点和 level + 1，表示进入下一层级。

3.打印当前节点：

使用 for 循环输出 level 个空格，实现当前节点的缩进；然后输出当前节点的键值（root->key）。

4.打印左子树：

递归调用 printTree 函数，传入当前节点的左子节点和 level + 1，表示进入下一层级。

具体分析：

 调用过程：

1.初始调用：printTree(root, 0)，root 是节点 3。

• level = 0，所以没有缩进。

• 先递归调用 printTree(root->right, 1)（打印右子树）。

2.打印右子树（节点 5）：

• level = 1，循环打印 1 次 " "（4 个空格）。

• 再递归调用 printTree(root->right, 2)（节点 5 的右子树是空，直接返回）。

• 打印节点 5 的值。

• 再递归调用 printTree(root->left, 2)（节点 5 的左子树是空，直接返回）。

3.返回到节点 3：

• 打印节点 3 的值。

4.打印左子树（节点 1）：

• level = 1，循环打印 1 次 " "（4 个空格）。

• 再递归调用 printTree(root->right, 2)（节点 1 的右子树是空，直接返回）。

• 打印节点 1 的值。

• 再递归调用 printTree(root->left, 2)（节点 1 的左子树是空，直接返回）。

输出结果：

为什么这样能形成树形？

1.右子树优先打印：
右子树的内容先被打印到最右侧，形成树的“右分支”。

2.缩进控制层次：
每层增加 4 个空格，确保子节点在横向（水平方向）上比父节点更向右。

3.根节点居中：
根节点在右子树和左子树之间打印，形成树的“中心”。

4.左子树最后打印：
左子树的内容出现在根节点的下方和左侧，形成树的“左分支”。

空格的作用：

空格是横向添加的：printf("    "); 每次添加 4 个空格，拉开奖项之间的水平距离。
没有竖向空格：节点之间没有额外的竖向空格，所有节点都在同一竖直线上，只是通过缩进体现层次。

优点和缺点
优点：
直观展示层次：通过缩进清晰地展示了树的层次结构。
简单易懂：递归逻辑清晰，易于实现和理解。
适用于小型树：对于小型树，输出非常直观。
缺点：
不适用于大型树：对于大型树，输出可能过于宽广，超出屏幕范围。
无法展示连接线：节点之间没有连线，仅通过缩进体现层次，不够直观。
固定缩进：缩进量固定为 4 个空格，无法动态调整。

14. 以层次结构展示操作printLeveOeder

参数：

root：指向 AVL 树的根节点的指针，用于指定要打印的树的起始节点。
 

逻辑流程：

1.初始检查：

• 如果树为空（root == NULL），则直接输出“Tree is empty”并返回。

2.初始化队列：

• 使用一个固定大小的数组 queue 来模拟队列，front 表示队列的头部（出队位置），rear 表示队列的尾部（入队位置）。

• 将树的根节点入队。

3.层序遍历：

• 使用一个 while 循环，当队列不为空（front != rear）时，持续进行遍历。

• 在每次循环中，计算当前层的节点数 levelSize（rear - front），确保一次处理完整层的所有节点。

• 遍历当前层的所有节点：

  • 从队列中取出节点（queue[front++]），并打印其键值。

  • 如果当前节点有左子节点，则将左子节点加入队列。

  • 如果当前节点有右子节点，则将右子节点加入队列。

• 每处理完一层，打印一个换行符。

优点：

直观展示层级结构：层序遍历清晰地展示了树的层级关系，便于观察树的整体结构。

简单易懂：通过队列的辅助，代码逻辑清晰，易于实现和理解。

适合中小型树的展示：对于中小型树，输出紧凑且易于阅读。
 

缺点：

固定队列大小：代码中使用了固定大小的数组（queue[100]）来模拟队列，这可能导致队列溢出（如果树的节点数超过 100）。可以考虑使用动态数据结构（如链表）来实现队列。

不适用于树的可视化：层序输出虽然展示了层级关系，但无法直观展示树的形状（如节点之间的连接关系）。

性能考虑：对于非常大的树，层序遍历可能需要较大的内存来存储队列。

具体分析：

调用 printLevelOrder(root) 后的输出将为：

假设队列的初始状态如下：

• front = 0, rear = 0

• queue[0] = root（节点 3），rear 增加到 1

第一圈（处理第 1 层）：

• levelSize = rear - front = 1

• 取出节点 3，打印 3

• 将节点 3 的左子节点（1）和右子节点（5）加入队列

• 队列变为：[1, 5]，front = 1, rear = 2

第二圈（处理第 2 层）：

• levelSize = rear - front = 1

• 取出节点 1，打印 1

• 节点 1 无子节点，所以不入队

• 队列变为：[5]，front = 2, rear = 2

第三圈（处理第 3 层）：

• levelSize = rear - front = 0，循环结束

15.保存树结构到文件

参数：

root：指向 AVL 树的根节点的指针，表示要保存的树的起始节点。

filename：目标文件的路径名，用于指定保存树结构的文件。

逻辑流程：

1.文件打开与错误处理：、

• 使用 fopen 函数以写模式打开（或创建）指定文件。

• 若文件打开失败（返回 NULL），输出错误信息并返回。

2.队列初始化：

• 使用固定大小的数组 queue 模拟队列，用于存储待处理的节点。

• 初始化队列的头指针 front 和尾指针 rear 为 0。

• 将树的根节点加入队列。

3.层序遍历与文件写入：

• 当队列非空时，循环执行以下操作：

  • 计算当前层节点数：根据队列的头尾指针计算当前层的节点数 levelSize。

  • 处理当前层所有节点：

    • 从队列中取出节点（先进先出）。

    • 若节点非空，将其键值写入文件，并将其子节点加入队列。

    • 若节点为空，向文件写入 "N" 表示空节点。

  • 每处理完一层，向文件写入换行符，准备下一层的记录。

4.文件关闭：

• 所有节点处理完毕后，关闭文件并输出保存成功的提示信息。

优点

直观记录树结构：逐层保存树节点，清晰体现树的层次关系，便于后续分析或重建树结构。

兼容空节点：通过 "N" 标记空节点，完整保存树的实际结构，包括空分支。

简单易懂：基于队列的层序遍历逻辑清晰，代码实现直观。
 

缺点

固定队列大小限制：队列使用固定大小的数组实现，树节点过多时可能导致队列溢出。建议改用动态数据结构（如链表队列）。

文件格式简单：输出文件的格式较为基础，每行节点以逗号分隔，缺乏结构化信息（如层级标记），可能不便于某些复杂场景下的解析。

性能考虑：对于大规模树结构，频繁的文件读写操作可能影响性能，建议优化缓冲策略。

16.查询节点的前驱和后继函数

参数：

root：指向AVL树根节点的指针，表示要查询的树的起始节点。

key：要查询的节点的键值。

逻辑流程：

1.查找目标节点：

• 使用search函数在AVL树中查找键值为key的节点。如果找不到该节点（返回NULL），则输出提示信息并返回。

2.查找前驱节点：

• 调用findPredecessor函数获取目标节点的前驱节点。

• 如果前驱节点存在（非NULL），则输出前驱节点的键值；否则，提示没有前驱。

3.查找后继节点：

• 调用findSuccessor函数获取目标节点的后继节点。

• 如果后继节点存在（非NULL），则输出后继节点的键值；否则，提示没有后继。

三、完整代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 定义AVL树节点结构
typedef struct AVLNode 
{int key;struct AVLNode* left;struct AVLNode* right;int height;struct AVLNode* parent; // 新增：父指针
} AVLNode;// 创建新节点
AVLNode* createNode(int key) 
{AVLNode* node = (AVLNode*)malloc(sizeof(AVLNode));if (node == NULL){return NULL;}node->key = key;node->left = NULL;node->right = NULL;node->height = 1;node->parent = NULL; // 初始化父指针return node;
}// 获取节点高度
int getHeight(AVLNode* node) 
{if (node == NULL) {return 0;}return node->height;
}// 更新节点高度
void updateHeight(AVLNode* node) 
{if (node != NULL) {node->height = 1 + (getHeight(node->left) > getHeight(node->right) ? getHeight(node->left) : getHeight(node->right));}
}// 计算平衡因子
int getBalanceFactor(AVLNode* node)
{if (node == NULL){return 0;}return getHeight(node->left) - getHeight(node->right);
}// 右旋操作
AVLNode* rightRotate(AVLNode* y)
{AVLNode* x = y->left;AVLNode* T2 = x->right;// 执行旋转x->right = y;y->left = T2;// 更新父指针 - 新增y->parent = x;if (T2 != NULL) {T2->parent = y;}// 更新高度updateHeight(y);updateHeight(x);return x;
}// 左旋操作
AVLNode* leftRotate(AVLNode* x) 
{AVLNode* y = x->right;AVLNode* T2 = y->left;// 执行旋转y->left = x;x->right = T2;// 更新父指针 - 新增x->parent = y;if (T2 != NULL) {T2->parent = x;}// 更新高度updateHeight(x);updateHeight(y);return y;
}// 插入节点
AVLNode* insert(AVLNode* node, int key) 
{// 1. 执行标准BST插入if (node == NULL) {return createNode(key);}if (key < node->key) {node->left = insert(node->left, key);node->left->parent = node; // 更新左子节点的父指针 - 新增}else if (key > node->key) {node->right = insert(node->right, key);node->right->parent = node; // 更新右子节点的父指针 - 新增}else {// 不允许插入重复值return node;}// 2. 更新高度updateHeight(node);// 3. 获取平衡因子int balance = getBalanceFactor(node);// 如果节点不平衡，则进行旋转// 左左情况if (balance > 1 && key < node->left->key) {AVLNode* temp = rightRotate(node);temp->parent = node->parent; // 更新旋转后的父指针 - 新增return temp;}// 右右情况if (balance < -1 && key > node->right->key){AVLNode* temp = leftRotate(node);temp->parent = node->parent; // 更新旋转后的父指针 - 新增return temp;}// 左右情况if (balance > 1 && key > node->left->key) {node->left = leftRotate(node->left);AVLNode* temp = rightRotate(node);temp->parent = node->parent; // 更新旋转后的父指针 - 新增return temp;}// 右左情况if (balance < -1 && key < node->right->key){node->right = rightRotate(node->right);AVLNode* temp = leftRotate(node);temp->parent = node->parent; // 更新旋转后的父指针 - 新增return temp;}// 无需旋转，直接返回return node;
}// 查找节点
AVLNode* search(AVLNode* root, int key) 
{if (root == NULL || root->key == key){return root;}if (key < root->key) {return search(root->left, key);}return search(root->right, key);
}// 查找节点前驱
AVLNode* findPredecessor(AVLNode* node)
{if (node == NULL) {return NULL;}// 如果有左子树，前驱是左子树中最右的节点if (node->left != NULL) {AVLNode* predecessor = node->left;while (predecessor->right != NULL) {predecessor = predecessor->right;}return predecessor;}else {// 如果没有左子树，向上查找前驱AVLNode* parent = node->parent;while (parent != NULL && node == parent->left){node = parent;parent = parent->parent;}return parent;}
}// 查找节点后继
AVLNode* findSuccessor(AVLNode* node)
{if (node == NULL){return NULL;}// 如果有右子树，后继是右子树中最左的节点if (node->right != NULL) {AVLNode* successor = node->right;while (successor->left != NULL) {successor = successor->left;}return successor;}else {// 如果没有右子树，向上查找后继AVLNode* parent = node->parent;while (parent != NULL && node == parent->right){node = parent;parent = parent->parent;}return parent;}
}// 删除节点
AVLNode* deleteNode(AVLNode* root, int key)
{if (root == NULL){return root;}if (key < root->key) {root->left = deleteNode(root->left, key);if (root->left != NULL) {root->left->parent = root; // 更新左子节点的父指针 - 新增}}else if (key > root->key){root->right = deleteNode(root->right, key);if (root->right != NULL) {root->right->parent = root; // 更新右子节点的父指针 - 新增}}else {// 叶子节点或只有一个子节点的节点if (root->left == NULL){AVLNode* temp = root->right;if (temp != NULL){temp->parent = root->parent; // 更新子节点的父指针 - 新增}free(root);return temp;}else if (root->right == NULL){AVLNode* temp = root->left;if (temp != NULL) {temp->parent = root->parent; // 更新子节点的父指针 - 新增}free(root);return temp;}// 有两个子节点的节点，找到前驱节点AVLNode* predecessor = findPredecessor(root);root->key = predecessor->key;root->left = deleteNode(root->left, predecessor->key);if (root->left != NULL) {root->left->parent = root; // 更新左子节点的父指针 - 新增}}// 如果树为空，返回if (root == NULL){return root;}// 更新高度updateHeight(root);// 获取平衡因子int balance = getBalanceFactor(root);// 如果节点不平衡，则进行旋转// 左左情况if (balance > 1 && getBalanceFactor(root->left) >= 0) {AVLNode* temp = rightRotate(root);temp->parent = root->parent; // 更新旋转后的父指针 - 新增return temp;}// 左右情况if (balance > 1 && getBalanceFactor(root->left) < 0) {root->left = leftRotate(root->left);AVLNode* temp = rightRotate(root);temp->parent = root->parent; // 更新旋转后的父指针 - 新增return temp;}// 右右情况if (balance < -1 && getBalanceFactor(root->right) <= 0){AVLNode* temp = leftRotate(root);temp->parent = root->parent; // 更新旋转后的父指针 - 新增return temp;}// 右左情况if (balance < -1 && getBalanceFactor(root->right) > 0){root->right = rightRotate(root->right);AVLNode* temp = leftRotate(root);temp->parent = root->parent; // 更新旋转后的父指针 - 新增return temp;}return root;
}// 以树形结构展示AVL树
void printTree(AVLNode* root, int level) 
{if (root == NULL){return;}printTree(root->right, level + 1);for (int i = 0; i < level; i++){printf("    ");}printf("%d\n", root->key);printTree(root->left, level + 1);
}// 以层序结构展示AVL树
void printLevelOrder(AVLNode* root) 
{if (root == NULL){printf("Tree is empty\n");return;}printf("Level Order Traversal:\n");// 创建一个队列AVLNode* queue[100] = {0};int front = 0, rear = 0;queue[rear++] = root;while (front != rear){// 计算当前层的节点数int levelSize = rear - front;// 输出当前层的所有节点for (int i = 0; i < levelSize; i++){AVLNode* node = queue[front++];printf("%d ", node->key);// 将子节点加入队列if (node->left){queue[rear++] = node->left;}if (node->right){queue[rear++] = node->right;}}printf("\n");}
}// 保存树结构到文件
void saveTreeToFile(AVLNode* root, const char* filename) 
{FILE* file = fopen(filename, "w");if (file == NULL) {printf("无法打开文件 %s\n", filename);return;}// 创建一个队列AVLNode* queue[100] = {0};int front = 0, rear = 0;queue[rear++] = root;while (front != rear){// 计算当前层的节点数int levelSize = rear - front;// 输出当前层的所有节点for (int i = 0; i < levelSize; i++){AVLNode* node = queue[front++];// 如果节点不为空，记录其值和子节点if (node) {fprintf(file, "%d,", node->key);if (node->left) queue[rear++] = node->left;if (node->right) queue[rear++] = node->right;}else {fprintf(file, "N,");}}fprintf(file, "\n");}fclose(file);printf("树结构已保存到文件 %s\n", filename);
}// 查询节点的前驱和后继
void findPredecessorAndSuccessor(AVLNode* root, int key)
{AVLNode* node = search(root, key);if (node == NULL) {printf("节点 %d 不存在于树中\n", key);return;}AVLNode* predecessor = findPredecessor(node);if (predecessor != NULL) {printf("节点 %d 的前驱是 %d\n", key, predecessor->key);}else {printf("节点 %d 没有前驱\n", key);}AVLNode* successor = findSuccessor(node);if (successor != NULL) {printf("节点 %d 的后继是 %d\n", key, successor->key);}else{printf("节点 %d 没有后继\n", key);}
}// 主函数
int main() 
{AVLNode* root = NULL;int choice, key;char filename[100];while (1) {printf("\n=== AVL树交互式系统 ===\n");printf("1. 插入节点\n");printf("2. 删除节点\n");printf("3. 查找节点\n");printf("4. 显示树结构\n");printf("5. 查询节点的前驱和后继\n"); // 新增：菜单选项printf("6. 保存树结构到文件\n");printf("7. 退出程序\n");printf("请输入您的选择：");scanf_s("%d", &choice);switch (choice){case 1:printf("请输入要插入的键值：");scanf_s("%d", &key);root = insert(root, key);printf("节点 %d 已插入\n", key);break;case 2:printf("请输入要删除的键值：");scanf_s("%d", &key);root = deleteNode(root, key);printf("节点 %d 已删除\n", key);break;case 3:printf("请输入要查找的键值：");scanf_s("%d", &key);if (search(root, key) != NULL) {printf("节点 %d 存在于树中\n", key);}else {printf("节点 %d 不存在于树中\n", key);}break;case 4:printf("=== AVL树当前结构 ===\n");printTree(root, 0);printf("\n");printLevelOrder(root);break;case 5: // 新增：查询前驱和后继printf("请输入要查询的键值：");scanf_s("%d", &key);findPredecessorAndSuccessor(root, key);break;case 6:printf("请输入保存文件名：");scanf_s("%s", filename, (unsigned)_countof(filename));saveTreeToFile(root, filename);break;case 7:printf("退出程序\n");exit(0);default:printf("无效的选择，请重新输入\n");}}return 0;
}

用c语言实现的——一个完整的AVL树管理系统，支持查找、插入、删除、查找指定节点的前驱和后继节点、树形展示、层次展示、文件存储等功能，适用于需要高效数据管理和树结构操作的场景。用户可以通过交互式菜单方便地操作和查看AVL树的状态。