| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 876 人关注过本帖
标题:平衡二叉树的编程
取消只看楼主 加入收藏
ltxbs81
Rank: 1
等 级:新手上路
帖 子:11
专家分:0
注 册:2010-4-23
结帖率:66.67%
收藏
已结贴  问题点数:20 回复次数:2 
平衡二叉树的编程
诸位好,小弟遇到了一道难题:
已知某排序平衡二叉树T具有下列特点:
(1)结点的关键字均在1到9范围为内;
(2)在T中存在一个关键字为n1的叶结点,若删去该结点,立即插入一个关键字为n1的结点,得到的平衡树与原T不同;
(3)在T中存在一个关键字为n2的非叶结点,若删去该结点,立即插入n2结点,得到与原T相同的平衡树;
(4)在T中插入某n3结点并立即删去它,得到的平衡树与原T不同。
试通过程序输出具有上述特点的最简单(结点个数最少)的平衡二叉树T,并写明n1,n2,n3分别等于几?
恳请大家帮忙解决,谢谢!

我的QQ:751217908.
邮箱:ltxbs81@
搜索更多相关主题的帖子: 二叉树 
2010-05-06 00:45
ltxbs81
Rank: 1
等 级:新手上路
帖 子:11
专家分:0
注 册:2010-4-23
收藏
得分:0 
我摘抄了些,但不能满足题目的要求。恳请各位帮忙搞定!谢谢!


