【1】为什么需要平衡二叉树？
矛盾是推进事物向前发展的源动力。
那么平衡二叉树是从哪里来？肯定是有矛盾存在的。请看下面的分析：
【2】什么是平衡二叉树？
平衡二叉树的基本认识：
【3】平衡二叉树的构建原理
平衡二叉树的形成肯定是有一定规律可循的，那么平衡二叉树的“生长”原理是什么呢？
请看程老师下面的构建示例以及详细讲解：
关于平衡二叉树的旋转分为以下四种情况：
【4】平衡二叉树的实现
平衡二叉树的实现代码如下：
1 #include2 using namespace std; 3 4 template 5 class AVLtree; 6 7 template 8 class TNode 9 { 10 friend class AVLtree ; 11 private: 12 Type data; 13 int balance; // 平衡因子 14 TNode *leftChild, *rightChild; 15 public: 16 TNode(const Type &x = Type(),TNode *left = NULL,TNode *right = NULL) 17 : data(x) 18 , leftChild(left) 19 , rightChild(right) 20 , balance(0) 21 {} 22 }; 23 24 template 25 class AVLtree 26 { 27 private: 28 TNode *root; 29 private: 30 void RightBalance(TNode * &r,bool &action); 31 void LeftBalance(TNode *&r,bool &action); 32 void Insert(TNode * &root,const Type &x,bool &action); 33 void LeftLeft(TNode * &r); 34 void RightRight(TNode * &r); 35 void LeftRight(TNode *&r); 36 void RightLeft(TNode *&r); 37 TNode *Parent(TNode *p,TNode *cur); 38 TNode *FindNodeNext(TNode *cur); 39 void DeleTNode(TNode *&cur,TNode *par); 40 void Remove(TNode * &r,const Type &x,bool &action); 41 void InOrder(TNode *p); 42 public: 43 AVLtree(); 44 void Insert(const Type &bt); 45 TNode *Parent(TNode *cur); 46 void Remove(const Type &x); 47 void InOrder(); 48 }; 49 50 // 右平衡处理过程 51 template 52 void AVLtree ::RightBalance(TNode * &r, bool &action) 53 { 54 TNode *rightsub = r->rightChild, *leftsub = NULL; 55 switch (rightsub->balance) //判断右子树的平衡因子 56 { 57 case -1: // RR型 58 r->balance = 0; 59 rightsub->balance = 0; 60 RightRight(r); //RR型处理 61 action = false; 62 break; 63 case 0: 64 break; 65 case 1: // RL型 66 leftsub = rightsub->leftChild; 67 switch (leftsub->balance) // 判断左子树的平衡因子 68 { 69 case 0: // RL型 70 r->balance = 0; 71 rightsub->balance = 0; 72 leftsub->balance = 0; 73 break; 74 case 1: // RLL型 75 r->balance = 0; 76 leftsub->balance = 0; 77 rightsub->balance = -1; 78 break; 79 case -1: // RLR型 80 rightsub->balance = 0; 81 leftsub->balance = 0; 82 r->balance= -1; 83 break; 84 } 85 RightLeft(r); // RL折线型转换处理 86 action = false; 87 break; 88 } 89 } 90 // 折线型LR处理 91 template 92 void AVLtree ::LeftRight(TNode *&r) 93 { 94 RightRight(r->leftChild); // 转换为LL型(一条直线) 95 LeftLeft(r); // LL型处理 96 } 97 // 折线型RL处理 98 template 99 void AVLtree ::RightLeft(TNode *&r)100 {101 LeftLeft(r->rightChild); // 先转换为RR型(一条直线)102 RightRight(r); // RR型处理103 }104 // 1. 把RL转换为RR 2. LL型处理105 template 106 void AVLtree ::LeftLeft(TNode * &r) 107 {108 TNode *cur = r; // cur暂存r109 r = r->leftChild; // 改变r就是改变根110 cur->leftChild = r->rightChild;// 改变暂存cur 实现衔接111 r->rightChild = cur; // 根的右子树置为cur112 }113 // 1. 把LR转换为LL 2. RR型处理114 template 115 void AVLtree ::RightRight(TNode * &r)116 {117 TNode *cur = r; // cur暂存r118 r = r->rightChild; // 改变r就是改变根119 cur->rightChild = r->leftChild;// 改变暂存cur 实现衔接120 r->leftChild = cur; // 根的左子树置为cur121 }122 // 左平衡处理过程123 template 124 void AVLtree ::LeftBalance(TNode *&r, bool &action)125 {126 TNode *leftsub = r->leftChild;127 TNode *rightsub = leftsub->rightChild;128 switch (leftsub->balance)129 {130 case 1:// LL型131 leftsub->balance = 0;132 r->balance = 0;133 LeftLeft(r);134 action = false;135 break;136 case 0:137 action = false;138 break;139 case -1:// LR型140 switch (rightsub->balance)141 {142 case 0:// LR型143 r->balance = 0;144 rightsub->balance = 0;145 leftsub->balance = 0;146 break;147 case -1:// LRR型148 r->balance = 0;149 rightsub->balance = 0;150 leftsub->balance = 1;151 break;152 case 1:// LRL型153 rightsub->balance = 0;154 leftsub->balance = 0;155 r->balance = -1;156 break;157 }158 LeftRight(r); // LR折线型转换处理159 action = false;160 break;161 }162 }163 // Insert主函数164 template 165 void AVLtree ::Insert(TNode * & root, const Type &x, bool &action)166 {167 if (NULL == root)168 {169 root = new TNode (x);170 return;171 }172 else if (x > root->data)173 {174 Insert(root->rightChild, x, action);175 if (action) // 右子树插入成功176 {177 switch (root->balance) // 需要重置根的平衡因子178 {179 case 1: // 表示左子树已经存在，现再插入右子树成功180 root->balance = 0; //平衡因子置0181 break;182 case 0: // 表示之前平衡，现再插入右子树成功183 root->balance = -1; //平衡因子置1184 break;185 case -1: // 表示右子树已经存在，现再插入右子树成功186 RightBalance(root, action); //右平衡187 break;188 }189 }190 }191 else if (x < root->data)192 {193 Insert(root->leftChild, x, action);194 if (action) // 左子树插入成功195 {196 switch (root->balance) // 需要重置根的平衡因子197 {198 case 1: // 平衡左子树199 LeftBalance(root, action);200 break;201 case 0:202 root->balance = 1;203 break;204 case -1:205 root->balance = 0;206 action = false;207 break;208 }209 }210 }211 else212 cout << "数据" << x << "重复！" << endl;213 }214 // 查找当前节点的父节点215 template 216 TNode *AVLtree ::Parent(TNode *p, TNode *cur)217 {218 if (NULL == p || NULL == cur|| p == cur)219 return NULL;220 if (cur == p->leftChild || cur == p->rightChild)221 return p;222 223 if (p->data < cur->data)224 return Parent(p->rightChild, cur);225 else226 return Parent(p->leftChild, cur);227 }228 // 查找当前结点的后继 (先序遍历的后继)229 template 230 TNode *AVLtree ::FindNodeNext(TNode *cur)231 {232 if (NULL == cur) 233 return NULL;234 TNode *p = cur->rightChild;235 while (p->leftChild != NULL)236 {237 p = p->leftChild;238 }239 return p;240 }241 //242 /删除节点243 template 244 void AVLtree ::DeleTNode(TNode *&cur, TNode *par)245 {246 if (NULL == cur) 247 return;248 // 情况一：删除的是根节点，那么它的父节点必定为NULL249 if (NULL == par)250 { // cur可能是根结点，并且树仅仅只有一个根251 if (NULL == cur->rightChild && NULL == cur->leftChild)252 {253 delete cur;254 cur = NULL;255 return;256 }257 // 单分支的树258 if (NULL == cur->rightChild)259 { // 右子树不存在260 TNode *p = cur;261 cur = cur->leftChild;262 delete p;263 p = NULL;264 return;265 }266 if (NULL == cur->leftChild)267 { // 左子树不存在268 TNode *q = cur;269 cur = cur->rightChild;270 delete q;271 q = NULL;272 return;273 }274 }275 // 情况二：删除的属于双分支的节点276 if (cur->leftChild != NULL && cur->rightChild != NULL)277 {278 TNode *p = FindNodeNext(cur); // 锁定先序遍历的后继279 // 情况一：280 if (cur->rightChild == p)281 { // 说明右子树仅仅只有一个节点282 cur->balance += 1; // 删除之后平衡因子改变283 cur->data = p->data; // 填充数据，意味着改变删除对象284 cur->rightChild = p->rightChild; // 衔接数据285 delete p; //删除节点p286 p = NULL;287 return;288 }289 // 情况二：290 // 否则291 TNode *q = Parent(p); // 找到父节点292 if (q->balance != 0) // 不等于0，说明删除后会影响根结点的平衡因子293 cur->balance += 1; // 调整根节点的平衡因子294 // 否则295 q->balance -= 1; // 删除的是左节点，所以加一296 cur->data = p->data; // 填充数据，意味着改变删除对象297 298 q->leftChild = p->rightChild; // 衔接数据299 300 // 最后才可以动手删除节点 删除节点 释放内存301 delete p;302 p = NULL;303 return;304 }305 // 情况三：单分支(其中包括了叶子节点的情况)306 if (NULL == cur->leftChild)307 {308 TNode *p = cur;309 if (cur == par->leftChild)310 par->leftChild = cur->rightChild; // 衔接数据311 else 312 par->rightChild = cur->rightChild; // 衔接数据313 314 delete p;315 p = NULL;316 return;317 }318 if (NULL == cur->rightChild)319 {320 TNode *q = cur; 321 if (cur == par->leftChild)322 par->leftChild = cur->leftChild;323 else 324 par->rightChild = cur->leftChild;325 326 delete q;327 q = NULL;328 return;329 }330 }331 // 删除过程的主函数332 template 333 void AVLtree ::Remove(TNode * &r, const Type &x, bool &action)334 {335 if (NULL == r) 336 return;337 if (x == r->data)338 {339 TNode *cur = r; // 确定数据的节点信息340 TNode *par = Parent(r);// 确定当前结点的父节点341 DeleTNode(r, par); // 删除当前指针342 return;343 }344 else if (x > r->data)345 { // 右边查找346 Remove(r->rightChild, x, action);347 if (action)348 {349 switch (r->balance)350 {351 case -1: // 若原来为1，现在删除了右节点，应该为0352 r->balance = 0;353 break;354 //若原来为-1，现在又再右枝上删除了节点， 355 //树一定不平衡，需要左平衡调整356 case 1: 357 LeftBalance(r, action);358 action = false;359 break;360 case 0: // 若原来为0，现在删除了右节点，应该为-1361 r->balance = 1;362 action = false;363 break;364 }365 }366 }367 else if (x < r->data)368 {369 Remove(r->leftChild, x, action);370 if (action)371 {372 switch (r->balance)373 {374 case -1:// 若原来为1，现在又再左枝上删除了节点，375 // 树一定不平衡，需要右平衡调整376 RightBalance(r, action);377 break;378 case 1:// 若原来为-1，现在删除了左节点，应该为0379 r->balance = 0;380 break;381 case 0:// 若原来为0，现在删除了左节点，应该为1382 r->balance = -1;383 action = false;384 break;385 }386 }387 }388 }389 390 template 391 AVLtree ::AVLtree(): root(NULL)392 {}393 template 394 void AVLtree ::Insert(const Type &bt)395 {396 bool action = true;397 Insert(root, bt, action);398 }399 template 400 TNode *AVLtree ::Parent(TNode *cur)401 {402 return Parent(root, cur);403 }404 template 405 void AVLtree ::Remove(const Type &x)406 {407 bool action = true;408 Remove(root, x, action);409 }410 template 411 void AVLtree ::InOrder(TNode *p)412 {413 if (p != NULL)414 {415 InOrder(p->leftChild);416 cout << p->data << " ";417 InOrder(p->rightChild);418 }419 }420 template 421 void AVLtree ::InOrder()422 {423 InOrder(root);424 cout << endl;425 }
Good Good Study, Day Day Up.
顺序 选择 循环 总结