平衡二叉树是二叉搜索树的改进版，二叉搜索树有可能会被退化为链表，而平衡二叉树保持二叉树的高度稳定，使得查找数据效率基本维持在对数级别。本文介绍如何实现c语言平衡二叉树结构。工具/原料morenotepad++等编辑器gcc等c语言编译器方法/步骤1/14分步阅读

定义平衡二叉树结构：定义数据结构以及声明函数。

2/14

创建二叉树，以及创建二叉树节点。只是使用内存申请函数创建对应结构并返回。

3/14

查找二叉搜索树中是否存在某个节点：在遍历过程中，因为左子节点小于根节点值，根节点值小于右子节点值。利用该特性，在查询时递归查找左/右子树。

4/14

添加或删除节点时，我们需要修改父节点中子节点指针，所以我们还定义一个查找某个值对应父节点的函数。并且函数返回值标识为该值是否存在，这样在添加或删除时可以先判断是否存在后，在进行进一步操作。

5/14

添加节点：首先查找二叉搜索树中是否存在该值。只有不存在时才进行添加操作。

并且，使用上述函数，我们同时得到该值添加位置，创建节点后添加到父节点相应子节点下。

6/14

删除节点：使用步骤4中定义的查找方法，如果节点不存在则不做处理。否则，需要删除该节点。

因为删除节点后要保持二叉搜索树的完整性，所以我们需要区分节点的不同情况。

1. 删除叶子节点：直接删除，只需要修改父节点中对应指针为空

2. 节点只有左子树：直接删除，并且修改父节点中指针指向该左子树

3. 节点只有右子树：直接删除，并且修改父节点中指针指向右子树

4. 节点有左右子树：需要将合适的元素移动到该位置。左子树中最大值或右子树中最小值。

在这里，我们选择使用左子树中最大值：查找左子树中最右边节点值。

7/14

二叉搜索树的遍历，与二叉树的遍历类似，使用递归调用的方式，有前序、中序、后序遍历三种方式

8/14

在此，我们添加二叉搜索树的层序遍历方法。顾名思义，按照每层的方式输出二叉树。

因为我们在二叉树结构中保存了节点个数信息，所以首先我们初始化一个指针数组。层序遍历时，将非空子树添加到指针数组中，之后递归遍历该数组。

9/14

二叉搜索树的释放：采用递归调用的方式，需要先释放节点的子节点，之后才释放节点。

10/14

上述步骤与二叉搜索树基本一致，我们只是在添加节点、删除节点函数最后执行了调整二叉树的操作。

引起节点不平衡有4种情况：往节点的左子树的左子树添加节点、往节点的左子树的右子树添加节点，以及对称的往节点的右子树的左子树添加节点、往节点右子树的右子树添加节点。

11/14

我们分别定义处理上述4种情况的旋转函数，如下图所示

12/14

在调整二叉搜索树之前，我们首先初始化二叉树中每个节点的高度。

13/14

调整二叉树：判断当前节点是否平衡，并针对引起不平衡的情况执行不同的旋转处理操作。如下图所示：

14/14

最后，编写验证程序。构造包含20个数的二叉树，并输出最终二叉树结构。删除部分节点后，重新输出二叉树结构。程序运行结果正确。

注意事项

删除节点时，需要保持二叉搜索树的特性

添加、删除节点等操作，需要注意处理边界情况，如根节点

添加、删除节点后，调整二叉树进行平衡处理

C语言数据结构平衡二叉树AVL树二叉树