#include<iostream>using namespace std;typedef struct BSTNode{ char data; int bf; BSTNode *lchild,*rchild;}BSTNode,*BSTree;//函数功能:实现对节点P的右旋处理void R_Rotate(BSTree &p) //右转函数{ BSTree lc; lc=p->lchild; //lc指向*p的左子树根节点 p->lchild=lc->rchild; //lc的右子树挂接为*p的左子树 lc->rchild=p;  p=lc; //p指向新的根节点}//函数功能:实现对节点P的左旋处理void L_Rotate(BSTree &p){ BSTree rc; rc=p->rchild; //lc指向*p的右子树根节点 p->rchild=rc->lchild; //lc的左子树挂接为*p的左子树 rc->lchild=p;  p=rc; //p指向新的根节点}#define LH 1 //左高#define EH 0 //等高#define RH -1 //右高//函数功能:实现对树T的左平衡处理void LeftBalance(BSTree &T){ BSTree lc,rd; lc=T->lchild; //lc指向T的左孩子 switch(lc->bf) //检查T的左子树的平衡度,并作相应处理 { case LH:T->bf=lc->bf=EH;R_Rotate(T);break;  case RH:rd=lc->rchild; //新节点插入在T的左孩子的右子树上,做双旋处理 switch(rd->bf) //修改T及其左孩子的平衡因子 { case LH:T->bf=RH;lc->bf=EH;break; case EH:T->bf=lc->bf=EH;break; case RH:T->bf=EH; lc->bf=EH;break; } rd->bf=EH; L_Rotate(T->lchild); //对T的左子树作左旋处理 R_Rotate(T); //对T作右旋平衡处理 }}//函数功能:实现对树T的右旋处理void RightBalance(BSTree &T){ BSTree lc,rd; lc=T->rchild; //lc指向T的右孩子 switch(lc->bf) { case RH:T->bf=lc->bf=EH;L_Rotate(T);break; //修改平衡因子,左旋处理 case LH:rd=lc->lchild; switch(rd->bf) //新节点插入在T的左子树上,作双旋处理 { case LH:T->bf=EH;lc->bf=RH;break; case EH:T->bf=lc->bf=EH;break; case RH:T->bf=LH; lc->bf=EH;break; } rd->bf=EH; R_Rotate(T->rchild); //对T的右子树右旋处理 L_Rotate(T); //对T作左旋处理 }}//函数功能:实现对元素E的插入到二叉树的操作int InsertAVL(BSTree &T,char e,bool &taller){ if(!T){ //T为空的情况。树长高 T=(BSTree)malloc(sizeof(BSTNode)); T->lchild=T->rchild=NULL; T->bf=EH; T->data=e; taller=true; } else { if(e==T->data) //树中已存在和要插入的E相等的节点,不予插入 { taller=false; return 0; } else if(e<T->data) //插入到左边 { if(!InsertAVL(T->lchild,e,taller)) return 0; //未插入 if(taller) switch(T->bf) //检查T的平衡因子 { case LH:LeftBalance(T);taller=false;break; //原本左高,左旋 case EH: T->bf=LH;taller=true;break; //原本等高,左变高 case RH: T->bf=EH;taller=false;break; //原本右高,变等高 } } else //插入到右子树 { if(!InsertAVL(T->rchild,e,taller)) return 0; if(taller) switch(T->bf) //检查平衡因子 { case LH:T->bf=EH; taller=false;break; //原本左高,变等高 case EH:T->bf=RH;taller=true;break; //原本等高,变右高 case RH:RightBalance(T);taller=true;break; //原本右高,右旋处理 } } } return 1;}//函数功能:中序打印出树的所有节点//功能简单,不再注释int Print(BSTree T){ if(!T) return 1; Print(T->lchild); cout<<T->data<<",";//<<"平衡因子:"<<T->bf<<endl; Print(T->rchild); return 0;}//函数功能:先根以凹入表的形式输出树的所有节点int PrintTree(BSTree &T,int layer){ if(!T) return 1; //树为空的情况,即结束条件  for(int i=0;i<layer;i++) //打印前面的空格 cout<<" "; cout<<T->data; //打印节点信息 layer++; for(i=layer;i<20;i++) //打印后面的#号 cout<<"#"; cout<<endl;  PrintTree(T->lchild,layer); PrintTree(T->rchild,layer); return 0;}//函数功能:查找元素e是否在平衡二叉树中,返回要查找点的双亲和本身节点指针int SearchAVL(BSTree &T,char e){ if(!T) {cout<<e<<"不在该平衡二叉树中!"<<endl<<endl;return 0;}  if(T){ if(T->data==e) {cout<<e<<"在平衡二叉树中."<<endl<<endl;return 0;} else if(T->data>e) SearchAVL(T->lchild,e); else SearchAVL(T->rchild,e); } }//函数功能:删除指定的T节点int Delete(BSTree &T,char e,bool &shorter){  BSTree p,q; e=0; p=T; if(!T->rchild) //右子树为空 {  T=T->lchild; free(p); shorter=true; } else if(!T->lchild) //左子树为空 {  T=T->rchild; free(p); shorter=true; } else //左右子树均不空 {  q=T->lchild; // Push(S,p); while(q->rchild!=NULL) //寻找代替节点,即左孩子的最右下节点,删除之 {  //Push(S,q->rchild); q=q->rchild; } e=q->data; } return e;}//函数功能:删除之后的左平衡调节void Delete_Leftbalance(BSTree &T,bool &shorter)//删除的为左子树上的节点{  BSTree rc=T->rchild,ld; switch(rc->bf) { case LH: //先右旋后左旋 ld=rc->lchild; rc->lchild=ld->rchild; ld->rchild=rc; T->rchild=rc->lchild; rc->lchild=T; switch(ld->bf)  { case LH:T->bf=EH; rc->bf=RH;  break; case EH:T->bf=rc->bf=EH; break; case RH:T->bf=LH; rc->bf=EH; break; } ld->bf=EH; T=rc; shorter=true;break; case EH: //单左旋 T->rchild=rc->lchild; rc->lchild=T; rc->bf=LH; T->bf=RH; T=rc; shorter=EH;break; case RH: //单左旋 T->rchild=rc->lchild; rc->lchild=T; rc->bf=T->bf=EH; T=rc; shorter=true;break; }}//函数功能:实现删除之后的右平衡void Delete_Rightbalance(BSTree &T,bool &shorter)/////删除右子树上的,相当于插入在左子树上{ BSTree p1,p2; p1=T->lchild; switch(p1->bf)  { case LH:T->lchild=p1->rchild;//单右旋 p1->rchild=T; p1->bf=T->bf=EH; T=p1;  shorter=true; break; case EH:T->lchild=p1->rchild;//单右旋 p1->rchild=T; p1->bf=RH; T->bf=LH; T=p1; shorter=false; break; case RH:p2=p1->rchild; //双旋 p1->rchild=p2->lchild; p2->lchild=p1; T->lchild=p2->rchild; p2->rchild=T; switch(p2->bf) { case LH:T->bf=RH;p1->bf=EH;break; case EH:T->bf=EH;p1->bf=EH;break; case RH:T->bf=EH;p1->bf=LH;break; } p2->bf=EH; T=p2; shorter=true;break; } }//函数功能:实现删除平衡二叉树,结构类似插入函数InsertAVL()BSTree DeleteAVL(BSTree &T,char e,bool &shorter){  int judge;/////标记 BSTree q; if(!T) return NULL; else //树非空的情况 { if(e==T->data) //根节点与之相等,直接删除 {  judge=Delete(T,e,shorter);  if(judge!=0) //树高大于2时,删除根的左孩子的最右下节点 { q=T; DeleteAVL(T,judge,shorter); q->data=judge; }  } else { //如果被删的不是根节点 if(e<T->data) //被删节点在左子树上 {  DeleteAVL(T->lchild,e,shorter); if(shorter) //树变矮了 { switch(T->bf) { case LH:T->bf=EH;shorter=true;break; case EH:T->bf=RH;shorter=false;break; case RH:Delete_Leftbalance(T,shorter);shorter=true;break; } } } else //被删节点在在右子树上 {  DeleteAVL(T->rchild,e,shorter);  if(shorter) //树变矮了 switch(T->bf) { case LH:Delete_Rightbalance(T,shorter);shorter=true;break; case EH:T->bf=LH;shorter=false;break; case RH:T->bf=EH;shorter=true;break; } } } } return T;}int main(){ BSTree T=NULL; char e,judge='y',choice,out; bool taller=false; //SqStack S; //InitStack(S);  do{ judge='y'; cout<<endl<<endl; cout<<" ***************************************"<<endl; cout<<" * *"<<endl; cout<<" * *"<<endl; cout<<" * 查找(s) 插入(i) 删除(d) *"<<endl; cout<<" * *"<<endl; cout<<" * 退出(q) *"<<endl; cout<<" ***************************************"<<endl; do{ cout<<"请选择操作:"; cin>>choice; }while(choice!='s'&&choice!='i'&&choice!='d'&&choice!='q'); switch(choice) { case 'i':e='@'; cout<<"您选择了插入。请输入你要输入的节点元素,并以“#”表示结束!"<<endl; cout<<endl<<"请输入你要插入的节点元素:"; while(e!='#') { //cout<<endl<<"请输入你要插入的节点元素:"; cin>>e; if(e!='#') InsertAVL(T,e,taller); //cout<<"是否继续输入(y/n)?"; // cin>>judge; } cout<<"插入之后的平衡二叉树为:"<<endl; PrintTree(T,1);cout<<endl; break; case 's':while(judge=='y') {  if(T) { cout<<endl<<"请输入你要查找的节点元素:"; cin>>e;  SearchAVL(T,e); cout<<"是否继续查找(y/n)?"; cin>>judge; } else {cout<<"对不起,你无法进行查找操作.因为平衡二叉树是空的!"<<endl;break;} } break; case 'd':while(judge=='y') { if(!T) {cout<<"无法执行删除操作,因为树为空.请在树非空的情况下进行!"<<endl<<endl;break;}   cout<<endl<<"请输入你要删除的节点元素:"; cin>>e;  DeleteAVL(T,e,taller); cout<<endl<<endl<<"删除之后的二叉树为:"<<endl; PrintTree(T,1); cout<<endl<<"是否继续删除(y/n)?"; cin>>judge; } break; case 'q':out='y';cout<<endl<<"谢谢使用!"<<endl<<" 龙行天下工作室制作出品"<<endl;;break; }  }while(out!='y');  return 0;}
2010-05-07 10:45
ltxbs81
Rank: 1
等 级:新手上路
帖 子:11
专家分:0
注 册:2010-4-23
收藏
得分:0 
                    版主求助:平衡二叉树的编程!

