平衡二叉树所涉及的一些算法

今晚整那个ubuntu，什么也没弄成，唉，把算法先保留一下吧， 插入函数还没理解透彻呢

#include<stdio.h> #include<stdlib.h>#define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define NULL 0typedef int Status; typedef int ElemType; typedef int KeyType;typedef struct BSTNode{ElemType data;int bf; //结点平衡因子BSTNode *lchild, *rchild; //左右孩子指针 }BSTNode, *BSTree;Status InitBSTree(BSTree &BT) //初始化 {//操作结果：构造一个空的动态查找表BTBT=NULL;return OK; }//InitBSTreeStatus DestroyBSTree(BSTree &BT) //销毁 {//初始条件：动态表已经存在。操作结果：销毁动态查找表BTif(BT) //非空树{if(BT->lchild) //有左孩子DestroyBSTree(BT->lchild); //递归法销毁左孩子子树if(BT->rchild) //有右孩子DestroyBSTree(BT->rchild); //递归法消去右孩子子树free(BT); //释放根结点BT=NULL;}//ifreturn OK; }//DestroyBSTreeBSTree SearchBSTree(BSTree T, KeyType key) //查找 {//在根指针T所指平衡二叉树中递归地查找某关键字等于key的数据元素//若查找成功，则返回指向该数据元素结点的指针，否则返回空指针。if(!T){if(key == T->data)return T; //查找结束；else if(key < T->data)return SearchBSTree(T->lchild, key); //在左子树中查找else if(key > T->data)return SearchBSTree(T->rchild, key); //在右子树中查找}//if }//SearchBSTreeStatus R_Rotate(BSTree &p) //右旋 {//对以*p为根的二叉树作右旋处理，处理之后p指向新的树根结点，//即指向处理前的左子树的根结点（p的左孩子结点）BSTree lc;lc=p->lchild; //lc指向左子树的根结点p->lchild = lc->rchild; //lc的右子树挂接为p的左子树lc->rchild =p;p=lc; //p指向新的根结点return OK; }//R_RotateStatus L_Rotate(BSTree &p) //左旋 {BSTree rc;rc=p->rchild;p->rchild = rc->lchild;rc->lchild=p;p=rc;return OK; }//L_Rotate#define LH +1 //左高 #define EH 0 //等高 #define RH -1 //右高Status LeftBalance(BSTree &T) //左平衡旋转处理 {//对以指针T所指结点为根的二叉树作左平衡处理，//T指向新根结点BSTree lc, rd;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;}//switchrd->bf=EH;L_Rotate(T->lchild);//对*T的左子树做左旋平衡处理R_Rotate(T); //对*T做右旋处理}//switchreturn OK; }//LeftBalanceStatus RightBalance(BSTree &T) //右平衡旋转处理 {//对以T所指向的结点为根二叉树做右平衡处理，//T指向新的根结点BSTree rc, rd;rc=T->rchild; //rc指向T的右子树根结点switch(rc->bf){//检查*T的右子树的平衡度，并作相应平衡处理case RH: //新结点插入在右子树右子树上，单向左旋T->bf=rc->bf=EH;L_Rotate(T);break;case LH: //新结点插入在右子树的左子树上，双选处理rd=rc->lchild;//rd指向右子树的座子树根switch(rd->bf){//修改*T及其右孩子的平衡因子case RH: T->bf=LH;rc->bf=EH;break;case EH: T->bf=rc->bf=EH;break;case LH: T->bf=EH;rc->bf=RH;}//switchrd->bf=EH;R_Rotate(T->rchild);//右子树右旋L_Rotate(T); //对*T作左旋平衡处理}//switchreturn OK; }//RightBalanceStatus InsertElem(BSTree &T, ElemType e, Status &taller) {//若不存在e则插入，返回1；否则返回0；若插入后失衡，则作相应平衡处理//taller记录树长高与否if(!T){//插入新结点树长高，则置taller为TRUET=(BSTree)malloc(sizeof(BSTNode));T->data=e;T->lchild=T->rchild=NULL;T->bf=EH;taller=TRUE;}else{if(e == T->data){//存在相同结点，则不插入taller=FALSE;return FALSE;}//ifif(e < T->data){//应继续在T的左子树中搜索if(!InsertElem(T->lchild, e, taller))//未插入return FALSE;if(taller) //已插入，且左子树长高{switch(T->bf)//检查*T的平衡度{case LH://原本左高，需左平衡处理LeftBalance(T);taller=FALSE;break;case EH: //原本等高，左增高则树增高T->bf=LH;taller=TRUE;break;case RH: //原本右高，则左右等高taller=FALSE;}//switch}//ifelse{//应在T的右子树中搜索if(!InsertElem(T->rchild, e, taller))//未插入return FALSE;if(taller){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;}}}}}return OK;}

 

转载于:https://www.cnblogs.com/java0721/archive/2011/12/06/2602924.html

总结

以上是生活随笔为你收集整理的平衡二叉树所涉及的一些算法的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。