| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1580 人关注过本帖, 1 人收藏
标题:版主求助:排序平衡二叉树的编程!
只看楼主 加入收藏
ltxbs81
Rank: 1
等 级:新手上路
帖 子:11
专家分:0
注 册:2010-4-23
结帖率:66.67%
收藏(1)
已结贴  问题点数:20 回复次数:9 
版主求助:排序平衡二叉树的编程!
版主求助:排序平衡二叉树的编程!

小弟遇到了一道难题:
已知某排序平衡二叉树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 13:25
hzh512
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:6
帖 子:234
专家分:1333
注 册:2009-6-5
收藏
得分:10 
,解决不了,帮你顶一下!!

编程=用几种语言在某个或几个平台上通过抽象思维运用一系列算法来解决现实中问题的手段
2010-05-08 13:49
tfxanxing
Rank: 3Rank: 3
等 级:论坛游侠
威 望:2
帖 子:82
专家分:165
注 册:2010-5-7
收藏
得分:10 
     好复杂啊.................
2010-05-09 10:20
ltxbs81
Rank: 1
等 级:新手上路
帖 子:11
专家分:0
注 册:2010-4-23
收藏
得分:0 
还有没有高手帮忙解决啊。。。。有兴趣的过来研究吧!
2010-05-09 11:06
hzh512
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:6
帖 子:234
专家分:1333
注 册:2009-6-5
收藏
得分:0 
可以用穷尽的方法来做,可是复杂度太高 n!级的,做不了

编程=用几种语言在某个或几个平台上通过抽象思维运用一系列算法来解决现实中问题的手段
2010-05-09 11:26
ltxbs81
Rank: 1
等 级:新手上路
帖 子:11
专家分:0
注 册:2010-4-23
收藏
得分:0 
hzh512,您好!不知您有没有更简单一点的办法解小弟的那道题啊。。。有个网友说:“这是97年上海交大的数据结构考研真题啊!难怪这么难,不知网上有没有真题解析!
2010-05-09 13:54
hzh512
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:6
帖 子:234
专家分:1333
注 册:2009-6-5
收藏
得分:0 
嗯,目前正在想,想到了会发上来的

编程=用几种语言在某个或几个平台上通过抽象思维运用一系列算法来解决现实中问题的手段
2010-05-09 20:17
ltxbs81
Rank: 1
等 级:新手上路
帖 子:11
专家分:0
注 册:2010-4-23
收藏
得分:0 
hzh512,您好!小弟这几天一直在想这个问题,可是还没有解决的办法啊,太繁琐了。这位大哥要是能做出来就发给小弟一份吧!小弟前来好好学习研究。谢谢了!
邮箱:ltxbs81@
2010-05-10 13:05
寒风中的细雨
Rank: 17Rank: 17Rank: 17Rank: 17Rank: 17
等 级:贵宾
威 望:66
帖 子:1710
专家分:8645
注 册:2009-9-15
收藏
得分:0 
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

#define MAX 10
#define ADD 5

typedef struct BSTNode
{
    int data;
    int bf;
    int depth;
    struct BSTNode *lchild, *rchild;
}*BSTree;

typedef struct
{
    BSTree *base;
    BSTree *top;
    int stack_size;
}BST_Stack;

typedef struct
{
    BSTree *base;
    int front;
    int rear;
    int q_size;
}BST_Queue;

///////////队的基本操作/////////////////
void Init_Queue( BST_Queue &Q );
void Enter_Queue( BST_Queue &Q, BSTree temp );
void Delete_Queue( BST_Queue &Q, BSTree &temp );
int Empty_Queue( BST_Queue Q );
void Destroy_Queue( BST_Queue &Q );
///////////栈的操作///////////////////////
void Init_Stack( BST_Stack &S );
void Push_Stack( BST_Stack &S, BSTree temp );
void Pop_Stack( BST_Stack &S, BSTree &temp );
int Empty_Stack( BST_Stack S );

void Create( BSTree &T );//1 创建树
int Depth_AVL( BSTree &T );//2求树的深度
void BF_AVL( BSTree &T );//3求树的平衡因子
int Balance( BSTree T );//4判断树是否平衡//平衡返回1 否则返回0
void Print( BSTree T );//5打印树

