平衡二叉树AVL操作模板模板

1、平衡二叉树AVL操作模板这篇文章主要介绍了平衡二叉树AVL操作*II板，需要的朋友可以参考下复制代码代码如下:/* 目的：实现AVLacm 模板* 利用数组对左右儿子简化代码，但是对脑力难度反而增大不少，只适合* 其实avl在acm中基本不用，基本被treap取代* avl一般只要求理解思路，不要求写出代码，因为真心很烦*/#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<string>#include<time.h>

2、;#include<queue>usingnamespacestd;intCOUNT;/统计树中不重复节点的个数intHEIGHT;/统计数的高度/数据节点classDNodepublic:intdata;DNode():data(0);DNode(intd):data(d)booloperator=(constDNode&d)returndata=d.data;booloperator=(constDNode&d)returndata=d.data;booloperator>(constDNode&d)returndata>d.data;boo

3、loperator<(constDNode&d)returndata<d.data;voidshow()cout<<endl;cout <<"*"<< endl;cout<<"data:"<<data<<endl;/treap的节点template<classT>classAVLNodeprivate:inthgt;/节点的高度public:Tdata;intcount;AVLNode<T>*son2;/0是左儿子，1是右儿子AVLNode

4、<T>(Tdata):data(data),count(1)son0=son1=NULL;hgt=1;intmax(inta,intb)returna>b?a:b;voidshow()data.show();cout<<"chgt:"<<this->height()<<endl;cout<<"lhgt:"<<this->son0->height()<<endl;cout<<"rhgt:"<<this-&g

5、t;son1->height()<<endl;cout<<"count:"<<count<<endl;cout<<endl;intheight()if(NULL=this)return0;return_getHeight(this);int_getHeight(AVLNode<T>*cur)if(NULL=cur)return0;return1+max(_getHeight(cur->son0),_getHeight(cur->son1);voidsetHeight()hgt=_get

6、Height(this);/AVLTree/这里的T是节点中的数据类型template<classT>classAVLTreeprivate:AVLNode<T>*root;/根节点inthgt;/树的高度intsize;/树中不重复节点数量void_insert(AVLNode<T>*&cur,Tdata);void_mid_travel(AVLNode<T>*cur);/层次遍历void_cengci_travel(AVLNode<T>*cur);/单旋转(左左，右右),左旋不是想左旋转的意思，而是由于左子树的左儿子的高度

7、太大/与treap的旋转命名相反void_singleRoate(AVLNode<T>*&cur,intdir);/双旋转(两次单旋转)void_doubleRoate(AVLNode<T>*&cur,intdir);intmax(inta,intb)returna>b?a:b;public:AVLTree():root(NULL),hgt(0)voidinsert(constT&data);voidmid_travel();intheight()returnroot->height();/层次遍历voidcengci_travel(

8、)_cengci_travel(root);/*私有方法开始*/template<classT>voidAVLTree<T>:_insert(AVLNode<T>*&cur,Tdata)if(NULL=cur)cur=newAVLNode<T>(data);elseif(data=cur->data)cur->count+;elseintdir=(data>cur->data);_insert(cur->sondir,data);if(2<=cur->sondir->height()-cur

9、->son!dir->height()boollr=(data>cur->data);lr?_singleRoate(cur,dir):_doubleRoate(cur,dir);cur->setHeight();/cout<<"setheight:"<<endl;/cur->show();template<classT>voidAVLTree<T>:_mid_travel(AVLNode<T>*cur)if(NULL!=cur)/先查找做子树_mid_travel(cur-&g

10、t;son0);/if(abs(cur->son0->height()-cur->son1->height()>=2)cur->show();_mid_travel(cur->son1);/层次遍历，/如果节点为空就输出0来占位template<classT>voidAVLTree<T>:_cengci_travel(AVLNode<T>*cur)if(NULL=cur)return;queue<AVLNode<T>*>q;q.push(cur);AVLNode<T>*top=NU

11、LL;queue<AVLNode<T>*>tmp;while(!q.empty()while(!q.empty()top=q.front();q.pop();if(NULL=top)/用#代表该节点是空，#的后代还是#cout<<'#'<<""tmp.push(top);elsecout<<top->data.data<<""tmp.push(top->son0);tmp.push(top->son1);boolflag=false;while(!e

12、mpty()if(NULL!=tmp.front()flag=true;q.push(tmp.front();tmp.pop();cout<<endl;if(!flag)break;/单旋转，即只旋转一次/dir=0时,左左旋转；否则为右右旋转template<classT>voidAVLTree<T>:_singleRoate(AVLNode<T>*&cur,intdir)AVLNode<T>*&k2=cur,*k1=k2->sondir;/k2必须是引用k2->sondir=k1->son!dir

13、;k1->son!dir=k2;k2=k1;k2->setHeight();k1->setHeight();/双旋转，即调两次单旋转/dir=0是左右情况；否则为右左情况template<classT>voidAVLTree<T>:_doubleRoate(AVLNode<T>*&cur,intdir)_singleRoate(cur->sondir,!dir);_singleRoate(cur,dir);/*公有方法（接口）开始*/template<classT>voidAVLTree<T>:inse

14、rt(constT&data)_insert(root,data);template<classT>voidAVLTree<T>:mid_travel()_mid_travel(root);intmain()AVLTree<DNode>*avlt=newAVLTree<DNode>();constintnum=30;for(inti=0;i<num;i+)DNode*d=newDNode(i);avlt->insert(*d);cout<<"*"<<endl;avlt->mid_travel();co