小弟遇到了一道难题:
已知某排序平衡二叉树T具有下列特点:
(1)结点的关键字均在1到9范围为内;
(2)在T中存在一个关键字为n1的叶结点,若删去该结点,立即插入一个关键字为n1的结点,得到的平衡树与原T不同;
(3)在T中存在一个关键字为n2的非叶结点,若删去该结点,立即插入n2结点,得到与原T相同的平衡树;
(4)在T中插入某n3结点并立即删去它,得到的平衡树与原T不同。
试通过程序输出具有上述特点的最简单(结点个数最少)的平衡二叉树T,并写明n1,n2,n3分别等于几?
恳请大家帮忙解决,谢谢!

我的QQ:751217908.
邮箱:ltxbs81@


书上的是采用AVL方法实现平衡树的。
抄了书本中的相关程序如下:
AVL树的结点声明;
typedef struct avlnode
{
    int height;//比普通二杈有序树多了一个高度信息
    ElemType data;
    struct bnode *lchild, *rchild;
} *AvlTree, *Position;   
//----------AVL树基本操作------------ ------------------------------
AvlTree MakeEmpty(AvlTree T);
Position Find(ElemType x, AvlTree T);
Position FindMin(AvlTree T);
Position FindMax(AvlTree T);
static int Height(Position P);
AvlTree Insert(ElemType x, AvlTree T);
AvlTree Delete(ElemType x, AvlTree T);
ElemType Retrieve(Position P);