void Traverse_AVL1( BSTree T, BST_Stack &S );//6将所有的叶子结点压入栈中
void Traverse_AVL2( BSTree T, BST_Stack &S );//7将所有的非叶子结点压入栈中
void Copy_AVL( BSTree T1, BSTree &T2 );//8将T1 复制到 T2
int Compare_AVL( BSTree T1, BSTree &T2 );//9 将树T1和T2比较 相同返回1 否则0
int Search_AVL( BSTree T, int i, BSTree &p );//10找到和i相同的返回1  否则0
int Searchf( BSTree T, BSTree &f, int p );//11查找p的双亲 找到就赋值为f 否则f为NULL
int Insert_AVL( BSTree &T, int i );//12如果i不是树的结点 则在树种插入结点i
void Delete_AVL( BSTree &T, int i );//13删除结点i 因为是插入后立即删除 所以不需要加判断 一定可以找到i
void Traverse_AVL3( BSTree T, BST_Stack &S );//14将所有的不平衡的点压入栈S中 层序遍历应用
void Change_AVL( BSTree &T );//15进行调整

int main()
{
    BSTree T1=NULL, T2=NULL, temp;
    BST_Stack S1;//叶子结点栈
    BST_Stack S2;//非叶子结点栈
    BST_Stack S3;
    int i, j1, j2, j3;

    Init_Stack( S1 );Init_Stack( S2 );Init_Stack( S3 );
   
    for( i=1; i<10; ++i )
    {
        if( Insert_AVL(T1, i) )//表示插入成功则执行
        {
            Depth_AVL( T1 );
            BF_AVL( T1 );
            while( !Balance( T1 ) )//直到平衡跳出循环
            {   
                Change_AVL( T1 );
                Depth_AVL( T1 );
                BF_AVL( T1 );
            }
            Traverse_AVL1( T1, S1 );//将所有的叶子结点入栈
            while( !Empty_Stack( S1 ) )//栈不空则往下执行
            {
                Copy_AVL( T1, T2 ); //赋值到T2
                Pop_Stack( S1, temp );
                j1 = temp->data;
                Delete_AVL( T1, j1 );//删除栈顶叶子结点
                Depth_AVL( T1 );
                BF_AVL( T1 );
                while( !Balance( T1 ) )//直到平衡跳出循环
                {
                    Change_AVL( T1 );
                    Depth_AVL( T1 );
                    BF_AVL( T1 );
                }
                Insert_AVL( T1, j1 );
                Depth_AVL( T1 );
                BF_AVL( T1 );
                while( !Balance( T1 ) )
                {
                    Change_AVL( T1 );
                    Depth_AVL( T1 );
                    BF_AVL( T1 );
                }
                if( !Compare_AVL( T1, T2 ) )//要是T1放生变化则往下执行
                {
                    Copy_AVL( T2, T1 );//还原T1
                    Traverse_AVL2( T1, S2 );//将所有的非叶子接的进栈
                    while( !Empty_Stack( S2 ) )
                    {
                        Pop_Stack( S2, temp );
                        j2 = temp->data;
                        Delete_AVL( T1, j2 );//~~~~
                        Depth_AVL( T1 );
                        BF_AVL( T1 );
                        while( !Balance( T1 ) )//直到平衡跳出循环
                        {
                            Change_AVL( T1 );
                            Depth_AVL( T1 );
                            BF_AVL( T1 );
                        }
                        Insert_AVL( T1, j2 );
                        Depth_AVL( T1 );
                        BF_AVL( T1 );
                        while( !Balance( T1 ) )//直到平衡跳出循环
                        {
                            Change_AVL( T1 );
                            Depth_AVL( T1 );
                            BF_AVL( T1 );
                        }
                        if( Compare_AVL( T1, T2 ) )//T1不花生改变则执行下
                        {
                            for( j3=1; j3<10; ++j3 )
                            {
                                if( Insert_AVL( T1, j3) )
                                {
                                    Depth_AVL( T1 );
                                    BF_AVL( T1 );
                                    while( !Balance( T1 ) )//直到平衡跳出循环
                                    {
                                        Change_AVL( T1 );
                                        Depth_AVL( T1 );
                                        BF_AVL( T1 );
                                    }
                                    Delete_AVL( T1, j3 );
                                    Depth_AVL( T1 );
                                    BF_AVL( T1 );
                                    while( !Balance( T1 ) )//直到平衡跳出循环
                                    {
                                        Change_AVL( T1 );
                                        Depth_AVL( T1 );
                                        BF_AVL( T1 );
                                    }
                                    if( !Compare_AVL( T1, T2) )//T1改变则执行下面
                                    {
                                        Print( T2 );printf("\n");
                                        printf("%d  %d   %d\n", j1, j2, j3);
                                    }
                                }
                                Copy_AVL( T2, T1 );
                            }
                            Copy_AVL( T2, T1);
                        }
                        Copy_AVL( T2, T1 );
                    }
                    Copy_AVL( T2, T1 );
                }
                Copy_AVL( T2, T1 );
            }
        }
    }

    return 0;
}

