平衡二叉树的c语言实现

本代码用c语言实现了平衡二叉树这一数据结构，同时实现了基本查找，插入，删除操作，都是自己精心设计的算法，花了很多功夫。。

#include“iostream.h“
#include“BBstree.h“
#include“stdlib.h“
BBstree Search（BBstree &TKeytype key）
{   //在平衡二叉排序树中查找与key值相同的关键字，若存在则函数返回相应的不为空的指针，
	//否则返回空指针
	if（!T||（key==T->key））
		return T;
	else if（keykey）
		return Search（T->lchildkey）;  //递归在左子树中进行查找
	else
		return Search（T->rchildkey）;  //递归在右子树中进行查找
}
void L_Rotate（BBstree &p）
{  //对以*p为根的二叉排序树作左旋处理，处理之后p指向新的树根结点，及旋转处理之前的树的右子树的根结点
	BBstree rc=p->rchild; //rc指向*p的右子树的根结点
	p->rchild=rc->lchild; //rc的左子树挂接为*p的右子树
	rc->lchild=p; //p挂接在rc的左子树上
	p=rc;  //p指向新的根结点
}
void R_Rotate（BBstree &p）
{  //对以*p为根的二叉排序树作右旋处理，处理之后p指向新的树根结点，及旋转处理之前的树的左子树的根结点
	BBstree lc=p->lchild; //rc指向*p的左子树的根结点
	p->lchild=lc->rchild; //rc的右子树挂接为*p的左子树
	lc->rchild=p; //p挂接在rc的右子树上
	p=lc;  //p指向新的根结点
}
void LeftBalance（BBstree &T）
{ //对以指针T所指结点为根的二叉树作左平衡旋转处理，算法结束时，指针T指向新的根结点
	BBstree lcrd;
	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=lc->bf=EH;
					  break;
					 }
			 case RH:{
				      T->bf=EH;
					  lc->bf=LH;
					  break;
					 }
			 }
			 rd->bf=EH;
			 L_Rotate（T->lchild）;  //对*T的左子树作左旋平衡处理
			 R_Rotate（T）;  //对*T作右旋平衡处理
			}
	}
}
void LeftBalance1（BBstree &Tbool &taller）
{//原本T所指结点的平衡因子为1删除T的右孩子后作左平衡旋转处理，算法结束时，指针T指向新的根结点
	BBstree lcrd;
	lc=T->lchild;  //lc指向*T的左子树根结点
	switch（lc->bf）  //检查*T的左子树的平衡度，并做相应平衡处理
	{
	case LH:{  //T的左孩子平衡因子为1相应的对T作右旋处理使T保持平衡
		     T->bf=lc->bf=EH;
			 R_Rotate（T）;
			 taller=true;//对T而言树变矮
			 break;
			}
	case EH:{  //T的左孩子平衡因子为0相应的对T作右旋处理使T保持平衡
		     T->bf=LH;
			 lc->bf=RH;
			 R_Rotate（T）;
			 taller=false;//对T而言树没变矮
			 break;
			}
	case RH:{  //T的左孩子平衡因子为-1相应的对T作右旋处理使T保持平衡
		     rd=lc->rchild;  //rd指向*T的左孩子的右子树根
			 switch（rd->bf）  //修改*T及其左孩子的平衡因子
			 {
			 case LH:{//T平衡因子变为-1T的左孩子变为0	
				      T->bf=RH;
					  lc->bf=EH;
					  break;
					 }
			 case EH:{//T平衡因子变为0T的左孩子变为0	
				      T->bf=lc->bf=EH;
					  break;
					 }
			 case RH:{//T平衡因子变为0T的左孩子变为1
				      T->bf=EH;
					  lc->bf=LH;
					  break;
					 }
			 }
			 rd->bf=EH;
			 L_Rotate（T->lchild）;  //对*T的左子树作左旋平衡处理
			 R_Rotate（T）;//对*T作右旋平衡处理
			 taller=true;//对T而言树变矮
			}
	}
}
void RightBalance（BBstree &T）
{ //对以指针T所指结点为根的二叉树作右平衡旋转处理，算法结束时，指针T指向新的根结点
	BBstree 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=EH;
					  rc->bf=RH;
				

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

     文件       4428  2008-12-18 22:22  BBstree\BBstree.dsp

     文件        522  2008-12-16 22:20  BBstree\BBstree.dsw

     文件       1537  2008-12-29 18:04  BBstree\BBstree.h

     文件      66560  2010-10-26 17:58  BBstree\BBstree.ncb

     文件      48640  2010-10-26 17:58  BBstree\BBstree.opt

     文件        927  2010-03-13 23:16  BBstree\BBstree.plg

     文件      12002  2008-12-29 20:32  BBstree\BBstree_hanshu.cpp

     文件       1496  2009-01-04 17:32  BBstree\BBstree_main.cpp

     文件     217174  2010-03-13 23:16  BBstree\Debug\BBstree.exe

     文件     252360  2010-03-13 23:16  BBstree\Debug\BBstree.ilk

     文件      43520  2008-12-28 15:49  BBstree\Debug\BBstree.opt

     文件     256300  2010-03-13 23:16  BBstree\Debug\BBstree.pch

     文件     549888  2010-03-13 23:16  BBstree\Debug\BBstree.pdb

     文件      18407  2009-01-04 17:32  BBstree\Debug\BBstree_hanshu.obj

     文件      10701  2010-03-13 23:16  BBstree\Debug\BBstree_main.obj

     文件      74752  2010-03-13 23:16  BBstree\Debug\vc60.idb

     文件      61440  2010-03-13 23:16  BBstree\Debug\vc60.pdb

     目录          0  2011-10-15 00:53  BBstree\Debug

     目录          0  2011-10-15 00:53  BBstree

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

              1620654                    19