数据结构C语言版 平衡二叉树.doc

数据结构C语言版 平衡二叉树83847,要看他的眼神;看一个人的身价,要看他的对手;看一个人的底牌,要看他的朋友。明天是世上增值最快的一块土地,因它充满了希望。/* 数据结构C语言版平衡二叉树 P236 编译环境:Dev-C++ 日期:2011年2月15日Forpersonaluseonlyinstudyandresearch;mercialuse*/#include<>Forpersonaluseonlyinstudyandresearch;mercialuse#include<>#defineLH+1 //左高Forpersonaluseonlyinstudyandresearch;mercialuse#defineEH0 //等高#defineRH-1 //右高#defineN5 //数据元素个数typedefcharKeyType;//设关键字域为字符型typedefstruct{ KeyTypekey; intorder;}ElemType;//数据元素类型//平衡二叉树的类型typedefstructBSTNode{ ElemTypedata; //bf结点的平衡因子,只能够取0,-1,1,它是左子树的深度减去 //右子树的深度得到的 intbf; structBSTNode*lchild,*rchild;//左、右孩子指针}BSTNode,*BSTree;//构造一个空的动态查找表DTintInitDSTable(BSTree*DT){ *DT=NULL; return1;}//销毁动态查找表DTvoidDestroyDSTable(BSTree*DT){ if(*DT)//非空树 { if((*DT)->lchild)//有左孩子 DestroyDSTable(&(*DT)->lchild);//销毁左孩子子树 if((*DT)->rchild)//有右孩子 DestroyDSTable(&(*DT)->rchild);//销毁右孩子子树 free(*DT);//释放根结点*DT=NULL;//空指针赋0 }}//(a)//在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素,//若查找成功,则返回指向该数据元素结点的指针,否则返回空指针。BSTreeSearchBST(BSTreeT,KeyTypekey){ if((!T)||(key==T->)) returnT;//查找结束 elseif(key<T->)//在左子树中继续查找 returnSearchBST(T->lchild,key); else returnSearchBST(T->rchild,key);//在右子树中继续查找}////对以*p为根的二叉排序树作右旋处理,处理之后p指向新的树根结点,即旋转//处理之前的左子树的根结点。voidR_Rotate(BSTree*p){ BSTreelc; lc=(*p)->lchild;//lc指向p的左子树根结点 (*p)->lchild=lc->rchild;//lc的右子树挂接为p的左子树 lc->rchild=*p; *p=lc;//p指向新的根结点}////对以*p为根的二叉排序树作