本文共 3773 字，大约阅读时间需要 12 分钟。
真是惭愧呀，又双㕛叕鸽了好几天了，这段时间把查找基本看完了，比较基础的二叉排序树呀，平衡二叉树呀，哈斯表呀，都了解得差不多，这次实现的是平衡二叉树这种数据结构，说老实话，真的挺麻烦的。上次的那个二叉排序树在构建的过程中可能让树的结构不好，导致查找的效率不高。所以整了个平衡调整方法，就是加了一个平衡因子，每个结点的平衡因子的绝对值不能大于1，这样就使得树的结构始终很好，但是真正调整的时候还是很麻烦，基本上有四种不平衡的状态，分为四个类型，这个在书上都可以找到。理解了之后我突然觉得用代码实现确实不容易，所以就照着《大话数据结构》这本书和CSDN上面copy了一份，以后要是有用得着的地方就可以直接看过来，hhh
/*C语言实现平衡二叉树*/#include#include #define LH 1#define EH 0#define RH -1typedef struct BiTNode{ int data; int bf;//增加一个数据元素存储平衡因子，它的取值范围是{-1,0,1} struct BiTNode *lchild,*rchild;}BiTNode,*BiTree; void InorderTraverse(BiTree T){ //中序遍历二叉树 if(NULL==T) return ; InorderTraverse(T->lchild); printf("%d ",T->data); InorderTraverse(T->rchild);}//对以P为根的二叉排序树作右旋处理 void R_Rotate(BiTree *P){ BiTree L; L=(*P)->lchild;//L指向P的左子树根结点 (*P)->lchild=L->rchild;//L的右子树挂接为P的左子树 L->rchild=(*P); *P=L;//P指向新的根结点 } //对以P为根的二叉排序树作左旋处理 void L_Rotate(BiTree *P){ BiTree R; R=(*P)->rchild;//R指向P的右子树根结点 (*P)->rchild=R->lchild;//R的左子树挂接为P的右子树 R->lchild=(*P); *P=R;//P指向新的根结点 } //对以T为根节点的二叉树作左平衡旋转处理void LeftBalance(BiTree *T){ BiTree L,Lr; L=(*T)->lchild;//L指向T的左子树根结点 switch(L->bf) { //检查T的左子树平衡度，并作相应平衡处理 case LH://新结点插入在T的左孩子的左子树上，要作单右旋处理 (*T)->bf=L->bf=EH; R_Rotate(T); break; case RH://新结点插入在T的左孩子的右子树上，要作双旋处理 Lr=L->rchild; switch(Lr->bf)//修改T及其左孩子的平衡因子 { case LH: (*T)->bf=RH; L->bf=EH; break; case EH: (*T)->bf=L->bf=EH; break; case RH: (*T)->bf=EH; L->bf=LH; break; } Lr->bf=EH; L_Rotate(&(*T)->lchild); R_Rotate(T); } } //对以T为根节点的二叉树作右平衡旋转处理void RightBalance(BiTree *T){ BiTree R,Rl; R=(*T)->rchild; switch(R->bf) { //检查T的右子树平衡度，并作相应平衡处理 case RH://新结点插入在T的左孩子的左子树上，要作单右旋处理 (*T)->bf=R->bf=EH; L_Rotate(T); break; case LH://新结点插入在T的左孩子的右子树上，要作双旋处理 Rl=R->lchild; switch(Rl->bf)//修改T及其左孩子的平衡因子 { case RH: (*T)->bf=LH; R->bf=EH; break; case EH: (*T)->bf=R->bf=EH; break; case LH: (*T)->bf=EH; R->bf=RH; break; } Rl->bf=EH; R_Rotate(&(*T)->rchild); L_Rotate(T); } } //若在平衡的二叉排序树T中不存在和e有相同关键字的结点，则插入一个数据元素为e的新结点并返回1，否则返回0//若因插入而使二叉排序树失去平衡，则做平衡旋转处理，变量taller反应T长高与否int InsertAVL(BiTree *T,int e,int *taller){ if(!*T) { //插入新结点，树长高，置taller为1 *T=(BiTree)malloc(sizeof(BiTNode)); (*T)->data=e; (*T)->lchild=(*T)->rchild=NULL; (*T)->bf=EH; *taller=1; } else { if(e==(*T)->data) { //树中已存在和e相同关键字的结点则不再插入 *taller=0; return 0; } if(e<(*T)->data) { //应继续在T的左子树中进行搜索 if(!InsertAVL(&(*T)->lchild,e,taller))//未插入 return 0; if(*taller)//已插入到T的左子树中且左子树“长高” { switch((*T)->bf) { case LH://原本左子树比右子树高，需要作左平衡处理 LeftBalance(T); *taller=0; break; case EH://原本左右子树等高，现因左子树增高而树增高 (*T)->bf=LH; *taller=1; break; case RH://原本右子树比左子树高，现左右子树等高 (*T)->bf=EH; *taller=0; break; } } } else { //应继续在T的右子树中进行搜索 if(!InsertAVL(&(*T)->rchild,e,taller)) return 0; if(*taller)//已插入到T的右子树中且右子树“长高” { switch((*T)->bf) { case LH://原本左子树比右子树高，现左右子树等高 (*T)->bf=EH; *taller=0; break; case EH://原本左右子树等高，现因右子树增高而树增高 (*T)->bf=RH; *taller=1; break; case RH://原本右子树比左子树高，需要作右平衡处理 RightBalance(T); *taller=0; break; } } } } return 1; } int main(){ int i,j; int a[10]={ 3,2,1,4,5,9,7,10,9,8}; BiTree T=NULL; int taller; for(i=0;i<10;i++) { j=InsertAVL(&T,a[i],&taller); if(j==1) printf("第%d个数插入成功\n",i+1); else printf("第%d个数插入失败\n",i+1); } printf("构建平衡二叉树后,中序遍历结果如下:\n "); InorderTraverse(T); system("pause"); return 0;}
还有3个星期课程就结束了，我这个学期重学数据结构的计划完成到现在也刚好渐入尾声，总的来说还是进步不小，自己的多多少少看了也敲了这些代码，对自己的编程能力有了进一步提高。而且愈接近数据结构，愈觉得它的用处很大。以后还要深入算法的学习，这个就是基础！ 加油吧，持之以恒！！！
转载地址：http://cstki.baihongyu.com/