///////////
void Create( BSTree &T )
{
    int d;

    scanf("%d", &d);
    if(d == 0)
        T = NULL;
    else
    {
        T =(BSTree) malloc (sizeof(BSTree));
        T->lchild = T->rchild = NULL;
        T->data = d;
        Create( T->lchild );
        Create( T->rchild );
    }
}
//求树的深度
int Depth_AVL( BSTree &T )
{
    if( T )
    {
        return T->depth = Depth_AVL(T->rchild)>
            Depth_AVL(T->lchild)?Depth_AVL(T->rchild)+1
            :Depth_AVL(T->lchild)+1;
    }
    else
        return 0;
}
//求树的平衡因子
void BF_AVL( BSTree &T )
{
    if( T )
    {
        if( T->rchild && T->lchild )
            T->bf = T->lchild->depth
            - T->rchild->depth;
        else if( !T->rchild && T->lchild )
            T->bf = T->lchild->depth;
        else if( T->rchild && !T->lchild )
            T->bf = -T->rchild->depth;
        else if( !T->rchild && !T->lchild )
            T->bf = 0;
        BF_AVL( T->lchild );
        BF_AVL( T->rchild );
    }
}
//判断树是否平衡
int Balance( BSTree T )
{//平衡返回1 否则返回0
    if( T )
    {
        if( abs(T->bf) > 1 )
            return 0;
        else
            return Balance( T->rchild ) &
            Balance( T->lchild );
    }
    else
        return 1;
}

void Print( BSTree T )
{
    if(T)
    {
        printf("%d %d %d\n", T->data, T->depth, T->bf);
        Print( T->lchild );
        Print( T->rchild );
    }
}
///////////栈的操作///////////////////////
void Init_Stack( BST_Stack &S )
{
    S.base = (BSTree*) malloc (MAX*sizeof(BSTree));
    if( !S.base )
        exit(0);
    S.top = S.base;
    S.stack_size = MAX;
}

void Push_Stack( BST_Stack &S, BSTree temp )
{
    if( S.top - S.base >= S.stack_size )
    {
        S.base = (BSTree*) realloc (S.base, (ADD+S.stack_size)*sizeof(BSTree));
        S.top = S.base + S.stack_size;
        S.stack_size += ADD;
    }
    *S.top++ = temp;
}   

void Pop_Stack( BST_Stack &S, BSTree &temp )
{
    if( S.base == S.top )
        return;
    temp = *--S.top;
}

int Empty_Stack( BST_Stack S )
{
    if( S.base == S.top )
        return 1;
    else
        return 0;
}
/////////////
void Traverse_AVL1( BSTree T, BST_Stack &S )
{//将所有的叶子结点压入栈中
    if( T )
    {
        if( !T->lchild && !T->rchild )
            Push_Stack( S, T );
        Traverse_AVL1( T->lchild, S );
        Traverse_AVL1( T->rchild, S );
    }
}

void Traverse_AVL2( BSTree T, BST_Stack &S )
{//7将所有的非叶子结点压入栈中
    if( T )
    {
        if( T->lchild || T->rchild )
            Push_Stack( S, T );
        Traverse_AVL2( T->lchild, S );
        Traverse_AVL2( T->rchild, S );
    }
}

void Copy_AVL( BSTree T1, BSTree &T2 )
{//将T1 复制到 T2
    if( T1 )
    {
        T2 = (BSTree) malloc (sizeof(BSTree));
        T2->data = T1->data;
        T2->bf = T1->bf;
        T2->depth = T1->depth;
        T2->lchild = T2->rchild = NULL;
        Copy_AVL( T1->lchild, T2->lchild );
        Copy_AVL( T1->rchild, T2->rchild );
    }
}

int Compare_AVL( BSTree T1, BSTree &T2 )
{// 将树T1和T2比较 相同返回1 否则0
    if( T1 && T2 )
    {
        if( T1->data == T2->data )
        {
            return Compare_AVL( T1->lchild, T2->lchild )
                && Compare_AVL( T1->rchild, T2->rchild );
        }
        else
            return 0;
    }
    else if( !T1 && T2 )
        return 0;
    else if( !T2 && T1 )
        return 0;
    else
        return 1;
}