//----------AVL树基本操作的算法实现--------------------
递归算法:
Position FindMin(AvlTree T)
{
    if(T==NULL)
        return NULL;
    else if(T->lchild == NULL)
        return T;
    else
        return FindMin(T->lchild);
}

Position FindMax(AvlTree T)
{
    if(T==NULL)
        return NULL;
    else if(T->rchild == NULL)
        return T;
    else
        return FindMax(T->rchild);
}
非递归算法:
Position FindMin(AvlTree T)
{
    if(T!=NULL)
    {
        while(T->lchild != NULL)
            T = T->lchild;
    }
   
    return T;
}

Position FindMax(AvlTree T)
{
    if(T!=NULL)
    {
        while(T->rchild != NULL)
            T = T->rchild;
    }
   
    return T;
}
//返回P点的高度
static int Height(Position P)
{
    if(P==NULL)
        return -1;
    else
        return P->height;
}
//在对一棵AVL树进行插入操作后,可能会破坏它的平衡条件,因此必须对新的AVL树进行调整,
这里用到了“单旋转”或“双旋转”的算法,分别适用于:
单左旋转(SingleRotateWithLeft);对结点p的左孩子的左子树进行一次插入
单右旋转(SingleRotateWithRight);对结点p的右孩子的右子树进行一次插入  
双左旋转(DoubleRotateWithLeft);对结点p的左孩子的右子树进行一次插入
双右旋转(DoubleRotateWithRight);对结点p的右孩子的左子树进行一次插入  
static Position SingleRotateWithLeft(Position K2)
{
    Position K1;
   
    K1 = K2->lchild;  //在K2和K1之间进行一次单左旋转
    K2->lchild = K1->rchild;
    K1->rchild = K2;
   
    K2->height = Max(Height(K2->lchild), Height(K2->rchild)) + 1;
    K1->height = Max(Height(K1->lchild), Height(K1->rchild)) + 1;
   
    return K1;
}

