二叉树排序树建立及平衡处理

１本程序在vc++6.0编译通过并能正常运行。 ２主界面 程序已经尽量做到操作简便了，用户只需要根据提示一步步进行操作就行了。 六思考和总结： 这个课程设计的各个基本操作大部分都在我的综合性实验中实现了，所以做这个主要攻克插入和删除这两个算法！其中插入在书本上已经有了，其中的右平衡算法虽然没有给出，但通过给出的左平衡算法很容易就可以写出右平衡算法。所以最终的点就在于删除算法的实现！做的过程中对插入算法进行了非常非常多次的尝试！花了非常多的时间，这其中很多时候是在对程序进行单步调试，运用了ＶＣ６。０的众多良好工具，也学到了很多它的许多好的调试手段。 其中删除算法中最难想到的一点是：在用叶子结点代替要删除的非叶子结点后，应该递归的运用删除算法去删除叶子结点！这就是整个算法的核心，其中很强烈得体会到的递归的强大，递归的最高境界（我暂时能看到的境界）！ 其它的都没什么了。选做的那两个算法很容易实现的： １合并两棵平衡二叉排序树：只需遍历其中的一棵，将它的每一个元素插入到另一棵即可。 ２拆分两棵平衡二叉排序树：只需以根结点为中心，左子树独立为一棵，右子树独立为一棵，最后将根插入到左子树或右子树即可。 BSTreeEmpty(BSTree T) 初始条件：平衡二叉排序树存在。 操作结果：若T为空平衡二叉排序树，则返回TRUE,否则FALSE. BSTreeDepth(BSTree T) 初始条件：平衡二叉排序树存在。 操作结果：返回T的深度。 LeafNum(BSTree T) 求叶子结点数，非递归中序遍历 NodeNum(BSTree T) 求结点数，非递归中序遍历 DestoryBSTree(BSTree *T) 后序遍历销毁平衡二叉排序树T R_Rotate(BSTree *p) 对以*p为根的平衡二叉排序树作右旋处理，处理之后p指向新的树根结点 即旋转处理之前的左子树的根结点 L_Rotate(BSTree *p) 对以*p为根的平衡二叉排序树作左旋处理，处理之后p指向新的树根结点， 即旋转处理之前的右子树的根结点 LeftBalance(BSTree *T) 对以指针Ｔ所指结点为根的平衡二叉排序树作左平衡旋转处理， 本算法结束时，指针Ｔ指向新的根结点 RightBalance(BSTree *T) 对以指针Ｔ所指结点为根的平衡二叉排序树作右平衡旋转处理， 本算法结束时，指针Ｔ指向新的根结点 Insert_AVL(BSTree *T, TElemType e, int *taller) 若在平衡的二叉排序树Ｔ中不存在和e有相同的关键字的结点， 则插入一个数据元素为e的新结点，并返回OK,否则返回ERROR. 若因插入而使二叉排序树失去平衡，则作平衡旋转处理 布尔变量taller反映Ｔ长高与否 InOrderTraverse(BSTree T) 递归中序遍历输出平衡二叉排序树 SearchBST(BSTree T, TElemType e, BSTree *f, BSTree *p) 在根指针Ｔ所指的平衡二叉排序树中递归的查找其元素值等于e的数据元素， 若查找成功，则指针p指向该数据元素结点，并返回TRUE，否则指针p 指向查找路径上访问的最后一个结点并返回FALSE，指针f指向Ｔ的双亲， 其初始调用值为NULL Delete_AVL(BSTree *T, TElemType e, int *shorter) 在平衡二叉排序树中删除元素值为e的结点,成功返回OK,失败返回ERROR PrintBSTree_GList(BSTree T) 以广义表形式打印出来 PrintBSTree_AoList(BSTree T, int length) 以凹入表形式打印,length初始值为0 Combine_Two_AVL(BSTree *T1, BSTree T2) 合并两棵平衡二叉排序树 Split_AVL(BSTree T, BSTree *T1, BSTree *T2) 拆分两棵平衡二叉树 } (2)存储结构的定义： typedef struct BSTNode { TElemType data; int bf; //结点的平衡因子 struct BSTNode *lchild, *rchild;//左.右孩子指针 }BSTNode, *BSTree;

#define MAX_NUM 100
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define Status int
#define LH 1  //左高
#define RH -1 //右高
#define EH 0  //等高
#define TETYPE “%c“
#define TElemType char
#include 
#include 
#include 
#include 
typedef struct BSTNode
{
	TElemType data;
	int      bf;                    //结点的平衡因子
	struct BSTNode *lchild *rchild;//左.右孩子指针
}BSTNode *BSTree;
//***********基本操作***************************************
void Visit（BSTree T）
{
	printf（TETYPE T->data）;
	printf（“（%d）“ T->bf）;
	printf（“ “）;
}
Status BSTreeEmpty（BSTree T）
//初始条件：平衡二叉排序树存在。
//操作结果：若T为空平衡二叉排序树，则返回TRUE否则FALSE.
{
	return （T ? FALSE : TRUE）;
}
int BSTreeDepth（BSTree T）
//初始条件：平衡二叉排序树存在。操作结果：返回T的深度。
{
	int L_depthR_depth;
	if（T==NULL）
		return 0;
	else
	{
		if（T->lchild）
			L_depth = BSTreeDepth（T->lchild）;
		else
			L_depth = 0;
		if（T->rchild）
			R_depth = BSTreeDepth（T->rchild）;
		else
			R_depth=0;
		return （L_depth >= R_depth ? L_depth : R_depth）+1;
	}
}
int LeafNum（BSTree T）
//求叶子结点数，非递归中序遍历
{
	BSTree s[MAX_NUM]; int i=0num=0; BSTree p;

	if（T）
	{
		s[i++]=T;
		while（i）
		{
			while（（p=s[i-1]）&&p）
				s[i++]=p->lchild;
			--i;//空指针出
			if（i）
			{
				p=s[--i];
				if（!p->lchild&&!p->rchild）
				{
					num++;
					Visit（p）;
					putchar（‘ ‘）;
				}
				s[i++]=p->rchild;
			}
		}
	}
	return num;
}
int NodeNum（BSTree T）
//求结点数，非递归中序遍历
{
	BSTree s[MAX_NUM]; int i=0num=0; BSTree p;

	if（T）
	{
		s[i++]=T;
		while（i）
		{
			while（（p=s[i-1]）&&p）
				s[i++]=p->lchild;
			--i;//空指针出
			if（i）
			{
				p=s[--i];
				num++;
				s[i++]=p->rchild;
			}
		}
	}
	return num;
}
void DestoryBSTree（BSTree *T）
//后序遍历销毁平衡二叉排序树T
{
	if（*T）
	{
		if（（*T）->lchild）
			DestoryBSTree（&（*T）->lchild）;
		if（（*T）->rchild）
			DestoryBSTree（&（*T）->rchild）;
		free（*T）;
		*T = NULL;
	}
}
void R_Rotate（BSTree *p）
{//对以*p为根的平衡二叉排序树作右旋处理，处理之后p指向新的树根结点
 //即旋转处理之前的左子树的根结点
	BSTree lc = NULL;

	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 = NULL;

	rc = （*p）->rchild;        //rc指向*p的右子树根结点
	（*p）->rchild = rc->lchild;//rc的左子树挂接为*p的右子树
	rc->lchild = *p;        
	*p = rc;                //p指向新的根结点
}
void LeftBalance（BSTree *T）
{//对以指针Ｔ所指结点为根的平衡二叉排序树作左平衡旋转处理，
 //本算法结束时，指针Ｔ指向新的根结点
	BSTree lc = NULL rd = NULL;

	lc = （*T）->lchild;   //lc指向*T的左子树的树根结点
	switch（lc->bf）       //检查*T的左子树的平衡度，并作相应的平衡处理
	{
	case LH:             //新结点插入在*T的左孩子的左子树上，要作单右旋处理
		（*T）->bf = lc->bf = EH;
		R_Rotate（T）;
		break;
	case RH:             //新结点插入在*T的左孩子的右子树上，要作双旋处理
		rd = lc->rchild; //rd指向*T的左孩子的右子树的根
		switch（rd->bf）   //根据其的平衡度，修改*T及其左孩子的平衡因子
		{
		case LH:
			（*T）->bf = RH;
			lc->bf = EH;
			break;
		case EH:
			（*T）->bf = l

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

     文件      20360  2009-12-22 16:15  b.c

     文件     188452  2009-12-22 16:10  b.exe

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

               208812                    2