AVL二叉平衡树C+实现

1、/以下是AVL平衡二叉树的实现头文件，基本思想请见维斯的数据结构与算法分析该书提供了构建此树的基本思想，只是没有提供删除节点的算法。本代码删除节点并保持平衡的基本思想是（递归实现）：先找到被删除节点，若为叶节点则直接删除，否则选取删除节点的左子树的的最大值代替该删除节点。不同于增加节点的是，删除节点后，在沿着原轨迹一直到根节点时候，对每个节点都要进行平衡性的检查，若不平衡则需要旋转，注意，旋转后有两种结果，一种是旋转后高度与之前节点的高度一致，那么从此节点再往根节点的所有的所有节点都将平衡，不会再对它们进行旋转，。另外一种是旋转后该节点左右子树平衡，但是比之前高度少了一层，此时要沿着轨迹一直旋

2、转到根节点，直到旋转后发生第一种情况为止。若每个节点旋转后一直到根节点都不能使节点高度与原来一致，那么到根节点为止，整个树的的高度便降低了一层#ifndef TREE_H#define TREE_Htemplateclass Tree;template class TreeNodepublic:TreeNode(T value)data=value;leftPtr=rightPtr=0;height=0;/一半在插入节点的时候会初始化新节点，而该节点一开始肯定被插入到叶出，而叶节点的高度为0；T getData()return data;T data;int height;/节点的高度Tree

3、Node* leftPtr;TreeNode* rightPtr;templateclass Tree/此为AVL二叉平衡树public:Tree()rootTreeNode=0;Tree()destroyHelper(rootTreeNode);TreeNode* treeSearch(T value);/搜索二叉树的值，并返回指向该值的指针，如果树内无该值，返回一个空指针void outputTree();/形象地打印出树（图）void insertTreeNode(T);/插入数值void inOrederTraversal();/中序遍历打印树void deleteValue(T);/

4、删除节点private:/以下四个函数为插入节点后的旋转函数，以维持树的平衡void rotateLeft(TreeNode* &);void rotateRight(TreeNode* &);/必须改变该节点的指向，所以为引用void doubleRotateLeft(TreeNode* &);void doubleRotateRight(TreeNode* &);/删除节点的两个辅助函数void deleteHelper1(TreeNode* &,T);T deleteHelper2(TreeNode* &,T);/测量节点高度的函数int high(TreeNode* );/返回节点高度

