1、平衡二叉樹AVL操作模板這篇文章主要介紹了平衡二叉樹AVL操作*II板，需要的朋友可以參考下復(fù)制代碼代碼如下:/* 目的：實(shí)現(xiàn)AVLacm 模板* 利用數(shù)組對(duì)左右兒子簡(jiǎn)化代碼，但是對(duì)腦力難度反而增大不少，只適合* 其實(shí)avl在acm中基本不用，基本被treap取代* avl一般只要求理解思路，不要求寫出代碼，因?yàn)檎嫘暮軣?/#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<string>#include<time.h>

2、;#include<queue>usingnamespacestd;intCOUNT;/統(tǒng)計(jì)樹中不重復(fù)節(jié)點(diǎn)的個(gè)數(shù)intHEIGHT;/統(tǒng)計(jì)數(shù)的高度/數(shù)據(jù)節(jié)點(diǎn)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的節(jié)點(diǎn)template<classT>classAVLNodeprivate:inthgt;/節(jié)點(diǎn)的高度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是節(jié)點(diǎn)中的數(shù)據(jù)類型template<classT>classAVLTreeprivate:AVLNode<T>*root;/根節(jié)點(diǎn)inthgt;/樹的高度intsize;/樹中不重復(fù)節(jié)點(diǎn)數(shù)量void_insert(AVLNode<T>*&cur,Tdata);void_mid_travel(AVLNode<T>*cur);/層次遍歷void_cengci_travel(AVLNode<T>*cur);/單旋轉(zhuǎn)(左左，右右),左旋不是想左旋轉(zhuǎn)的意思，而是由于左子樹的左兒子的高度

7、太大/與treap的旋轉(zhuǎn)命名相反void_singleRoate(AVLNode<T>*&cur,intdir);/雙旋轉(zhuǎn)(兩次單旋轉(zhuǎn))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);/層次遍歷，/如果節(jié)點(diǎn)為空就輸出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)/用#代表該節(jié)點(diǎn)是空，#的后代還是#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;/單旋轉(zhuǎn)，即只旋轉(zhuǎn)一次/dir=0時(shí),左左旋轉(zhuǎn)；否則為右右旋轉(zhuǎn)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();/雙旋轉(zhuǎn)，即調(diào)兩次單旋轉(zhuǎn)/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