static Position SingleRotateWithRight(Position K2)
{
    Position K1;
   
    K1 = K2->rchild;    //在K2和K1之间进行一次单右旋转
    K2->rchild = K1->lchild;
    K1->lchild = K2;
   
    K2->height = Max(Height(K2->lchild), Height(K2->rchild)) + 1;
    K1->height = Max(Height(K1->lchild), Height(K1->rchild)) + 1;
   
    return K1;
}

static Position DoubleRotateWithLeft(Position K3)
{
    K3->lchild = SingleRotateWithRight(K3->lchild); //在K2和K1之间进行一次单右旋转
   
    return SingleRotateWithLeft(K3); //在K3和K2之间进行一次单左旋转
}

static Position DoubleRotateWithRight(Position K3)
{
    K3->rchild = SingleRotateWithLeft(K3->rchild); //在K2和K1之间进行一次单左旋转
   
    return SingleRotateWithRight(K3);//在K3和K2之间进行一次单右旋转
}

//向AVL树插入结点的操作
AvlTree Insert(float x, AvlTree T)
{
    if(T == NULL)
    {
        T = (Position)malloc(sizeof(struct avlnode));
        if(T == NULL)
        {
            puts("wrong");
            exit(1);
        }
        T->data = x;  
        T->height = 0;
        T->lchild = T->rchild = NULL;
    }
    else if(T->data == x)//不做任何插入操作
        ;
    else if(T->data > x)//把s所指结点插入到左子树中
    {
          T->lchild = Insert(x, T->lchild);
          if(Height(T->lchild) - Height(T->rchild) == 2) //若平衡被破坏
          {
            if(x < T->lchild->data)     //若x比T的左孩子小,对T单左旋转  
                T = SingleRotateWithLeft(T);
            else                         //否则,对T双左旋转   
                T = DoubleRotateWithLeft(T);
        }
    }
    else      //把s所指结点插入到右子树中
    {
          T->rchild = Insert(x, T->rchild);
          if(Height(T->rchild) - Height(T->lchild) == 2)
          {
            if(x > T->rchild->data)    //若x比T的右孩子大,对T单右旋转  
                T = SingleRotateWithRight(T);
            else                        //否则,对T双右旋转   
                T = DoubleRotateWithRight(T);
        }
    }
    T->height = Max(Height(T->lchild), Height(T->rchild)) + 1;
   
    return T;   
}
int Max(int a, int b)
{
    if(a > b)
        return a;
    else
        return b;
}


但书上没有删去时对平衡的处理,下面是我摘抄的别人的删去,插入结点处理方法:


typedef struct BBT
{
 int data;              //节点的数据域
 int bf;                //平衡因子
 BBT * lchild,*rchild;  //节点的左、右孩子指针
}* B_Point,BBT;            //将B_Point定义为结构体指针

B_Point Root;              //定义全树的树根指针全局变量

//左旋转
void BBT_L_Rotate(B_Point & root)            // root为需要旋转的子树树根指针
{
 B_Point rc=root->rchild;                 // 将rc指身树的树根的右子树
 root->rchild=rc->lchild;                 // 将树的右子树的左子树挂到树根的右子树上
 rc->lchild=root;                         // 将root所指树挂到rc的左子树上
 root=rc;                                 //更新树根
}

// 右旋转
void BBT_R_Rotate(B_Point & root)             // root为需要右旋的子树树根指针
{
 B_Point lc=root->lchild;                  //lc指向root的右子树根
 root->lchild=lc->rchild;                  //lc的右子树连接到root的左子树上
 lc->rchild =root;                         //root连接到lc的右子树
 root=lc;                                  //更新树根   
}