int Search_AVL( BSTree T, int i, BSTree &p )
{//找到和i相同的返回1  否则0
    if( T )
    {
        p = T;
        if( T->data == i )
            return 1;
        else if( i > T->data )
            return Search_AVL( T->rchild, i, p );
        else
            return Search_AVL( T->lchild, i, p );
    }
    else
        return 0;
}

int Searchf( BSTree T, BSTree &f, int p )
{//查找p的双亲 找到就赋值为f 否则f为NULL
    if( T )
    {
        if( T->data == p )
        {
            f = NULL;
            return 0;
        }
        else if( T->data > p )
        {
            if( T->lchild )
            {
                if( T->lchild->data == p )
                {
                    f = T;
                    return 1;
                }
                else
                    Searchf( T->lchild, f, p );
            }
            else
            {
                f = NULL;
                return 0;
            }
        }
        else
        {
            if( T->rchild )
            {
                if( T->rchild->data == p )
                {
                    f = T;
                    return 1;
                }
                else
                    Searchf( T->rchild, f, p );
            }
            else
            {
                f = NULL;
                return 0;
            }
        }
    }
    else
    {
        f = NULL;
        return 0;
    }
}

int Insert_AVL( BSTree &T, int i )
{//如果i不是树的结点 则在树种插入结点i
    BSTree p;

    if( !Search_AVL( T, i, p ) )//
    {
        BSTree temp;
        temp = (BSTree) malloc (sizeof(BSTree));
        temp->bf = 0;
        temp->data = i;
        temp->depth = 1;
        temp->lchild = temp->rchild = NULL;
        if( !T )
            T = temp;
        else if( p->data > i )
            p->lchild = temp;
        else
            p->rchild = temp;
        return 1;
    }
    else
        return 0;
}

void Delete_AVL( BSTree &T, int i )
{//删除结点i 因为是插入后立即删除 所以不需要加判断 一定可以找到i
    BSTree p, f = NULL;

    Search_AVL( T, i, p );
    Searchf( T, f, p->data );
    if( !p->rchild && !p->lchild )
    {
        if( f == NULL )
        {
            T = NULL;
        }
        else
        {
            if( f->data > i )
                f->lchild = NULL;
            else
                f->rchild = NULL;
        }
    }
    else if( !p->rchild && p->lchild )
    {
        if( f == NULL )//表示删除的为根结点
            T = T->lchild;
        else
        {
            if( f->data > i )
                f->lchild = p->lchild;
            else
                f->rchild = p->lchild;
        }
    }
    else if( !p->lchild && p->rchild )
    {
        if( f == NULL )
            T = T->rchild;
        else
        {
            if( f->data > i )
                f->lchild = p->rchild;
            else
                f->rchild = p->rchild;
        }
    }
    else
    {
        BSTree s, q;

        s = p->lchild;
        if( !s->rchild )
        {
            if( f == NULL )
                T = s;
            else
            {
                if( f->data > i )
                    f->lchild = s;
                else
                    f->rchild = s;
            }
            s->rchild = p->rchild;            
            
        }
        else
        {
            while( s->rchild )
            {
                q = s;
                s = s->rchild;
            }
            q->rchild = s->lchild;
            if( f == NULL )
                T = s;
            else
            {
                if( f->data > i )
                    f->lchild = s;
                else
                    f->rchild = s;
            }
            s->rchild = p->rchild;   
            s->lchild = p->lchild;        
        }
    }
}

///////////队的基本操作/////////////////
void Init_Queue( BST_Queue &Q )
{
    Q.base = (BSTree *) malloc (MAX*sizeof(BSTree));
    if( !Q.base )
        exit( 0 );
    Q.front = Q.rear = 0;
    Q.q_size = MAX;
}

void Enter_Queue( BST_Queue &Q, BSTree temp )
{
    if( Q.rear >=  Q.q_size-1 )
    {
        Q.base = ( BSTree * ) realloc (Q.base,(Q.q_size+ADD)*sizeof(BSTree));
        if( !Q.base )
            exit( 0 );
        Q.q_size += ADD;
    }
    Q.base[Q.rear++] = temp;
}

void Delete_Queue( BST_Queue &Q, BSTree &temp )
{
    if( Q.front == Q.rear )
        return ;
    temp = Q.base[Q.front++];
}

int Empty_Queue( BST_Queue Q )
{
    if( Q.front == Q.rear )
        return 1;
    else
        return 0;
}

void Destroy_Queue( BST_Queue &Q )
{
    if( Q.base )
    {
        free( Q.base );
        Q.front = Q.rear = 0;
        Q.q_size = 0;
    }
}

