C/C++实现AVL树（二叉平衡搜索树）
一开始以为很复杂很可怕，后来自己想了一下其实也没那么可怕，无非就是左右子树的顺序调换而已。
有关AVL的旋转的原理就不再说明，不懂自行百度查书了解旋转原理。
以下是部分代码实现AVL树
首先是树的结构的构建
struct tree { struct tree* ls; //左儿子 struct tree* rs; //右儿子 int siz,con,data,height; //大小，内容，数据，高度 }; typedef struct tree stu; typedef struct tree* ptr;
下面是旋转的代码实现
1.左单旋与右单旋
什么时候单旋不再说明了，自行百度查书了解各种情况。
void left(ptr* now){ //左旋 ptr tmp=(*now)->rs; //其实本质就是左右儿子的替换 (*now)->rs=tmp->ls; tmp->ls=*now; tmp->siz=(*now)->siz; pushup(*now),pushup(tmp); *now=tmp; return; }
void right(ptr* now){ //右旋 ptr tmp=(*now)->ls; (*now)->ls=*now; tmp->siz=(*now)->siz; pushup(*now),pushup(tmp); *now=tmp; return; }
2.插入、平衡、刷新过程
平衡这一部分的代码是AVL的核心
其实也就是比普通二叉搜索树多了一个平衡的操作而已
写出二叉搜索树，再加上平衡操作就行了
总的来说就是插入->平衡->刷新
void ins(ptr* now,int num) //其实仔细分辨的话，也只是比二叉搜索树多了一些判断和平衡而已 { if (*now==NULL) { *now=(ptr)malloc(sizeof(stu)); (*now)->siz=(*now)->con=1; (*now)->data=num,(*now)->height=0; (*now)->ls=(*now)->rs=NULL; return; } if ((*now)->data==num) { (*now)->con++; pushup(*now); return; } if ((*now)->data>num) ins(&(*now)->ls,num); else ins(&(*now)->rs,num); pushup(*now); balance(now); return; }
void balance(ptr *now) //进行平衡的操作 对于不同情况的调用 { if (*now==NULL) return; if (h((*now)->ls)-h((*now)->rs)==2) { if (h((*now)->ls->ls)>h((*now)->ls->rs)) right(now); else left(&(*now)->ls),right(now); return; } if (h((*now)->rs)-h((*now)->ls)==2) { if (h((*now)->rs->rs)>h((*now)->rs->ls)) left(now); else right(&(*now)->rs),left(now); return; } return; }
void pushup(ptr now){ //进行重新刷新 相当于树的重建过程 if(now==NULL) return; //刷新当前树的高度，数据内容等 now->height=1; now->siz=now->con; now->siz+=size(now->ls); now->siz+=size(now->rs); if(h(now->ls)>h(now->ls)) now->height+=h(now->ls); else now->height+=h(now->rs); return; }
3.删除节点后的平衡
void del(ptr* now,int num) { if (*now==NULL) return; if ((*now)->data==num) { if ((*now)->con>1) (*now)->con--; else { ptr cng=*now; if ((*now)->ls==NULL) *now=(*now)->rs,free(cng); else if ((*now)->rs==NULL) *now=(*now)->ls,free(cng); else { cng=(*now)->rs; while (cng->ls) cng=cng->ls; (*now)->data=cng->data; (*now)->con=cng->con,cng->con=1; del(&(*now)->rs,cng->data); } } } else { if ((*now)->data>num) del(&(*now)->ls,num); else del(&(*now)->rs,num); } pushup(*now); balance(now); return; }
4.打印AVL树的结点
1.前序遍历
void print(ptr p) { printf("data:%d,con:%d,",p->data,p->con); printf("siz:%d,h:%d ",p->siz,p->height); return; } void printfst(ptr now) { if (now) { print(now); if (now->ls) printfst(now->ls); if (now->rs) printfst(now->rs); } else printf("NULL"); return; }
2.中序遍历
void printmid(ptr now) { if (now) { if (now->ls) printmid(now->ls); print(now); if (now->rs) printmid(now->rs); } else printf("NULL"); return; }
3.后序遍历
void printlst(ptr now) { if (now) { if (now->ls) printlst(now->ls); if (now->rs) printlst(now->rs); print(now); } else printf("NULL"); return; }
5.总结
这个是链表实现的AVL树，后期会补充上数组实现AVL树，
总的来说，并不算太难，比起复杂的图的递归，这个确实比较明确，就是旋转->平衡->刷新的过程。
往后也会补充上双旋的过程。
也欢迎大家一起学习交流。
