1 ********二叉树及其遍历********* 2 二叉树 3 树 每一个节点有多个节点 4 二叉树 每一个节点最多有两个节点 而且节点之间是有顺序的 5 下面来分辨几个二叉树 只是通常的定义 可能不同教材的定义不一样 6 7 满二叉树(Full Binary Tree) 8 要么没有儿子,要么有两个儿子 9 10 完全二叉树(Complete Binary Tree) 11 从根节点到最后一个节点(注意是这二叉树的最后一个节点) 一直都有连续的点 没有空掉一个位置 的二叉树 12 13 完美二叉树(Perfect BT) 14 每个节点都塞满的二叉树,在不增加层数的情况下不可能再增加节点的二叉树,有的书也叫满二叉树 15 16 为什么要区分这些? 17 因为越接近完美的树性能越好,越接近链表的树(就拉直了变成一链表)性能越差。 18 19 ****树与二叉树的顺序实现**** 20 我们要清楚,如果我们要去实现一个数据结构,逻辑上要能看得出这个结构原来的样子 21 比如我们用数组实现一棵树的话,我们就得能从数组的结构上能脑补出来这棵树原来的样子 22 那么怎样的树比较好用顺序存储,当参差不全的树存进数组的话,我们没法分清哪个点是谁的儿子, 23 因为中间会有断开的点,那么我们干脆就把这棵树给补全成一棵完全二叉树,就没有断了 24 然后又因为是二叉树,一个点后面两个点,就是它的儿子了,就能很容易看出来。 25 那不完全行不行,也可以,那个位置没有点的话,就空着,那就完事了,但是这样会很浪费空间。 26 所以如果不太接近完全二叉树的一般的树,不适合用数组去存储,接近完全二叉树的才会去用顺序实现。 27 28 29 ****树与二叉树的链式实现**** 30 一般的树:我们不能确定有多少个节点,指针域的数目安排会有问题 31 即使确定了,也可能有问题,比如根节点有一百个节点,但是下面的节点都最多只有4个, 32 但是指针域只能安排最多的,所以100个会有96个浪费。 33 那么我们想能不能用子节点去找父节点?每一个节点只要给一个指针域就好了, 34 但是找儿子找孙子就很难了。 35 36 至此,我们发现,一般的树这玩意真的很烦人,我们无比的怀念二叉树。 37 采用一种方法,左下角的是儿子右下角的是兄弟,把一般的树变成二叉树就好了。 38 这样的话我们就不用再纠结到底有几个儿子这样的问题了。 39 40 二叉树:每个节点有两个指针域left right,其实也可以加多一个节点指向父亲,最终还是根据需求来决定结构。 41 42 ****二叉树的遍历**** 43 巧记:前中右的区别就是根节点的访问次序 44 前序遍历:先访问根节点,再按照前序遍历的顺序访问左子树,再按照前序遍历的顺序访问右子树 45 中序遍历:用中序遍历的顺序访问左子树,然后访问树根,接着用中序遍历的顺序访问右子树 46 后序遍历:先按照后序遍历的顺序访问左子树,然后后序遍历的顺序访问右子树,最后访问根节点 47 48 还有一种访问遍历方式:层序遍历:每一层来访问 用队列存储访问过的点就好了 因为要先进先出(画个图走一遍就能看出来) 49 创建一个队列,然后把节点的指针入队...最后输出 就完事了 50 51 ****二叉树的迭代遍历(非递归)****ps:迭代即循环 52 递归的书写比较方便,逻辑容易懂。但是递归是函数不断调用自己来实现,会占用操作系统的栈内存,栈内存容量较少 53 可能会栈溢出,不能递归的话我们就来模拟递归的过程。函数调用是压栈的过程,函数返回是弹栈的过程。 54 那么我们自己写一个栈不就完了?确实。自己写的栈可以自定义空间大小,比操作系统调用栈要调用的层次要深。 55 我们来看看三种遍历的实质是什么?实际上,三种递归其实都是从树根走下去的,但是第几次走过树根的时候才对其进行访问 56 这就是遍历的实质,你可能路过这个节点,但是不一定就是这一次见面就要访问它,所以实际上三种遍历从走路顺序上都一样。 57 故,我们只要适时保存走过的点,然后保存,并在应该访问的时候弹出,就好了。 58 但是,如果按照上面说的,要到一定时候,就是第几次走过的时候才访问的话,就需要保存地址了,因为我们只有左右指针, 59 而没有回去的指针。那用栈来保存我们的来路就好了。 60 61 62 ******************* 63 ****二叉树的C++实现****(其实和JAVA差不多的,面向对象语言写出来的东西都差不多,JAVA的就不写了) 64 #include<iostream> 65 #include<stack> 66 67 using namespace std; 68 69 template<class Element>//二叉树的元素类型 类似于JAVA的泛型 70 struct BinNode{ 71 Element data; 72 BinNode<Element> *left; 73 BinNode<Element> *right; 74 BinNode(Element x){ 75 data = x; 76 left = right = NULL; 77 } 78 }; 79 80 template<class Element> 81 class BinTree{ 82 //有树根 我们就能抓住整一棵树 83 protected: 84 BinNode<Element> *root;//树根 85 86 //中序遍历 先左子树后根节点最后右子树 87 void rinprint(BinNode<Element> *r){ 88 if(r == NULL) return; 89 rinprint(r->left); 90 cout << r->data << ' '; 91 rinprint(r->right); 92 } 93 //复习递归 递归,要有递归关系式,要有递归终止条件 94 //另外要记住:凡是指针都可能出现NullPointerExcpetion,传入一个指针之后首先就要判断是不是空的 95 void rpreprint(BinNode<Element> *r){ 96 if(r == NULL) return; //写了这个之后下面的递归不用判断是不是空的了 97 cout << r->data << ' '; 98 rpreprint(r->left);//即使在这里写上if(left),也照样要判断一次,反正空的时候进去就会直接return 99 rpreprint(r->right);//判不判断其实省不了时间 100 } 101 //查找的内部递归函数 102 BinNode<Element> * rfindX(Element x, BinNode<Element> *r){ 103 if(!r){//树是空的 104 return NULL; 105 } 106 if(r->data == x) return r; 107 BinNode<Element> *found; 108 found = rfindX(x, r->left); 109 //如果在left找到了,就可以返回了,否则就找右树就完事 110 return found ? found : rfindX(x,r->right); 111 } 112 113 114 void rprint(BinNode<Element> *r, int depth){ 115 for(int i = 0; i < depth; i ++){ 116 //多一层就多两个空格 117 cout << " "; 118 } 119 if(r == NULL) { 120 cout << "[/]" << endl; 121 122 } 123 else{ 124 cout << r->data << endl; 125 rprint(r->left, depth + 1); 126 rprint(r->right, depth + 1); 127 } 128 } 129 130 //非递归 131 //迭代实现前序遍历 132 void ipreprint(BinNode<Element> *r){ 133 //访问点 压栈 向左访问 这样的顺序 134 //用栈的目的,找到来路 希望栈弹出来元素之后下一步往哪里走 135 //如果stack<int>,弹出来之后,还要find这个int是在哪个位置,就不方便了 136 //如果压一个结点进去的话,不知道会压的是什么东西,可能会很低效,干脆就压一个地址就好了 137 stack<BinNode<Element>*> st; 138 if(r == NULL) return ; 139 140 //for比较难写 可以先写while 条件也可以先假设 后期再改 写代码不是一蹴而就的 141 while(r){ 142 //前序遍历,走过去的时候就要打印了 143 //打印 压栈 打印 压栈 不断循环... 144 //顺序:每一个节点的根节点左子树右子树 145 cout << r->data << ' '; 146 st.push(r); 147 r = r->left; 148 //当左子树再往左走为空的时候 就开始弹出(注意弹的栈可能会空!!!就会失败) 149 //if(r == NULL){ 为什么要把if改成while? 因为左子树走到底是空的之后 150 //就要回到根节点,因为它的右儿子可能不是空的,要一直弹栈弹回去 151 //而用if之后,当r是NULL就结束循环,下一步就把r赋值给了while,就终止了 152 //而那个可能存在的整一棵树的树根的右儿子就打印不出来了 153 //另外,为什么要加上st.empty()?就像上面说的,树根有一个右儿子,当这个右儿子最后一个入栈 154 //同时,它也是最后一个弹出来的,然后就空了,遍历就结束了。 155 while(r == NULL && !st.empty()){ 156 //要找到右边 先得到这个父节点 157 //找到右边之后 就 访问点 压栈 向左访问 这样的顺序 158 r = st.top(); 159 st.pop(); 160 r = r->right; 161 } 162 } 163 } 164 165 //中序遍历 迭代实现 166 //拿前序遍历的稍作修改就能实现了 167 //中序遍历和前序遍历的非递归都走的同样的路径,只是什么时候访问不一样 168 void ipreprint(BinNode<Element> *r){ 169 stack<BinNode<Element>*> st; 170 if(r == NULL) return ; 171 172 while(r){ 173 //cout << r->data << ' '; 中序遍历是第二次经过才访问的 174 st.push(r); 175 r = r->left; 176 //注意下面这个循环是直至左边为空的时候才会进入 177 while(r == NULL && !st.empty()){ 178 r = st.top(); 179 st.pop(); 180 //当左边为空了,在我们向右走之前,就是第二次走到一棵树的树根,这时候就要访问了 181 cout << r->data << ' '; 182 r = r->right; 183 } 184 } 185 } 186 187 //后序遍历 迭代实现 留作练习 188 //这个就和前序和中序的那个函数很大不一样了 189 //因为每个元素要入栈两次,出栈两次,还需要压栈次数,如果是第二次弹栈,才需要访问 190 //解决方案:除了存指针的栈以外再stack<int> count这么一个次数栈 191 //第二个方法是,重新写一个struct,里面加入次数和结点的指针 192 193 public: 194 BinTree(){root = NULL;} 195 BinTree(Element r){ 196 //传入树根节点 类型应不应该是Element,还是BinNode? 197 //作为用户,我们只想要传入一个数据,而不会想去创建一个节点,所以,我们传入的是Elem 198 root = new BinNode<Element>(r); 199 } 200 //析构函数 释放树占用的内存 201 ~BinTree(){} 202 203 //找到这个点并且返回地址 204 BinNode<Element>* findX(Element x){ 205 // //查找就是一个遍历的过程 206 // //空树异常 207 // if(root != NULL) return NULL; 208 // //树根就是要找的 209 // if(root->data == x) return root; 210 // BinNode<Element> *found; 211 // // found = find()... 同时我们也要知道到底遍历的左右顺序,所以我们按照遍历的套路,写一个内部递归函数 212 // //由于我们有了rfindX,所以。。。上面写的东西全部作废. 213 return rfindX(x, root); 214 } 215 216 //因为插入会有失败的情况 所以用bool 217 //父节点元素 插入位置 要插入的元素 218 bool insert(Element p, int LorR, Element x){ 219 //首先我们要找到这个节点,然后再判断那个位置是不是能插入 220 //由于查找的操作比较频繁,所以我们要干脆封装成一个findX函数 221 BinNode<Element> *found; 222 //记住 找的是父节点 223 found = findX(p); 224 if(!found) return false; 225 if(LorR == 0){ 226 if(found->left) return false; 227 found->left = new BinNode<Element>(x); 228 } 229 else{ 230 if(found->right) return false; 231 found->right = new BinNode<Element>(x); 232 } 233 return true; 234 } 235 236 //遍历,就是打印,所以不用返回值 237 //参数在用户角度也是不需要提供的,因为我们就是调用一棵特定的树的前序遍历 238 //但是没有参数的话,我们在递归实现时候就会有麻烦,因为递归,必须有参数 239 //所以我们选择在内部实现前序遍历 rpreprint, preprint的话就只需要去调用就完事了 240 //前序遍历 241 void preprint(){ 242 //递归实现遍历 rpreprint(root); 243 /***非递归 迭代实现遍历**/ 244 ipreprint(root); 245 cout << endl; 246 } 247 //中序遍历 248 void inprint(){ 249 //调用递归中序遍历函数 250 rinprint(root); 251 } 252 253 void print(){ 254 //因为要打印出不同节点的一定数量的空格,所以要知道节点的深度 255 rprint(root, 0); 256 } 257 258 259 260 }; 261 262 int main(){ 263 BinTree<int> bt(11); 264 //bt.preprint();//前序遍历打印树 265 bt.insert(11, 0, 22);//插入哪一个节点的子节点位置?左二子还是右儿子?现在规定flag左二子是0,右儿子是1 266 bt.insert(11, 1, 33); 267 bt.insert(22, 0, 44); 268 bt.insert(33, 0, 55); 269 //bt.preprint(); 270 bt.preprint();//打印得比preprint打印得好看点 便于观察 271 /*打印成如图所示 272 11 273 22 274 44 275 [/] 276 33 277 55 278 [/] 279 */ 280 bt.inprint(); 281 return 0; 282 } 283 284 实例:数叶子节点的个数 需要遍历整一棵树 看看哪些节点没有儿子 285 遍历:要么就递归,要么就循环迭代 286 protected: 287 int countLeaves(BinNode<Element> *r){ 288 //空树无叶子 289 if(r == NULL){ 290 return 0; 291 } 292 //注意:当树只有树根自己一个 那么就只有它一个叶子 293 if(r->left == NULL && r->right == NULL){ 294 return 1; 295 } 296 //否则等于左子树的叶子+右子树的叶子 297 return countLeaves(r->left) + countLeaves(r->right); 298 } 299 public: 300 int count(){ 301 return countLeaves(root); 302 } 303 304 ***二叉树一般用于查找操作,那么接下来来讲二叉搜索树(Binary Search Tree)*** 305 左子树元素比树根小,右子树元素比树根大,左右子树都是BST 306 二叉树的查找效率是O(N),因为你可能要遍历到最后一个元素才能找到你要找的指定元素 307 而BST呢,来分析一下,首先要记住一个前提,所有的树都是从树根出发的。 308 FindMax FindMin FindX 实际都是同一个方法,不断的比较 309 当一棵树长的比较匀称的时候,左右两边的点都差不多的比较满,每次都是折半查找,是O(logN) 310 如果退化成一维的,比如只有右子树,实际上就已经是链表了,此时查找效率为O(N) 311 所以后来也衍生出来了一种树,会自动去调节平衡,叫平衡二叉搜索树,我们先说完二叉搜索树再去讲。 312 **插入与删除** 313 只要注意一个就好了:BST一般是不能存放重复的值的,如果插入的值里面有,就失败 314 另外的,插入一个数,如果找到了那个位置,那么这个位置本身是NULL的,插入就比较麻烦了 315 我们就要就地创建一个结点,然后给递归回去,返回当前这个新创建节点的地址, 316 然后赋值地址给父亲的儿子,才能挂上去父亲那里 317 我们也可以直接就找到这个位置的父亲,站在这个父亲节点,创建一个左儿子或者右儿子,然后再进行赋值,这样就好办多了 318 319 删除,当父亲只有一个儿子,把父亲删除,就直接把后代继承过来就好了。 320 那么有两个儿子的怎么办?还有孙子呢?儿子直接拿过来就会直接一连串位置给空掉 321 那我们要找一个点代替这个父亲的话,肯定是从下面的点里取一个大小差不多中间的一个, 322 找左树的最大出来,那么原先的右树也是符合BST的大小规律的,原先的左树剩余的点也是符合大小规律的 323 右树的最小也是可以的。但,不论是左树最大还是右树最小,都有可能最多还有一个儿子(为什么是最多? 324 因为左树最大,它不可能还有右孩子,右树最小,也不可能还有左孩子是吧,由BST的大小排序确定) 325 那么我们就可以这样干,因为只有一个点了嘛,我们把这个父亲的数据往上一个删除的位置给覆盖之后, 326 再拿它的儿子来覆盖,就完事啦!因为只有一个儿子!!! 327 328 329 那么下面就来说一下二叉搜索树的代码 330 因为二叉搜索树是一棵二叉树,在CPP这种语言下,可以把上门写过的二叉树的代码作为.h文件引入来用就好 331 记得改为.h文件的时候删掉函数的具体实现,然后最开始加上预编译指令 332 #ifndef bintree_h 333 #define bintree_h 334 最后一行加上 335 #endif 336 避免头文件被多次包含,多次展开 337 338 339 ********二叉搜索树实现******** 340 //下面的代码的Elem可能会有点问题,因为上面用的是Element,有问题改一下就好了 341 #include<iostream> 342 #include"bintree.h" 343 344 using namespace std; 345 346 //同样地,元素类型也不是确定的,所以用模板(泛型) 347 template <class Elem> 348 //冒号是CPP的继承的语法 JAVA用extends就完事 349 class BSTree : public Bintree<Elem>{ 350 protected: 351 //递归地寻找最大值 352 BinNode<Elem>* rfindMax(BinNode<Elem>* r){ 353 if(r->right == NULL){//没儿子你不就是最大的吗hh 354 return r; 355 } 356 return rfindMax(r->right); 357 //这种在返回部分递归的,叫尾递归,效率较低 358 //如果修改不太麻烦,一般都可以改成循环 359 } 360 361 //返回要插入的地址 362 BinNode<Elem>* rinsert(Elem x, BinNode<Elem>* r){ 363 // r->left = rinsert(x, r->left); 这种写法不好,要是插入失败,返回空的时候,整一左树没了 364 //思路也是小于往左找,大于右边找,等于就失败,因为BST一般不要有相同的元素 365 //root 空呢?空就直接插入就完了 366 if(r == NULL){ 367 r = new BinNode<Elem>(x); 368 if(!r) throw -1; //当因为内存不够时候,可能会在new的时候返回空 369 } 370 else if(x < r->data){ 371 r->left = rinsert(x, r->left); 372 } 373 else if(x > r->data){ 374 r->right = rinsert(x, r->right); 375 } 376 else throw -2;//用-1和-2分辨是插入失败还是内存太少创建失败 377 return r; 378 } 379 380 BinNode<Elem>* remove(Elem x, BinNode<Elem> * r){ 381 BinNode<Elem>* tmp; 382 //逻辑和查找是一样的 就小于往左边 大于往右边 等于直接删呗 383 //永远要记住!!!指针可能是空的 384 if(!r) throw -1;//空指针异常 385 else if(x < r->data){ 386 r->left = remove(x, r->left); 387 } 388 else if(x > r->data){ 389 r->right = remove(x, r->right); 390 } 391 else if(x == r->data){ 392 //return NULL; 注意 有可能有一个儿子,有可能两个儿子,有可能没有儿子 393 if(r->left && r->right){ 394 //有两个儿子 395 tmp = rfindMax(r->left);//tmp一定不为空 因为左儿子存在 396 r->data = tmp->data;//拿左树最大覆盖要删除的位置 397 r->left = remove(tmp->data, r->left)//然后把这个最大的值给删除 并且要更新左儿子!!! 398 } 399 else{ 400 //有儿子 或者 没有儿子 401 //有一个儿子,不论是左儿子还是右儿子,先把左儿子or右儿子拿来覆盖,接着 402 //都是把儿子的儿子节点挂过去给这个儿子 403 //没有儿子,可以把它视为做拥有NULL儿子,道理是一样的,也是拿过来覆盖 404 //所以可以不用那么多else if 全部合并到这个else里面 不需要分类讨论 405 tmp = r;//因为要删除它 先暂时存一下地址 406 r = r->left ? r->left : r->right;//全空时候也是NULL的 407 //当执行完上一句之后,树根的地址就变成了左儿子or右儿子或者NULL 408 //即使左儿子OR右儿子还有儿子!!! 因为变的是地址!!!不用再进行操作了 409 //原来是连着的点依然是连着的!!! 410 delete tmp; 411 } 412 } 413 414 return r; 415 } 416 public: 417 BSTree(){ 418 this->root = NULL; 419 } 420 //如果返回值是Elem,返回一个值,就不能给这个节点做一个改动 421 //另外还有一个弊端,如果是空的,只能抛出异常,而不能返回一个NULL值 422 //所以把返回值改为了返回节点的地址,但是改为地址也有弊端,可能会改动树的结构.. 423 BinNode<Elem>* findMax(){//findMax不需要参数,因为就是在这棵树上面进行findMax 424 // return rfindMax(this->root); 尾递归效率较低 425 //修改为循环版本 426 //一路向右,怎样才会向右,指针不空 427 //用一个临时指针保存树根 因为我们不能改变树根 428 //if(this->root == NULL) return NULL;//空树 直接返回 写在下面循环语句也行 效率差不太多 429 BinNode<Elem>* tmp = this->root; 430 //谨记用指针之前要保证指针不空 因为有可能一开始就是空的,所以要增加tmp && 431 while(tmp && tmp->right){ 432 tmp = tmp->right; 433 } 434 return tmp; 435 } 436 //找最小和找最大是完全对称的,照着上面写就完事了 437 BinNode<Elem>* findMin(){ 438 if(this->root == NULL) return NULL; 439 BinNode<Elem> *tmp = this->root; 440 while(tmp->left){ 441 tmp = tmp->left; 442 } 443 return tmp; 444 } 445 //找特定的值 446 BinNode<Elem>* findX(Elem x){ 447 //findMin findMax肯定能找出来值,找特定值findX的话不一定 448 BinNode<Elem>* tmp = this->root; 449 //要确定root是不是空的 450 //但是没必要写的像上面一开始就判断树根是不是为空 451 //因为我们还有可能找不到这个x,那时候也是返回空,集中起来写,尽量避免多个return(多出口) 452 while(tmp){ 453 if(x == tmp->data) break;//写在循环条件也行 && x != tmp->data 454 if(x < tmp->data) tmp = tmp->left; 455 if(x > tmp->data) tmp = tmp->right; 456 } 457 458 return tmp; 459 } 460 bool insert(Elem x){ 461 //因为只有元素x,一棵树的操作要和树根挂钩,所以要在内部写一个函数 462 //注意,肯定是赋值给this->root,因为你有可能是从一棵不空树去insert变成一棵树 463 try{ 464 this->root = rinsert(x, this->root); 465 } 466 catch(int e){ 467 return false; 468 } 469 return true; 470 } 471 //找不到这个要删除的点的话就会失败 所以bool作为返回值 472 //下面写的是递归的remove 迭代的留作练习 473 bool remove(Elem x){ 474 try{ 475 //删除以后返回树根地址 更新一下树 476 //在这里函数名字一样是可以的,重载(overload)就完事 477 this->root = remove(x, this->root); 478 } 479 catch(int e){ 480 //为什么不以返回空指针作为删除失败的标志?当树根只有一个点的话,你删除了不就NULL了 481 //所以返回NULL 不一定就是删除失败 482 return false; 483 } 484 return true; 485 } 486 }; 487 488 int main(){ 489 BSTree<int> bt; 490 cout << bt.findMax() << endl; 491 bt.insert(10);//作为使用者,当然希望只有一个参量,就是插入的参量 492 bt.insert(5); 493 bt.insert(20); 494 bt.insert(8); 495 bt.insert(15); 496 bt.insert(2); 497 bt.insert(6); 498 bt.print(); 499 cout << bt.findX(6) << endl; 500 cout << "-----------" << endl; 501 //bt.remove(20); 502 //bt.remove(15); 503 //bt.remove(10); 504 //bt.remove(5); 505 return 0; 506 } 507 508 *********平衡二叉搜索树(AVL树)********** 509 为什么需要这种东西?AVL树可以加快搜索的速度,而且这棵树经常会被删除和插入进行修改 510 首先是一棵二叉搜索树,然后是自平衡的一棵树。 511 那么我们来看一下平衡的定义: 512 1.空树是平衡的 513 2.当树是非空的时候,左右子树平衡且左右子树高度差绝对值<=1时候也是平衡的 514 平衡因子:这个节点的左右子树的高度差; 空树的高度定义为-1 515 所以,AVL树每个节点的平衡因子为-1 0 1三个 516 在此,我们定义树根深度为0,每个叶子高度为0,向上生长,所以一棵树的高度就是这个节点到它的叶子节点的最高的高度 517 也就是每一棵树的高度为节点树根的高度 518 AVL树的查找效率为O(lnN) 519 520 插入和删除,AVL树的插入和删除会时刻保持平衡,这就是它的特点 521 那么如何调节平衡,这就是问题了。我们可以去想象,一棵树的节点是可以拉起来的, 522 例如 20 523 10 524 插入5,5会在左边插入,也即左子树的左子树插入,导致20这个节点的平衡因子会变成2 525 20 10 526 10 5 20 527 5 拉起来, 这样的话每个节点的平衡因子都变成了0 528 又因为是左子树的左子树上插入的节点导致不平衡,调节的方式就定义叫左左单旋,记成LL单旋就好, 529 因为这命名方式有点反人类,明明是clockwise顺时针往右边旋转,却叫TMD左左单旋(LL Rotation)。。。 530 左左单旋的一般情况如图 A B 531 B AR(A的RIGHT) ->把B转上去 BL A 532 BL BR 插入 BR AR 533 插入 原先的BR就由A来收养,A降级变成B的右儿子,由图就能看到高度相对平衡 534 由上述的方法可以衍生出一堆方法,就是观察每个节点的平衡因子,然后尽量把高的给拧下来,低的上去,而且不能破坏BST结构(左小右大) 535 拧到这棵树能平衡,注意上面在左子树的左子树插入时候,左子树的右子树并没有升高高度. 536 示意图如图所示:注意图形带高度 537 538 又例如: 10 539 5 20 540 2 9 ->观察到10的平衡因子在插入之后变成了2,把5移上去是行不通的,当5上去的时候,把9给10当左儿子 541 6(新插入) 接着,5的平衡因子又会因为6的插入变成了-2,那么我们的目的依然是,要把10拉下来,还可以拉谁上去? 542 毕竟我们不能破坏BST左小右大的结构,我们可以尝试把9拉上去 543 该操作叫做左右双旋(LR双旋),因为在树根的左子树的右子树发生,9和10都要旋转,然后把新插入9的6扔给了9原先的父节点5, 544 9 545 5 10 546 2 6 20 547 548 一般情况示意图如图所示,我们要插入CL或者CR位置,然后的话那个图形就会变高,接着要想办法把这两位置变高的点拉上去 549 但是BL不改变高度,把B拉上去,BL会提高,目的达不到,所以只能把C拉上去,实际上就是一个,先把B左子树给拉平衡, 550 然后把A给拉平衡,也就是B为根节点的右右单旋后(注意动的只是左子树),然后进行A为根节点的左左单旋,就完事啦! 551 552 同理RL双旋和LR双旋是对称了,就不讲了。故一共有左左 右右 左右 右左 这四种(在哪个位置)旋转方式实现AVL的自平衡。 553 554 最后来讲一下AVL树的删除,一般不推荐说AVL树进行删除,因为可能会破坏AVL树的平衡性,然后又要调 555 当AVL树的删除不太频繁的时候,我们采取一种lazy deletion的操作,也就是在BinNode中加入一项标志删除的flag 556 如果要删除,这个点不用做替换,也不用做平衡,只要把删除flag标记上true就好。 557 一般来说AVL树大多是用来增加和查找,也就是插入和遍历。。删除的话比较少。 558 如果是经常需要删除,那还不推荐用AVL树这种结构。 559 560 *****AVL树的代码实现***** 561 事先把BST弄成BSTREE.h 562 563 #include<iostream> 564 #include<algorithm> 565 #include"bstree.h" 566 567 using namespace std; 568 569 template<class Elem> 570 class AVLTree : public BSTree<Elem>{ 571 //要计算高度 572 /* 573 在bstree.h中的BinNode结构体增加高度 574 struct BinNode{ 575 Elem data; 576 int h; 577 BinNode<Elem> *left; 578 BinNode<Elem> *right; 579 BinNode(Elem x){ 580 data = x; 581 left = right = NULL; 582 h = 0; 583 } 584 } 585 */ 586 protected: 587 //计算高度函数 内部使用 不用public 588 int height(BinNode<Elem> *r){ 589 if(!r) return -1;//空树 590 return r->h; 591 } 592 //虚函数 动态联编(说实话我也不知道是什么反正看得懂逻辑代码就完事了。。。) 593 virtual BinNode<Elem>* rinsert(Elem x, BinNode<Elem>* r){ 594 //大的框架是一样的,不一样的是,插入之后要调节平衡 595 //把调平衡的单独拎出去作为函数使用 596 if(r == NULL){ 597 //在空树插入不会导致不平衡 598 r = new BinNode<Elem>(x); 599 if(!r) throw -1;//空的 内存不够 创建失败 600 } 601 else if(x < r->data) { 602 r->left = rinsert(x, r->left); 603 //在左边插入,会让左边高,所以用左子树高度减去右子树的高度 604 if(height(r->left) - height(r->right) == 2){ 605 //不平衡 606 //然后判断是左子树的左边还是左子树的右边插入 607 if (x < r->left->data)//在左子树的左边 608 { 609 r = LLrotate(r); 610 } 611 else //在左子树的右边 612 { 613 r = LRrotate(r); 614 //这么一看,把操作定义为在哪里插入而进行的操作命名还挺方便的。。。 615 } 616 } 617 } 618 else if(x > r->data) { 619 r->right = rinsert(x, r->right); 620 //同理,在右边插入,会让右边的高度可能大于左边的高度 621 if(height(r->right) - height(r->left) == 2){ 622 if(x < r->right->data){ 623 //在右子树的左边 624 r = RLrotate(r); 625 } 626 else{ 627 //否则就在右子树的右边咯 628 r = RRrotate(r); 629 } 630 } 631 } 632 else throw -2; 633 //记得计算节点的高度 634 //rinsert是个递归函数,只要递归下去,就会从头到尾把所有节点高度计算一遍 635 //所以下面的不只是计算当前根节点的高度,递归调用时候就会把每个节点的高度计算好 636 r->h = max(height(r->left),height(r->right)) + 1; 637 return r; 638 } 639 //忘了怎么写就画图 自己转一下 640 BinNode<Elem>* LLrotate(BinNode<Elem>* r){ 641 //把child顶上去 把r弄下来 顺时针旋转 642 BinNode<Elem>* child; 643 child = r->left; 644 //首先,在左子树,所有的节点数据会比树根小,所以是放给树根的左儿子 645 //其次,可能会疑惑,直接丢给它,那原来的左儿子呢,诶,这就要看上一句啦! 646 //child=r->left;已经临时保存了树根的左儿子,所以左儿子的东西不会丢失! 647 r->left = child->right; 648 child->right = r; 649 //****注意!!!转好了 但是高度已经发生变化了 650 //为什么非得用height?不直接用r->h?因为懒- -懒得分析r是不是空的,r是空的话,r->h就没了。。 651 r->h = max(height(r->left),height(r->right)) + 1; 652 child->h = max(height(child->left),height(child->right)) + 1; 653 /****返回平衡后的树根!!!***/ 654 return child; 655 } 656 BinNode<Elem>* RRrotate(BinNode<Elem>* r){//逆时针旋转 657 //RR和LL左右对称,反着写就完事了 658 BinNode<Elem>* child; 659 child = r->right; 660 r->right = child->left; 661 child->left = r; 662 r->h = max(height(r->left),height(r->right)) + 1; 663 child->h = max(height(child->left),height(child->right)) + 1; 664 /****返回后来的树根!!!!!***/ 665 return child; 666 } 667 BinNode<Elem>* LRrotate(BinNode<Elem>* r){ 668 //先进行一下左子树的右右旋转 669 //然后进行一下整一棵树的树根的左左旋转 670 //高度不用再进行计算了,因为在RR/LL rotate中都已经算过一次了 所以不用再进行计算 671 r->left = RRrotate(r->left); 672 r = LLrotate(r); 673 //因为上面LL的时候已经把树根更新了 所以下面直接返回的是r 674 /****返回r!!!***/ 675 return r; 676 } 677 BinNode<Elem>* RLrotate(BinNode<Elem>* r){ 678 r->right = LLrotate(r->right); 679 r = RRrotate(r); 680 /****返回r!!!***/ 681 return r; 682 public: 683 AVLTree(){ 684 this->root = NULL; 685 } 686 //原先的insert不用重写 逻辑都是递归逻辑插入 但是rinsert要重写 687 //记得写析构函数... 688 ~AVLTree(){ 689 //...不写了 我是懒狗 690 } 691 }; 692 693 int main(){//调试 694 AVLTree<int> t; 695 t.insert(10); 696 t.insert(20); 697 t.print(); 698 cout << "----------" << endl; 699 t.insert(30); 700 return 0; 701 }
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论,欢迎说说您的想法!