void Traverse_AVL3( BSTree T, BST_Stack &S )
{//将所有的不平衡的点压入栈S中 层序遍历应用
    BST_Queue Q;
    BSTree temp;

    Init_Queue( Q );
    if( T )
    {
        Enter_Queue( Q, T );
        while( !Empty_Queue( Q ) )
        {
            Delete_Queue( Q, temp );
            if( abs( temp->bf ) > 1 )
                    Push_Stack( S, temp );
            if( temp->lchild )
                Enter_Queue( Q, temp->lchild );
            if( temp->rchild )
                Enter_Queue( Q, temp->rchild );
        }
    }
}

void Change_AVL( BSTree &T )
{//进行调整
    BST_Stack S;//压入所有的不平衡点
    BSTree f = NULL;//如果不为NULL 就表示当前不平衡点的双亲
    BSTree p;//表示当前不平衡点
    BSTree pl, pr;//表示当前不平衡点的左、右孩子
    BSTree plr, prl;//表示当前不平衡点的左(右)孩子的右(左)孩子

    Init_Stack( S );
    Traverse_AVL3( T, S );
    Pop_Stack( S, p );
    Searchf( T, f, p->data );
    if( p->bf == 2 )//L
    {
        pl = p->lchild;
        plr = pl->rchild;
        if( f == NULL )
        {
            if( pl->bf == 1 )//L
            {
                p->lchild = pl->rchild;
                pl->rchild = p;
                T = pl;
            }
            else if( pl->bf == -1 )//R
            {
                p->lchild = plr->rchild;
                pl->rchild = plr->lchild;
                plr->rchild = p;
                plr->lchild = pl;
                T = plr;
            }
            else if( pl->bf == 0 )
            {
                p->lchild = pl->rchild;
                pl->rchild = p;
                T = pl;
            }
        }
        else
        {
            if( pl->bf == 1 )//L
            {
                p->lchild = pl->rchild;
                pl->rchild = p;
                if( f->data > p->data )
                    f->lchild = pl;
                else
                    f->rchild = pl;
            }
            else if( pl->bf == -1 )//R
            {
                p->lchild = plr->rchild;
                pl->rchild = plr->lchild;
                plr->rchild = p;
                plr->lchild = pl;
                if( f->data > p->data )
                    f->lchild = plr;
                else
                    f->rchild = plr;
            }
            else if( pl->bf == 0 )
            {
                p->lchild = pl->rchild;
                pl->rchild = p;
                if( f->data > p->data )
                    f->lchild = pl;
                else
                    f->rchild = pl;
            }
        }
    }
    else if( p->bf == -2 )//R
    {
        pr = p->rchild;
        prl = pr->lchild;
        if( f == NULL )
        {
            if( pr->bf == -1 )//R
            {
                p->rchild = pr->lchild;
                pr->lchild = p;
                T = pr;
            }
            else if( pr->bf == 1 )//L
            {
                p->rchild = prl->lchild;
                pr->lchild = prl->rchild;
                prl->lchild = p;
                prl->rchild = pr;
                T = prl;
            }
            else if( pr->bf == 0 )
            {
                p->rchild = pr->lchild;
                pr->lchild = p;
                T = pr;
            }
        }
        else
        {
            if( pr->bf == -1 )//R
            {
                p->rchild = pr->lchild;
                pr->lchild = p;
                if( f->data > p->data )
                    f->lchild = pr;
                else
                    f->rchild = pr;
            }
            else if( pr->bf == 1 )//L
            {
                p->rchild = prl->lchild;
                pr->lchild = prl->rchild;
                prl->lchild = p;
                prl->rchild = pr;
                if( f->data > p->data )
                    f->lchild = prl;
                else
                    f->rchild = prl;
            }
            else if( pr->bf == 0 )//
            {
                p->rchild = pr->lchild;
                pr->lchild = p;
                if( f->data > p->data )
                    f->lchild = pr;
                else
                    f->rchild = pr;
            }
        }
    }
}
2010-06-09 12:01
寒风中的细雨
Rank: 17Rank: 17Rank: 17Rank: 17Rank: 17
等 级:贵宾
威 望:66
帖 子:1710
专家分:8645
注 册:2009-9-15
收藏
得分:0 
图片附件: 游客没有浏览图片的权限,请 登录注册

调试 的一个
排序上面 要重新 设计下
2010-06-09 12:03
快速回复:版主求助:排序平衡二叉树的编程!
数据加载中...
 
   



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

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