二叉树的应用详解 - 数据结构_数据结构-二叉树及其应用

Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p){  
	//在根指针T所指二叉排序樹中递归地查找其关键字等于key的数据元素，若查找成功，  
	//则指针p指向该数据元素节点，并返回TRUE，否则指针P指向查找路径上访问的  
	//最好一个节点并返回FALSE，指针f指向T的双亲，其初始调用值为NULL  
	if(!T){ p=f; return FALSE;} //查找不成功  
	else if EQ(key, T->data.key) {P=T; return TRUE;} //查找成功  
	else if LT(key,T->data.key)   
		return SearchBST(T->lchild, key, T, p); //在左子树继续查找  
	else return SearchBST(T->rchild, key, T, p); //在右子树继续查找  
}  

Status DeleteBST(BiTree &T, KeyType key){  
	//若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素，并返回  
	//TRUE；否则返回FALSE   
	if(!T) return FALSE;    //不存在关键字等于key的数据元素  
	else{  
		if(EQ(key, T->data.key)) {return Delete(T)};     找到关键字等于key的数据元素  
		else if(LT(key, T->data.key))    return DeleteBST(T->lchild, key);  
		else return DeleteBST(T->rchild, key);  
	}  
}  
Status Delete(BiTree &p){  
	//从二叉排序树中删除结点p，并重接它的左或右子树   
	if(!p->rchild){  //右子树空则只需重接它的左子树  
		q=p; p=p->lchild;    free(q);  
	}  
	else if(!p->lchild){ //左子树空只需重接它的右子树  
		q=p; p=p->rchild; free(q);  
	}  
	else{   //左右子树均不空  
		q=p;   
		s=p->lchild;  
		while(s->rchild){   
			q=s;   
			s=s->rchild  
		}   //转左，然后向右到尽头  
		p->data = s->data;    //s指向被删结点的“前驱”  
		if(q!=p)      
			q->rchild = s->lchild; //重接*q的右子树  
		else   
			q->lchild = s->lchild;    //重接*q的左子树  
		free(s);  
	}  
	return TRUE;  
}  
 

typedef struct  BSTNode {  
	ElemType    data;  
	int     bf;     //结点的平衡因子  
	struct BSTNode  *lchild, *rchild;     
	//左、右孩子指针  
} BSTNode, * BSTree;  
void R_Rotate (BSTree &p) {  
	//对以*p为根的二叉排序树作右旋处理，处理之后p指向新的树根结点，   
	//即旋转处理之前的左子树的根结点   
	lc = p－>lchild;          //lc指向的*p的左子树根结点  
	p－>lchild = lc－>rchild;       //lc的右子树挂接为*p的左子树  
	lc－>rchild = p;    
	p = lc;             //p指向新的根结点  
} // R_Rotate   
 
void L_Rotate (BSTree &p) {  
	//对以*p为根的二叉排序树作左旋处理，处理之后p指向新的树根结点，  
	//即旋转处理之前的右子树的根结点   
	rc = p－>rchild;          //rc指向的*p的右子树根结点  
	p－>rchild = rc－>lchild;       //rc的左子树挂接为*p的右子树  
	rc－>lchild = p;    
	p = rc;             //p指向新的根结点   
} // L_Rotate   
 
 
 
#define LH  +1      //左高   
#define EH  0       //等高   
#define RH  -1      //右高   
 
 
 
Status InsertAVL (BSTree &T, ElemType e, Boolean &taller) {  
	//若在平衡的二叉排序树T中不存在和e有相同关键字的结点，则插入   
	//一个数据元素为e的新结点，并返回1，否则返回0。若因插入而使二  
	//叉排序树失去平衡，则作平衡旋转处理，布尔变量taller反映T长高  
	//与否。   
	if (!T) {      //插入新结点，树“长高”，置taller为TRUE  
		T = (BSTree) malloc (sizeof (BSTNode));  
		T－>data = e;  
		T－>lchild = T－>rchild = NULL;  
		taller = TRUE;  
	}  
	else {  
		if (EQ(e.key, T－>data.key))      //树中已存在和e有相同关键字的  
		{taller = FALSE; return 0;}     //结点则不再插入  
		if (LT(e.key, T－>data.key)) {        //应继续在*T的左子树中进行搜索  
			if (!InsertAVL(T－>lchild, e, taller))    //未插入  
				return  0;  
			if (taller)         //已插入到*T的左子树中且左子树“长高”  
				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;  
			} // switch (T－>bf)  
		} // if   
		else {      //应继续在*T的右子树中进行搜索  
			if (!InsertAVL(T－>rchild, e, taller))        //未插入  
				return  0;  
			if (taller)     //已插入到*T的右子树中且右子树“长高”  
				switch (T－>bf) { //检查*T的平衡度  
				case LH:        //原本右子树比左子树高，现左、右子树等高  
					T－>bf = EH;  
					taller = FALSE;  
					break;  
				case EH:    //原本左右子树等高，现因右子树增高而使树增高  
					T－>bf = RH;  
					taller = TRUE;  
					break;  
				case RH:        //原本右子树比左子树高，需要作右平衡处理     
					RightBalance (T);  
					taller = FALSE;  
					break;  
			} // switch (T－>bf)   
		} // else   
	} // else   
	return  1;   
} // InsertAVL   
 
 
void LeftBalance (BSTree &T) {  
	//对以指针T所指结点为根的二叉树作左平衡旋转处理，本算法   
	//结束时，指针T指向新的根结点   
	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;  
				} // switch (rd－>bf)   
				rd－>bf = EH;  
				L_Rotate (T－>lchild);   //对*T的左子树作左旋平衡处理  
				R_Rotate (T);      //对*T作右旋平衡处理  
	} // switch (lc－>bf)   
} // LeftBalance