//左平衡处理
void LeftBalance(B_Point & root)     
{
 B_Point lc=root->lchild,rc=NULL;          //lc指向root的左子树
 if(lc->bf==1)                             //LL型
 {
  root->bf=lc->bf=0;                    //更新平衡因子
  BBT_R_Rotate(root);                   //root作为根进行右旋转
 }
 else if(lc->bf==-1)                       //LR型
 {
  rc=lc->rchild;                        //将rc指向lc的右子树
  if(rc->bf==1)                         //检查rc的平衡因子,并做相应的处理
  {
   root->bf=-1;
   lc->bf=0;
  }
  else if(rc->bf==0)
  {
   root->bf=0;
   lc->bf=0;
  }
  else
  {
   root->bf =0;
   lc->bf =1;
  }
  rc->bf=0;
  BBT_L_Rotate(root->lchild);               //以root的左子树根结点为根进行左旋转处理
  BBT_R_Rotate(root);                       //以root作为根进行旋转处理
 }
 else  //此情况只可能出现在删除中     此时lc->bf等于0      
 {//修改平衡因子
  rc=lc->rchild;
  if(rc->bf==1)
  {
   root->bf=-1;
   lc->bf=1;
   rc->bf=1;
  }
  else if(rc->bf==0)
  {
   root->bf=1;
   lc->bf=1;
   rc->bf=1;
  }
  else
  {
   root->bf =0;
   lc->bf =2;//设为2方便后面识别
   rc->bf=0;
  }
  
  BBT_L_Rotate(root->lchild);
  BBT_R_Rotate(root);
  if(root->lchild->bf==2)        //此时再追加一次旋转
  {
   root->lchild->bf=root->lchild->lchild->bf=0;
   BBT_R_Rotate(root->lchild);
  }
 }
}

//右平衡处理
void RightBalance(B_Point & root)      
{
 B_Point rc=root->rchild,lc=NULL;
 if(rc->bf==-1)                     //RR型
 {
  rc->bf=root->bf=0;
  BBT_L_Rotate(root);
 }
 else if(rc->bf==1)                 //RL型
 {
  lc=rc->lchild;
  if(lc->bf==1)
  {
   rc->bf=0;
   root->bf =-1;
  }
  else if(lc->bf==0)
  {
   root->bf=rc->bf=0;
  }
  else
  {
   root->bf =1;
   rc->bf =0;
  }
  lc->bf=0;
  BBT_R_Rotate(root->rchild);
  BBT_L_Rotate(root);
 }
 else //此情况只可能出现在删除过程中   此时rc->bf等于0
 {
  lc=rc->lchild;
  if(lc->bf==1)                       //检查lc的平衡因子,并进行相应处理
  {
   rc->bf=-2;
   root->bf =0;
   lc->bf=0;
  }
  else if(lc->bf==0)
  {
   root->bf=0;
   rc->bf=-1;
   lc->bf=-1;
  }
  else
  {
   root->bf =1;
   rc->bf =-1;
  }
  
  BBT_R_Rotate(root->rchild);
  BBT_L_Rotate(root);
  if(root->rchild->bf==-2)//此时由于树并不平等,须追加一次旋转
  {
   root->rchild->bf=root->rchild->rchild->bf=0;//更新平衡因子
   BBT_L_Rotate(root->rchild);
  }
 }
}


