平衡树.cpp

查找序列以带头结点的单链表表示

/*
  Name: 平衡树 
  Copyright: 
  Author: 
  Date: 02-12-08 18:12
  Description: 
*/
#define LH +1//左子树比右子树高1 
#define EH 0 //相等 
#define RH -1//右子树比左子树高1 
#define TRUE 1//树长高 
#define FALSE 0//树未长高 

#include<stdio.h>
#include<stdlib.h>
#include <malloc.h>
# include <iostream>

using namespace std;

typedef struct BSTNode //二叉树的节点
{
   char data;//存储关键字 
   int bf;   //平衡度 
   struct BSTNode * lchild, * rchild;
}BSTNode,* BSTree;

int insert(BSTree & root,char key,int & taller);//声明函数 insert,用于插入关键字  
void leftbalance(BSTree & root);//声明左平衡函数 leftbalance
void rightbalance(BSTree & root);//声明右平衡函数 rightbalance
void r_rotate(BSTree & p);//声明右旋函数  r_rotate
void l_rotate(BSTree &p);//声明左旋函数  l_rotate
void inorder(BSTree root);//声明逆中序遍历函数inorder, 

main()
{
   char key;//代表关键字 
   BSTree T=NULL; //代表树根 
   int taller=FALSE;//代表树是否长高
    
   cout << "please enter the string(end with a '#')"<<endl;//读入关键字 
   cin >> key;
   
   while(key!='#')
   {
      insert(T,key,taller);//插入关键字 
      
      cout<<"the reverse inorder is"<<endl;//逆中序遍历树 
      inorder(T);
      cout<<endl;
      
      cin>>key;//读入下一个关键字 
   }
   
   system("pause");
   return 0;
}

//定义遍历树的函数postorder 
void inorder(BSTree root)
{
   if(root)
   {
      inorder(root->rchild);//遍历右子树 
      cout<<root->data<<"  ";
      inorder(root->lchild);//遍历左子树 
   }
}

//定义函数 insert,用于插入关键字 
int insert(BSTree & root,char key,int & taller)
{
   if(!root)//是空树 
   {
      root=(BSTree)malloc(sizeof(BSTNode)) ;//动态申请内存 
      root->data=key;
      root->lchild=root->rchild=NULL;
      root->bf=EH;
      taller=TRUE;
   }
   else
   {
      if(key==root->data)//查找到了关键字 
      {
         taller=FALSE;
         return 0;
      }
      if(key<root->data)//关键字小 
      {
         if(!insert(root->lchild,key,taller))   return 0;//在左子树中查找 
         if(taller)//已插入并且左子树长高 
            switch(root->bf)
            {
               case LH:
                  leftbalance(root);taller=FALSE;break;//原本左子树高,进行左平衡 
               case EH:
                  root->bf=LH;taller=TRUE;break;//原本左右子树等高 ,现在左子树长高使树长高 
               case RH:
                  root->bf=EH;taller=FALSE;break;//原本右子树高.现在等高 
            }
      }
      else
      {
         if(!insert(root->rchild,key,taller))   return 0;//在右子树中查找
         if(taller)//已插入并且右子树长高
            switch(root->bf)
            {
               case RH:
                  rightbalance(root);taller=FALSE;break;//原本右子树高,进行右平衡
               case EH:
                  root->bf=RH;taller=TRUE;break;//原本左右子树等高 ,现在右子树长高使树长高 
               case LH:
                  root->bf=EH;taller=FALSE;break;//原本左子树高.现在等高 
            }
      }
   }
   return 1;
}

//定义左平衡函数 leftbalance
void leftbalance(BSTree & root)
{
   BSTree lc,rd;//代表左孩子,和左孩子的右子树 
   
   lc=root->lchild;

   switch(lc->bf)
   {
      case LH://要插入的节点在根的左孩子的左子树上,做单右旋处理 
         root->bf=lc->bf=EH;
         r_rotate(root);break;
      case RH://要插入的节点在根的左孩子的右子树上,做双旋处理
         rd=lc->rchild;
         switch(rd->bf)//修改根和它左孩子的平衡因子 
         {
            case LH:
               root->bf=RH;
               lc->bf=EH;
               break;
            case EH:
               root->bf=lc->bf=EH;
               break;
            case RH:
               root->bf=EH;
               lc->bf=LH;
               break;
         }
         rd->bf=EH;
         l_rotate(root->lchild); 
         r_rotate(root);
   }
}

//定义右平衡函数 rightbalance
void rightbalance(BSTree & root)
{
   BSTree rc,ld;//代表右孩子 ,和右孩子的左子树 
   
   rc=root->rchild;

   switch(rc->bf)//检查右孩子的平衡因子 
   {
      case RH://要插入的节点在根的右孩子的右子树上,做单右旋处理
         root->bf=rc->bf=EH;
         l_rotate(root);break;
      case LH://要插入的节点在根的右孩子的左子树上,做双旋处理
         ld=rc->lchild;
         switch(ld->bf)//修改根和它右孩子的平衡因子 
         {
            case LH:
               root->bf=RH;
               rc->bf=EH;
               break;
            case EH:
               root->bf=rc->bf=EH;
               break;
            case RH:
               root->bf=EH;
               rc->bf=LH;
               break;
         }
         ld->bf=EH;
         r_rotate(root->rchild);
         l_rotate(root);
   }
}

//定义左旋函数  r_rotate
void l_rotate(BSTree & p)
{
  BSTree rc;
  
  rc=p->rchild;  
  p->rchild=rc->lchild; 
  rc->lchild=p;    
  p=rc;   
}

//定义右旋函数  r_rotate
void r_rotate(BSTree & p)
{
  BSTree lc ;
  
  lc=p->lchild ;  
  p->lchild=lc->rchild ; 
  lc->rchild=p ;    
  p=lc ;           
}