数据结构C语言课程设计平衡二叉树

1， 利用平衡二叉树实现一个动态查找表，实现动态查找表的三种基本功能：查找，插入、删除和附加的两种功能：合并、分裂平衡二叉树。 2， 操作界面要给创建、查找、插入、删除、合并和分裂六种操作供选择。每种操作均要提示输入关键字。每次插入和删除一个节点后，应更新平衡二叉树的显示。该二叉树的显示采用凹入表形式。

#include
#include
#include
#include
#define TRUE  1
#define FALSE 0
#define LH +1  //左高
#define RH -1  //右高 
#define EH 0   //等高

typedef struct ElemType{
	int   key;
}ElemType;
typedef struct BSTNode{
	ElemType        data;
    int            bf;                 //结点的平衡因子
    struct BSTNode  *lchild*rchild;    //左右孩子指针
}BSTNode*BSTree;

void  menu（）
{printf（“        @@@@@@@@@@@@@@@@@@@@@@@平衡二叉树操作的演示@@@@@@@@@@@@@@@@@@@@@@\n“）;     //主界面函数
 printf（“        @                                                               @\n“）;
 printf（“        @                      1.创建树                                 @\n“）;
 printf（“        @                      2.查找元素                               @\n“）;
 printf（“        @                      3.插入元素                               @\n“）;
 printf（“        @                      4.删除元素                               @\n“）;
 printf（“        @                      5.合并树                                 @\n“）;
 printf（“        @                      6.分裂树                                 @\n“）;
 printf（“        @                      0.退出                                   @\n“）;
 printf（“        @                                                               @\n“）;
 printf（“        @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@\n“）;
 printf（“\n请选择（0----6）：“）;
}
 
void DispTree（BSTree Tint iint j）{  //树的打印输出
	if（T->rchild） 
		DispTree（T->rchildi+4j）;
	for（j=1;j<=i;j++） printf（“ “）;
	   printf（“%d“T->data.key）;
	   printf（“（“）; printf（“%d“T->bf）; printf（“）“）;
	   printf（“\n“）;
	  if（T->lchild） 
		  DispTree（T->lchildi+4j）;
}

void R_Rotate（BSTree &p） { 
  // 对以*p为根的二叉排序树作右旋处理，处理之后p指向新的树根结点即旋转处理之前的左子树的根结点
  BSTree lc;
  lc = p->lchild;            // lc指向*p的左子树根结点
  p->lchild = lc->rchild;    // lc的右子树挂接为*p的左子树
  lc->rchild = p;  p = lc;   // p指向新的根结点
} 

void L_Rotate（BSTree &p） {  
  // 对以p↑为根的二叉排序树作左旋处理，处理之后p指向新的树根结点即旋转处理之前的右子树的根结点
  BSTree rc;
  rc = p->rchild;            // rc指向*p的右子树根结点
  p->rchild = rc->lchild;    // rc的左子树挂接为*p的右子树
  rc->lchild = p;  p = rc;   // p指向新的根结点
} 


void RightBalance（BSTree &T） {  
  // 对以指针T所指结点为根的二叉树作右平衡旋转处理， 本算法结束时，指针T指向新的根结点
  BSTree rcld;
  rc = T->rchild;    // rc指向*T的右子树根结点
  switch （rc->bf） {  // 检查*T的右子树的平衡度，并作相应平衡处理
    case RH:   // 新结点插入在*T的右孩子的右子树上，要作单右旋处理
        T->bf = rc->bf = EH; 
        L_Rotate（T）;   
        break;  
    case LH:      // 新结点插入在*T的右孩子的左子树上，要作双旋处理
        ld = rc->lchild;// ld指向*T的右孩子的左子树根
        switch （ld->bf） {// 修改*T及其右孩子的平衡因子
          case LH: T->bf = LH;  rc->bf = EH;break;
          case EH: T->bf = rc->bf = EH;break;
          case RH: T->bf = EH;  rc->bf = RH;break;
        } 
        ld->bf = EH;   	
        R_Rotate（T->rchild）;// 对*T的右子树作右旋平衡处理
        L_Rotate（T）; break; // 对*T作左旋平衡处理
	case EH:
	    rc->bf=LH;
		L_Rotate（T）; 
  }  
} 



void LeftBalance（BSTree &T） {  
  // 对以指

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件      50176  2010-05-27 21:23  课程设计（平衡二叉树）\Debug\vc60.idb

     文件      61440  2010-05-10 15:41  课程设计（平衡二叉树）\Debug\vc60.pdb

     文件     221247  2010-05-27 21:23  课程设计（平衡二叉树）\Debug\平衡二叉树.exe

     文件     288384  2010-05-27 21:23  课程设计（平衡二叉树）\Debug\平衡二叉树.ilk

     文件      25186  2010-05-27 21:23  课程设计（平衡二叉树）\Debug\平衡二叉树.obj

     文件     280856  2010-05-09 23:32  课程设计（平衡二叉树）\Debug\平衡二叉树.pch

     文件     607232  2010-05-10 15:41  课程设计（平衡二叉树）\Debug\平衡二叉树.pdb

     文件      12204  2010-05-10 14:46  课程设计（平衡二叉树）\平衡二叉树.cpp

     文件       3451  2010-05-27 21:23  课程设计（平衡二叉树）\平衡二叉树.dsp

     文件        528  2010-05-27 21:26  课程设计（平衡二叉树）\平衡二叉树.dsw

     文件      50176  2010-05-27 21:26  课程设计（平衡二叉树）\平衡二叉树.ncb

     文件      48640  2010-05-27 21:26  课程设计（平衡二叉树）\平衡二叉树.opt

     文件        766  2010-05-27 21:23  课程设计（平衡二叉树）\平衡二叉树.plg

     文件     177664  2011-05-05 22:16  课程设计（平衡二叉树）\报告.doc

     目录          0  2011-05-05 22:15  课程设计（平衡二叉树）\Debug

     目录          0  2011-05-05 22:18  课程设计（平衡二叉树）

----------- ---------  ---------- -----  ----

              1827950                    16