// 插入操作
bool BBT_Insert(B_Point & now,bool & taller,int data)   //now表示当前子树的根,taller为真时表示到目前为子树层数增加,为假则没增加
{                                                       //插入成功返回真,否则返回假
 bool result=false;                               //result表示插入的结果,插入成功为真,否则为假
 if(!now)                                         //now指针为空时在当前指针处插入新节点
 {
  now=new BBT;                                 //新建一个节点
  now->bf=0;                                   //节点初始化操作,平衡因子赋为0
  now->data=data;                              //将待插入的数据置入新节点的数据域中
  now->lchild=now->rchild=NULL;                //将新节点的左右子树指针置为空
  taller=true;                                 //添加新节点,默认为增加子树的高度
  return true;                                 //插入成功,返回真
 }
 else if(data<now->data)                          //当前待插入数据小于当前子树根的数据
 {
  result=BBT_Insert(now->lchild,taller,data);   //递归,以当前树根的左子树根为新子树树根调用插入函数
  if(taller)                                    //判断taller的值,为真时插入操作一定成功,并且进入平衡处理
  {                                             //检查插入前当前树根的平衡因子
   if(now->bf==-1)                           
   {
    now->bf=0;                            //插入后不改变此子树高度,无须进一步平衡处理,修改平衡因子即可
    taller=false;                         //子树高不改变,taller置为假
   }
   else if(now->bf==0)
   {
    now->bf =1;                            //插入后子树高增加,但此子树的局部平衡没被破坏,修改平衡因子即可
    taller=true;                           //树高增加,taller置为真
   }
   else
   {
    LeftBalance(now);                      //插入后此子树局部平衡被破坏,需调用左平衡处理函数使之平衡
    taller=false;                          //平衡处理后此子树高度不会增加,taller置为假
   }
  }
 }
 else if(data>now->data)                             //待插入数据大于当前子树根节点数据
 {
  result=BBT_Insert(now->rchild,taller,data);     //以下同上
  if(taller)
  {
   if(now->bf==-1)
   {
    RightBalance(now);
    taller=false;
   }
   else if(now->bf==0)
   {
    now->bf=-1;
    taller=true;
   }
   else
   {
    now->bf=0;
    taller=false;
   }
  }
 }
 return result;                                       //返回插入情况
}