5、较大值的函数int max(int s1,int s2)return s1s2?s1:s2;/为实现递归原理相应的工具函数void outputTreeHelper(TreeNode*,int);void destroyHelper(TreeNode*);TreeNode* searchHelper(TreeNode*,T);TreeNode* rootTreeNode;void insertHelper(TreeNode* &,T);void inHelper(TreeNode*);templatevoid Tree:deleteValue(T value)if(rootTreeNode!=

6、0) deleteHelper1(rootTreeNode,value);templateT Tree:deleteHelper2(TreeNode* &nodePtr,T value)T retVal;if(nodePtr-leftPtr!=0)retVal=deleteHelper2(nodePtr-leftPtr,value);if(high(nodePtr-rightPtr)-high(nodePtr-leftPtr)=2)if(high(nodePtr-rightPtr-leftPtr)high(nodePtr-rightPtr-rightPtr)doubleRotateRight(

7、nodePtr);elserotateRight(nodePtr);nodePtr-height=max(high(nodePtr-leftPtr),high(nodePtr-rightPtr)+1;elseretVal=nodePtr-data;TreeNode* temp=nodePtr;nodePtr=nodePtr-rightPtr=0?0:nodePtr-rightPtr;delete temp;return retVal;templatevoid Tree:deleteHelper1(TreeNode* &nodePtr,T value)if(nodePtr=0)/找不到该数值co

8、utendldatarightPtr,value);if(high(nodePtr-leftPtr)-high(nodePtr-rightPtr)=2)/由于在右边删除了一个节点出现不平衡if(high(nodePtr-leftPtr-rightPtr)high(nodePtr-leftPtr-leftPtr)doubleRotateLeft(nodePtr);elserotateLeft(nodePtr);/相等或者大于else if(valuedata)deleteHelper1(nodePtr-leftPtr,value);if(high(nodePtr-rightPtr)-high(n

9、odePtr-leftPtr)=2)if(high(nodePtr-rightPtr-leftPtr)high(nodePtr-rightPtr-rightPtr)doubleRotateRight(nodePtr);elserotateRight(nodePtr);elseif(nodePtr-rightPtr=0)TreeNode* temp=nodePtr;nodePtr=nodePtr-leftPtr;delete temp;else if(nodePtr-leftPtr=0)TreeNode* temp=nodePtr;nodePtr=nodePtr-rightPtr;delete

10、temp;elsenodePtr-data=deleteHelper2(nodePtr-rightPtr,value); if(high(nodePtr-leftPtr)-high(nodePtr-rightPtr)=2)/由于在右边删除了一个节点出现不平衡 if(high(nodePtr-leftPtr-rightPtr)high(nodePtr-leftPtr-leftPtr) doubleRotateLeft(nodePtr); else rotateLeft(nodePtr);/相等或者大于 if(nodePtr!=0) nodePtr-height=max(high(nodePtr-

11、leftPtr),high(nodePtr-rightPtr)+1;templatevoid Tree:rotateLeft(TreeNode* &nodePtr)TreeNode* temp=nodePtr-leftPtr;nodePtr-leftPtr=temp-rightPtr;nodePtr-height=max(high(nodePtr-leftPtr),high(nodePtr-rightPtr)+1;temp-rightPtr=nodePtr;nodePtr=temp;nodePtr-height=max(high(nodePtr-leftPtr),high(nodePtr-ri

12、ghtPtr)+1;templatevoid Tree:rotateRight(TreeNode* &nodePtr)TreeNode* temp=nodePtr-rightPtr;nodePtr-rightPtr=temp-leftPtr;nodePtr-height=max(high(nodePtr-leftPtr),high(nodePtr-rightPtr)+1;temp-leftPtr=nodePtr;nodePtr=temp;nodePtr-height=max(high(nodePtr-leftPtr),high(nodePtr-rightPtr)+1;templatevoid

13、Tree:doubleRotateLeft(TreeNode* &nodePtr)rotateRight(nodePtr-leftPtr);rotateLeft(nodePtr);templatevoid Tree:doubleRotateRight(TreeNode* &nodePtr)rotateLeft(nodePtr-rightPtr);rotateRight(nodePtr);templateint Tree:high(TreeNode* nodePtr)return nodePtr=0?-1:nodePtr-height;templateTreeNode* Tree:treeSea

14、rch(T value)return searchHelper(rootTreeNode,value);templateTreeNode* Tree:searchHelper(TreeNode* nodePtr,T value)/使用递归实现搜索TreeNode* retPtr=0;if(nodePtr=0)return retPtr;if(valuedata)return searchHelper(nodePtr-leftPtr,value);if(valuenodePtr-data)return searchHelper(nodePtr-rightPtr,value);return nod

15、ePtr;/这种if的测试应该把最不可能的结果放在最后进行。templatevoid Tree:insertTreeNode(T value)insertHelper(rootTreeNode,value);templatevoid Tree:insertHelper(TreeNode* &nodePtr,T value)if(nodePtr=0)nodePtr=new TreeNode(value);elseif(valuedata)insertHelper(nodePtr-leftPtr,value);if(high(nodePtr-leftPtr)-high(nodePtr-rightP

16、tr)=2)if(valueleftPtr-data)rotateLeft(nodePtr);elsedoubleRotateLeft(nodePtr);else if(nodePtr-datarightPtr,value);if(high(nodePtr-rightPtr)-high(nodePtr-leftPtr)=2)if(valuerightPtr-data)doubleRotateRight(nodePtr);elserotateRight(nodePtr);else /如果value=nodePtr-data；因为是重复，所以直接无视掉；(空操作；;/更新高度nodePtr-hei

17、ght=max(high(nodePtr-leftPtr),high(nodePtr-rightPtr)+1;templatevoid Tree:inOrederTraversal()inHelper(rootTreeNode);templatevoid Tree:inHelper(TreeNode* nodePtr)if(nodePtr=0)return;inHelper(nodePtr-leftPtr);cout data;inHelper(nodePtr-rightPtr);templatevoid Tree:destroyHelper(TreeNode* nodePtr)if(nodePtr=0)return;destroyHelper(nodePtr-leftPtr);destroyHelper(nodePtr-rightPtr);delete nodePtr;templatevoid Tree:outputTree()coutendl;if(rootTreeNode!=0) outputTreeHelper(roo