平衡二叉树的实现算法

平衡二叉树的实现算法

[cpp] 
  1. /*
  2. 首先平衡二叉树是一个二叉排序树;
  3. 其基本思想是:
  4. 在构建二叉排序树的过程中,当每插入一个节点时,
  5. 先检查是否因为插入而破坏了树的平衡性,若是,
  6. 找出最小不平衡树,进行适应的旋转,使之成为新的平衡二叉树。
  7. */
  8. #include<cstdio>
  9. #include<cstdlib>
  10. #define LH 1
  11. #define EH 0
  12. #define RH -1
  13. using namespace std;
  14. typedef struct BTNode
  15. {
  16.     int data;
  17.     int BF;//平衡因子(balance factor)
  18.     struct BTNode *lchild,*rchild;
  19. }BTNode,*BTree;
  20. void R_Rotate(BTree *p)//以p为根节点的二叉排序树进行右旋转
  21. {
  22.     BTree L;
  23.     L=(*p)->lchild;
  24.     (*p)->lchild=L->rchild;
  25.     L->rchild=(*p);
  26.     *p=L;//p指向新的根节点
  27. }
  28. void L_Rotate(BTree *p)//以p为根节点的二叉排序树进行左旋转
  29. {
  30.     BTree R;
  31.     R=(*p)->rchild;
  32.     (*p)->rchild=R->lchild;
  33.     R->lchild=(*p);
  34.     *p=R;
  35. }
  36. void LeftBalance(BTree *T)
  37. {
  38.     BTree L,Lr;
  39.     L=(*T)->lchild;
  40.     switch(L->BF)
  41.     {
  42.         //检查T的左子树平衡度,并作相应的平衡处理
  43.         case LH://新节点插入在T的左孩子的左子树上,做单右旋处理
  44.             (*T)->BF=L->BF=EH;
  45.             R_Rotate(T);
  46.             break;
  47.         case RH://新插入节点在T的左孩子的右子树上,做双旋处理
  48.             Lr=L->rchild;
  49.             switch(Lr->BF)
  50.             {
  51.                 case LH:
  52.                     (*T)->BF=RH;
  53.                     L->BF=EH;
  54.                     break;
  55.                 case EH:
  56.                     (*T)->BF=L->BF=EH;
  57.                     break;
  58.                 case RH:
  59.                     (*T)->BF=EH;
  60.                     L->BF=LH;
  61.                     break;
  62.             }
  63.             Lr->BF=EH;
  64.             L_Rotate(&(*T)->lchild);
  65.             R_Rotate(T);
  66.     }
  67. }
  68. void RightBalance(BTree *T)
  69. {
  70.     BTree R,Rl;
  71.     R=(*T)->rchild;
  72.     switch(R->BF)
  73.     {
  74.         case RH://新节点插在T的右孩子的右子树上,要做单左旋处理
  75.             (*T)->BF=R->BF=EH;
  76.             L_Rotate(T);
  77.             break;
  78.         case LH://新节点插在T的右孩子的左子树上,要做双旋处理
  79.             Rl=R->lchild;
  80.             switch(Rl->BF)
  81.             {
  82.                 case LH:
  83.                     (*T)->BF=EH;
  84.                     R->BF=RH;
  85.                     break;
  86.                 case EH:
  87.                     (*T)->BF=R->BF=EH;
  88.                     break;
  89.                 case RH:
  90.                     (*T)->BF=LH;
  91.                     R->BF=EH;
  92.                     break;
  93.             }
  94.             Rl->BF=EH;
  95.             R_Rotate(&(*T)->rchild);
  96.             L_Rotate(T);
  97.     }
  98. }
  99. bool InsertAVL(BTree *T,int e,bool *taller)//变量taller反应T长高与否
  100. {
  101.     if(!*T)
  102.     {
  103.         *T=(BTree)malloc(sizeof(BTNode));
  104.         (*T)->data=e;
  105.         (*T)->lchild=(*T)->rchild=NULL;
  106.         (*T)->BF=EH;
  107.         *taller=true;
  108.     }
  109.     else
  110.     {
  111.         if(e==(*T)->data)//不插入
  112.         {
  113.             *taller=false;
  114.             return false;
  115.         }
  116.         if(e<(*T)->data)
  117.         {
  118.             if(!InsertAVL(&(*T)->lchild,e,taller))//未插入
  119.                 return false;
  120.             if(*taller)//以插入左子树,且左子树变高
  121.             {
  122.                 switch((*T)->BF)
  123.                 {
  124.                     case LH://原本左子树比右子树高,需要做左平衡处理
  125.                         LeftBalance(T);
  126.                         *taller=false;
  127.                         break;
  128.                     case EH://原本左右子树等高,现因左子树增高而树增高
  129.                         (*T)->BF=LH;
  130.                         *taller=true;
  131.                         break;
  132.                     case RH://原本右子树比左子树高,现在左右子树等高
  133.                         (*T)->BF=EH;
  134.                         *taller=false;
  135.                         break;
  136.                 }
  137.             }
  138.         }
  139.         else
  140.         {
  141.             //应在T的右子树中搜寻
  142.             if(!InsertAVL(&(*T)->rchild,e,taller))
  143.                 return false;
  144.             if(*taller)//插入右子树,且右子树长高
  145.             {
  146.                 switch((*T)->BF)
  147.                 {
  148.                     case LH://原本左子树比右子树高,现在左右子树等高
  149.                         (*T)->BF=EH;
  150.                         *taller=false;
  151.                         break;
  152.                     case EH://原本左右子树等高,现在右子树变高
  153.                         (*T)->BF=RH;
  154.                         *taller=true;
  155.                         break;
  156.                     case RH://原本右子树比左子树高,现在需做右平衡处理
  157.                         RightBalance(T);
  158.                         *taller=false;
  159.                         break;
  160.                 }
  161.             }
  162.         }
  163.     }
  164.     return true;
  165. }
  166. bool Find(BTree T,int key)
  167. {
  168.     if(!T)
  169.         return false;
  170.     else if(T->data==key)
  171.         return true;
  172.     else if(T->data<key)
  173.         return Find(T->rchild,key);
  174.     else
  175.         return Find(T->lchild,key);
  176. }
  177. void Output(BTree T)
  178. {
  179.     if(T)
  180.     {
  181.         printf(“%d”,T->data);
  182.         if(T->lchild||T->rchild)
  183.         {
  184.             printf(“(“);
  185.             Output(T->lchild);
  186.             printf(“,”);
  187.             Output(T->rchild);
  188.             printf(“)”);
  189.         }
  190.     }
  191. }
  192. int main(int argc,char *argv[])
  193. {
  194.     int i;
  195.     int A[]={3,2,1,4,5,6,7,10,9,8};
  196.     BTree T=NULL;
  197.     bool taller;
  198.     for(i=0;i<sizeof(A)/sizeof(int);i++)
  199.         InsertAVL(&T,A[i],&taller);
  200.     Output(T);
  201.     printf(“\n”);
  202.     if(Find(T,6))
  203.         printf(“6 is find in the AVL tree!\n”);
  204.     else
  205.         printf(“6 is not find in the AVL tree!\n”);
  206.     return 0;
  207. }

标签