平衡树源代码（有自己的注释）.doc

《平衡树源代码（有自己的注释）.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、#include#include#include#include"string"#includeusingnamespacestd;templateclassavlnode{public:Tdata;intheight;avlnode*left;avlnode*right;avlnode():height(0),left(0),right(0){}avlnode(Titem):height(0),data(item),left(0),righ

2、t(0){}};templateclassavltree{private:ofstreamouter;avlnode*root;vectorallitem;intgetheight(avlnode*target);//获取节点的高度信息vector&inorder2(avlnode*target);//把所有的节点存储到一个向量中并返回向量的引用voidinsert(avlnode*&target,Titem);//插入数据boolsearch(avlnode*root,Titem)

3、;//查找数据voidleftrotate(avlnode*&target);//左旋voidrightrotate(avlnode*&target);//右旋voidlrrotate(avlnode*&target);//左右旋voidrlrotate(avlnode*&target);//右左旋voiddeletenode(avlnode*&target,Titem);//删除节点voidinorder(avlnode*target);//中序遍历voidseebalence(avlnode*targ

4、et);//查看平衡度voidshowtree(avlnode*target,intdepth);//显示树voidshowheight(avlnode*target,intdepth);//显示高度voidshowinout(avlnode*target,intdepth);//把树显示到外部文件public:avltree():root(NULL){}//构造函数voidinsert(Titem);//插入节点的接口voidshowinout();//显示到外部文件vector&inorder2();//把节点的数据放

5、到向量并返回的接口boolsearch(Titem);//查找数据的接口voiddeletenode(Titem);//删除数据的接口voidshowheight();//显示高度的接口voidinorder();//中序遍历的接口voidseebalence();//查看平衡度的接口voidshowtree();//显示树到外部文件的接口intmax(inta,intb);//max函数};templateintavltree::getheight(avlnode*target){//得到node的height

6、值if(target==0)return-1;elsereturntarget->height;}templatevoidavltree::leftrotate(avlnode*&target){avlnode*temp=target;//新建一个节点指针把target保存target=target->right;//target指针指向target的右孩子avlnode*temp2=target->left;//新建一个指针保存当前的target的做孩子target->left=temp;//当前t

7、arget的左孩子置为原来的targettemp->right=temp2;//原来target的右孩子置为temp2target->height=max(getheight(target->left),getheight(target->right))+1;//可以发现，只有两个点的高度发生变化了temp->height=max(getheight(temp->left),getheight(temp->right))+1;}templatevoidavltree::rightrotate(avlnode*&t

8、arget){//同左旋avlnode*temp=target;target=target->left;avlnode*te