C语言中对平衡二叉树进行实现 C语言中对平衡二叉树进行实现

自平衡二叉搜索树（Self-Balanced Binary Search Tree），其左右子树的高度差为-1、0或1。

二叉平衡树又称为AVL树。

平衡因子BF是指二叉树上结点的左子树深度减去右子树深度的值。

如果二叉树中存在某个节点其balance factor的绝对值超过1那么该二叉树即为不均衡的

平衡二叉搜索树的核心思路是，在建立二叉排序树的过程中，在每次加入一个节点后检查是否导致了不平衡，并确定最小失衡子树区域。为了维持其特性，在优化相关联的子结构链接之后实现对称性重组以达到新的平衡状态。

若该最小不平衡子树根节点的BF值大于1，则执行右调整；若其对应的子树（即该根节点）的BF值小于-1，则执行左调整。在插入新结点后，在该最小不平衡子树中发现其对应的子树与之具有相反符号的情况时，则需先对该根节点进行一次调整使其符号一致后再反向调整一次即可完成整个平衡过程。

以下程序在DEV C++中调试运行通过。

 #include<stdio.h>

    
 #include<stdlib.h>
    
 #define LH 1
    
 #define EH 0
    
 #define RH -1
    
  
    
 typedef struct BiTNode
    
 {
    
 	int data;
    
 	int bf;