1 #include<iostream> 2 using namespace std; 3 4 5 6 //AVL树节点信息 7 template<class T> 8 class TreeNode 9 { 10 public: 11 TreeNode():lson(NULL),rson(NULL),freq(1),hgt(-1){} 12 T data;//值 13 int hgt;//高度 14 unsigned int freq;//频率 15 TreeNode* lson;//指向左儿子的地址 16 TreeNode* rson;//指向右儿子的地址 17 }; 18 //AVL树类的属性和方法声明 19 template<class T> 20 class AVLTree 21 { 22 private: 23 TreeNode<T>* root;//根节点 24 void insertpri(TreeNode<T>* &node,T x);//插入 25 TreeNode<T>* findpri(TreeNode<T>* node,T x);//查找 26 void insubtree(TreeNode<T>* node);//中序遍历 27 void pretree(TreeNode<T>* node);//先序遍历 28 void Deletepri(TreeNode<T>* &node,T x);//删除 29 int height(TreeNode<T>* node);//求树的高度 30 void SingRotateLeft(TreeNode<T>* &k2);//左左情况下的旋转 31 void SingRotateRight(TreeNode<T>* &k2);//右右情况下的旋转 32 void DoubleRotateLR(TreeNode<T>* &k3);//左右情况下的旋转 33 void DoubleRotateRL(TreeNode<T>* &k3);//右左情况下的旋转 34 int Max(int cmpa,int cmpb);//求最大值 35 36 public: 37 AVLTree():root(NULL){} 38 void get_root(TreeNode<T> *&r); 39 void insert(T x);//插入接口 40 TreeNode<T>* find(T x);//查找接口 41 void Delete(T x);//删除接口 42 void traversal();//遍历接口 43 44 }; 45 //计算节点的高度 46 template<class T> 47 int AVLTree<T>::height(TreeNode<T>* node) 48 { 49 if(node!=NULL) 50 return node->hgt; 51 return -1; 52 } 53 //返回根 54 template<class T> 55 void AVLTree<T>::get_root(TreeNode<T> *&r) 56 { 57 r=root; 58 } 59 //求最大值 60 template<class T> 61 int AVLTree<T>::Max(int cmpa,int cmpb) 62 { 63 return cmpa>cmpb?cmpa:cmpb; 64 } 65 //左左情况下的旋转 66 template<class T> 67 void AVLTree<T>::SingRotateLeft(TreeNode<T>* &k2) 68 { 69 TreeNode<T>* k1; 70 k1=k2->lson; 71 k2->lson=k1->rson; 72 k1->rson=k2; 73 74 k2->hgt=Max(height(k2->lson),height(k2->rson))+1; 75 k1->hgt=Max(height(k1->lson),k2->hgt)+1; 76 k2=k1; 77 } 78 //右右情况下的旋转 79 template<class T> 80 void AVLTree<T>::SingRotateRight(TreeNode<T>* &k2) 81 { 82 TreeNode<T>* k1; 83 k1=k2->rson; 84 k2->rson=k1->lson; 85 k1->lson=k2; 86 87 k2->hgt=Max(height(k2->lson),height(k2->rson))+1; 88 k1->hgt=Max(height(k1->rson),k2->hgt)+1; 89 k2=k1; 90 } 91 //左右情况的旋转 92 template<class T> 93 void AVLTree<T>::DoubleRotateLR(TreeNode<T>* &k3) 94 { 95 SingRotateRight(k3->lson); 96 SingRotateLeft(k3); 97 } 98 //右左情况的旋转 99 template<class T> 100 void AVLTree<T>::DoubleRotateRL(TreeNode<T>* &k3) 101 { 102 SingRotateLeft(k3->rson); 103 SingRotateRight(k3); 104 } 105 //插入 106 template<class T> 107 void AVLTree<T>::insertpri(TreeNode<T>* &node,T x) 108 { 109 if(node==NULL)//如果节点为空,就在此节点处加入x信息 110 { 111 node=new TreeNode<T>(); 112 node->data=x; 113 return; 114 } 115 if(node->data>x)//如果x小于节点的值,就继续在节点的左子树中插入x 116 { 117 insertpri(node->lson,x); 118 if(2==height(node->lson)-height(node->rson)) 119 if(x<node->lson->data) 120 SingRotateLeft(node); 121 else 122 DoubleRotateLR(node); 123 } 124 else if(node->data<x)//如果x大于节点的值,就继续在节点的右子树中插入x 125 { 126 insertpri(node->rson,x); 127 if(2==height(node->rson)-height(node->lson))//如果高度之差为2的话就失去了平衡,需要旋转 128 if(x>node->rson->data) 129 SingRotateRight(node); 130 else 131 DoubleRotateRL(node); 132 } 133 else ++(node->freq);//如果相等,就把频率加1 134 node->hgt=Max(height(node->lson),height(node->rson ))+1; 135 } 136 //插入接口 137 template<class T> 138 void AVLTree<T>::insert(T x) 139 { 140 insertpri(root,x); 141 } 142 //查找 143 template<class T> 144 TreeNode<T>* AVLTree<T>::findpri(TreeNode<T>* node,T x) 145 { 146 if(node==NULL)//如果节点为空说明没找到,返回NULL 147 { 148 return NULL; 149 } 150 if(node->data>x)//如果x小于节点的值,就继续在节点的左子树中查找x 151 { 152 return findpri(node->lson,x); 153 } 154 else if(node->data<x)//如果x大于节点的值,就继续在节点的左子树中查找x 155 { 156 return findpri(node->rson,x); 157 } 158 else return node;//如果相等,就找到了此节点 159 } 160 //查找接口 161 template<class T> 162 TreeNode<T>* AVLTree<T>::find(T x) 163 { 164 return findpri(root,x); 165 } 166 //删除 167 template<class T> 168 void AVLTree<T>::Deletepri(TreeNode<T>* &node,T x) 169 { 170 if(node==NULL) return ;//没有找到值是x的节点 171 if(x < node->data) 172 { 173 Deletepri(node->lson,x);//如果x小于节点的值,就继续在节点的左子树中删除x 174 if(2==height(node->rson)-height(node->lson)) 175 if(node->rson->lson!=NULL&&(height(node->rson->lson)>height(node->rson->rson)) )//右左的情况 176 DoubleRotateRL(node); 177 else //右右的情况 178 SingRotateRight(node); 179 } 180 181 else if(x > node->data) 182 { 183 Deletepri(node->rson,x);//如果x大于节点的值,就继续在节点的右子树中删除x 184 if(2==height(node->lson)-height(node->rson)) 185 if(node->lson->rson!=NULL&& (height(node->lson->rson)>height(node->lson->lson) )) //左右的情况 186 DoubleRotateLR(node); 187 else //左左的情况 188 SingRotateLeft(node); 189 } 190 191 else//如果相等,此节点就是要删除的节点 192 { 193 if(node->lson&&node->rson)//此节点有两个儿子 194 { 195 TreeNode<T>* temp=node->rson;//temp指向节点的右儿子 196 while(temp->lson!=NULL) temp=temp->lson;//找到右子树中值最小的节点 197 //把右子树中最小节点的值赋值给本节点 198 node->data=temp->data; 199 node->freq=temp->freq; 200 Deletepri(node->rson,temp->data);//删除右子树中最小值的节点 201 if(2==height(node->lson)-height(node->rson)) 202 { 203 if(node->lson->rson!=NULL&& (height(node->lson->rson)>height(node->lson->lson) )) 204 DoubleRotateLR(node); 205 else 206 SingRotateLeft(node); 207 } 208 } 209 else//此节点有1个或0个儿子 210 { 211 TreeNode<T>* temp=node; 212 if(node->lson==NULL)//有右儿子或者没有儿子 213 node=node->rson; 214 else if(node->rson==NULL)//有左儿子 215 node=node->lson; 216 delete(temp); 217 temp=NULL; 218 } 219 } 220 if(node==NULL) return;//当前节点0个儿子，删除后为NULL，直接退出，不用求hgt 221 node->hgt=Max(height(node->lson),height(node->rson))+1; 222 return; 223 } 224 //删除接口 225 template<class T> 226 void AVLTree<T>::Delete(T x) 227 { 228 Deletepri(root,x); 229 } 230 //先序遍历函数 231 template<class T> 232 void AVLTree<T>::pretree(TreeNode<T>* node) 233 { 234 if(node==NULL) return; 235 cout<<node->data<<" ";//输出根节点 236 pretree(node->lson);//先遍历左子树 237 pretree(node->rson);//再遍历右子树 238 } 239 //中序遍历函数 240 template<class T> 241 void AVLTree<T>::insubtree(TreeNode<T>* node) 242 { 243 if(node==NULL) return; 244 insubtree(node->lson);//先遍历左子树 245 cout<<node->data<<" ";//输出根节点 246 insubtree(node->rson);//再遍历右子树 247 } 248 //遍历接口 249 template<class T> 250 void AVLTree<T>::traversal() 251 { 252 253 pretree(root); 254 cout<<endl; 255 insubtree(root); 256 cout<<endl; 257 }