void BBT_Del(B_Point & root,int data,bool & shorter,bool & suc,bool & del,bool & leaf)
{//suc表示删除成功,shorter表示子树高度减小与否,del表示在本次中删除,leaf表示删除的节点是否为叶子节点
 B_Point p,f;
 if(!root)                                         //root为空时表示未找到该数据,suc赋为假
  suc=false;     
 else if(root->data==data)                         //如果待删除数据与当前子树根节点数据相等,即待删除节点为root
 {
  if(root->lchild==NULL&&root->rchild==NULL)    //检查是否为叶子节点
  {
   leaf=del=true;                            //将leaf、del赋为真,向上层传递删除节点信息
   if(Root==root) Root=NULL;                 //如果删除的节点是全树的根节点,则将全树根节点指针置为空
   delete root;                              //删除该节点
   shorter=true;                             //当前子树高度减小
  }
  else                             //不是叶子节点
  {
   if(root->lchild==NULL)//左子树为空时  (左为空右一定不为空,否则就是叶子)
   {
    p=root;                  // 将p指向root
    root=root->rchild;       // 将root的右子树挂到root上
    delete(p);               // 删除p所指节点
    shorter=true;            // 当前子树高度减小
   }
   else //左子树不为空时
   {
    p=f=root->lchild;         // 将p,f指向root的左孩子
    while(p->rchild)          // 左转向右到底
    {
     f=p;                  //f为p的前驱
     p=p->rchild;          //p向右子树走
    }
    if(p==f)                      //此时p没有右子树
    {//将root的左子树根节点补上来做新的root,删除以前的root
     p=root;                   //将p指向root
     root=f;                   //将root指向f
     root->rchild=p->rchild;   //将p的右子树挂到新root的右子树
     if(p->bf==0)//检查原树根的平衡因子
     {
      shorter=false;        //当前树高度没有减小
      root->bf=-1;          //更新当前树根的平衡因子
     }
     else if(p->bf==1)         
     {
      shorter=true;         //当前树高度减小
      root->bf=0;           //更新平衡因子
     }
     else
     {
      root->bf=p->bf-1;     //更新平衡因子
         RightBalance(root);   //此时相当于右子树增加节点
      shorter=true;         //当前树高度减小
     }
     delete p;                 //删除待删节点
    }
    else
    {// 此时待删除节点与左子树最右边的节点更换,再删除最右边的节点
     root->data=p->data;       //更换两节点的数据
     f->rchild=p->lchild;      //将p的左子树挂到其前驱f的右子树上
     delete p;                 //删除p所指的结点
     if(f->bf==0)              //检查f平衡因子
     {
      shorter=false;        //当前以f为根的子树高没发生变化
      f->bf=1;              //更新f的平衡因子
     }
     else if(f->bf==1)
     {
      LeftBalance(root->lchild);//当前以f为根的子树进行左平衡处理(相当于左边增加节点)
      shorter=true;
     }
     else
     {
      shorter=true;           //以f 为根的子树平衡未被破坏,但高度减小
      f->bf=0;                //更新f的平衡因子
     }
     if(shorter)                 //当以f 为根的子树树高减小时,进行平衡处理
     {//此这程类似上述过程
      if(root->bf==0)
      {
       shorter=false;
       root->bf=-1;
      }
      else if(root->bf==1)
      {
       shorter=true;
       root->bf=0;
      }
      else
      {
       RightBalance(root);//相当于右边增加
       shorter=true;
      }
     }
    }
   }
  }
 }
 else if(data<root->data)        //待删除的数据小于当前树根数据
 {
  BBT_Del(root->lchild,data,shorter,suc,del,leaf);   //递归,在以root左子树根中继续调用本函数
  if(del&&leaf)                       //删除的是叶子节点
  {
   root->lchild=NULL;              //当前树根左子树指针置为空
   del=false;                      //更新 del的值
  }
  if(shorter)                        //shorter为真,树高减小,分析平衡因子,进行平衡处理
  {
   if(root->bf==0)
   {
    root->bf=-1;
    shorter=false;
   }
   else if(root->bf==1)
   {
    root->bf=0;
    shorter=true;
   }
   else
   {
    RightBalance(root);
    shorter=true;
   }
  }
 }
 else//待删除的数据大于当前树根数据
 {
  BBT_Del(root->rchild,data,shorter,suc,del,leaf);
  if(del&&leaf)
  {
   del=false;
   root->rchild=NULL;
  }
  if(shorter)
  {
   if(root->bf==0)
   {
    root->bf=1;
    shorter=false;
   }
   else if(root->bf==1)
   {
    LeftBalance(root);//
    shorter=true;
   }
   else
   {
    root->bf=0;
    shorter=true;
   }
  }
 }
}

 //查找平衡因子
int Find_BF(B_Point root,int data)            
{
 if(!root)
  return 100;//100表示不存在,以用表示查找失败
 if(data==root->data)  
  return root->bf;                        //找到该数据节点,返回平衡因子
 else if(data<root->data)                    //否则递归调用
  return Find_BF(root->lchild,data);
 else return Find_BF(root->rchild,data);
}

//中序遍历
void Traverse(B_Point root)
{
 if(root)//当前根节点不为空
 {
  Traverse(root->lchild);           //在左子树中递归
  printf("%d ",root->data);         //显示当前节点为数据
  Traverse(root->rchild);           //在右子树中递归
 }
}

//获取树高
void GetTreeHeight(B_Point root,int TreeHeight,int & MaxHeight)
{
 if(root)                                               //当前根节点不为空
 {
  TreeHeight++;                                      //树高加1
  if(TreeHeight>MaxHeight) MaxHeight=TreeHeight;     //与树高最大值比较
  GetTreeHeight(root->lchild,TreeHeight,MaxHeight);  //在左子树中递归
  GetTreeHeight(root->rchild,TreeHeight,MaxHeight);  //在右子树中递归
 }
}



可是这些程序没办法实现题中的要求啊!再次向各位讨教!谢谢!

2010-05-07 12:53
快速回复:平衡二叉树的编程
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.033010 second(s), 10 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved