首页 > 代码库 > 平衡二叉树-AVL树的构建和操作
平衡二叉树-AVL树的构建和操作
首先上一下单纯的二叉树插入节点的代码，用的是不返回新根节点的方式：
1 void insertNode(BTree *&root,int data) 2 { 3 if (root == nullptr)//当根节点为NULL时，在根节点上插入 4 { 5 root = initRoot(data); 6 return; 7 } 8 if (root->data =http://www.mamicode.com/= data)//当插入数据等于根节点时，不插入 9 {10 return;11 }12 if (root->data > data)//如果当前节点比插入节点大，那么插入在左子树进行13 {14 insertNode(root->left, data);15 }16 else//否则在右子树进行17 {18 insertNode(root->right, data);19 }20 }
上面提到的initRoot()函数如下：
1 BTree *initRoot(int data)2 {3 BTree *root = new BTree;4 root->data =http://www.mamicode.com/ data;5 root->left = nullptr;6 root->right = nullptr;7 return root;8 }
这里使用了C++的内存管理方式：new
为了了解如何释放申请的这些块，我写了这么一个删掉整个树的函数：
1 void deleteTree(BTree *&root) 2 { 3 if (root == nullptr) 4 return; 5 if (root->left != nullptr) 6 deleteTree(root->left); 7 if (root->right != nullptr) 8 deleteTree(root->right); 9 delete root;10 root = nullptr;11 }
所有函数如下（为了不占太多地方，折叠了起来）：
1 #include "iostream" 2 3 typedef struct _avlTree_//结构类中的成员默认都是共有的（Public） 4 { 5 int data; 6 struct _avlTree_ *left; 7 struct _avlTree_ *right; 8 }BTree; 9 10 BTree *initRoot(int data)11 {12 BTree *root = new BTree;13 root->data =http://www.mamicode.com/ data;14 root->left = nullptr;15 root->right = nullptr;16 return root;17 }18 19 void insertNode(BTree *&root,int data)20 {21 if (root == nullptr)//当根节点为NULL时，在根节点上插入22 {23 root = initRoot(data);24 return;25 }26 if (root->data =http://www.mamicode.com/= data)//当插入数据等于根节点时，不插入27 {28 return;29 }30 if (root->data > data)//如果当前节点比插入节点大，那么插入在左子树进行31 {32 insertNode(root->left, data);33 }34 else//否则在右子树进行35 {36 insertNode(root->right, data);37 }38 }39 40 void deleteTree(BTree *&root)41 {42 if (root == nullptr)43 return;44 if (root->left != nullptr)45 deleteTree(root->left);46 if (root->right != nullptr)47 deleteTree(root->right);48 delete root;49 root = nullptr;50 }51 52 int main(void)53 {54 BTree *root = initRoot(5);55 insertNode(root, 8);56 insertNode(root, 2);57 insertNode(root, 1);58 insertNode(root, 4);59 insertNode(root, 3);60 insertNode(root, 7);61 insertNode(root, 9);62 deleteTree(root);63 system("pause");64 return 0;65 }
当然为了使用system("pause")，iostream是不可不加的（当然也是为了简单）。
为了进行平衡二叉树的构建，我们需要进行如下操作：
1.为树的节点添加深度标识；
2.通过搜索深度进行判断哪里出现不符合AVL标准的节点；
3.根据情况决定使用单旋转还是双旋转；
所有的这些操作除了需要建立独立函数之外，全部都可以集中到插入操作中，在插入完毕之后就可以进行判断，然后进行平衡操作。
从易到难，先来进行深度的添加：
二叉树结构体：
1 typedef struct _avlTree_//结构类中的成员默认都是共有的（Public）2 {3 int data;4 struct _avlTree_ *left;5 struct _avlTree_ *right;6 int height;//深度标识7 }BTree;
返回节点深度的函数：
1 int getHeight(BTree *root)2 {3 if (root == nullptr)4 return -1;5 else6 return root->height;7 }
最主要的------>插入的函数：
1 void insertNode(BTree *&root,int data) 2 { 3 if (root == nullptr) 4 root = initRoot(data); 5 else if (root->data =http://www.mamicode.com/= data) 6 return; 7 else if (root->data > data) 8 insertNode(root->left, data); 9 else if (root->data < data)10 insertNode(root->right, data);11 12 root->height = Max(getHeight(root->left), getHeight(root->right)) + 1;13 }
返回最大值的函数：
1 int Max(const int &x,const int &y)2 {3 if (x > y)4 return x;5 else6 return y;7 }
为了更加方便的实现深度的标注和平衡与否的检测，这里使用的深度有如下特征（因为跟我想象中的不一样，所以记录一下）：
1.根节点有最大深度；
2.任何一个叶子都是0深度；
3.深度从叶子到根递增；
4.某父节点的左右节点的深度不一定一样；
（我想象的深度是从根节点为0深度向下递增，相同水平线上的深度相同。）
为了能够全自动（区别于人工构建）构建平衡树，需要了解会产生深度差的情况，因此会发现可能的结果只有四种：
1.在根的左子的左子
2.在跟的右子的右子
3.在根左子的右子
4.在根右子的左子
分别对应如下图示：
在右侧插入的两图应当类似，为了省事就没画；
上述两幅图体现了插入后产生的不平衡情况和其解决方式，前图称为单旋转，后图称为双旋转；
我们就是在这个理论基础上实现在插入过程中进行判断并旋转：改进后的插入函数为（注意其他函数有变化，全部代码请到文章最后找）：
1 BTree *insertNode(BTree *&root,const int &data) 2 { 3 if (root == nullptr)//如果要被插入节点的树为空树，就初始化它并返回地址 4 { 5 root = new BTree; 6 root->left = nullptr; 7 root->right = nullptr; 8 root->data =http://www.mamicode.com/ data; 9 }10 else if (root->data > data)11 {12 //以下重点理解13 root->left = insertNode(root->left, data);14 if (getHeight(root) - getHeight(root->right) >= 2)15 {16 if (data < root->left->data)17 root = singleRotateWithLeft(root);18 else19 root = doubleRotateWithLeft(root);20 }21 }22 else if (root->data < data)23 {24 root->right = insertNode(root->right, data);25 if (getHeight(root) - getHeight(root->left) >= 2)26 {27 if (data>root->right->data)28 root = singleRotateWithRight(root);29 else30 root = doubleRotateWithRight(root);31 }32 }33 34 root->height = getMax(getHeight(root->left), getHeight(root->right)) + 1;35 return root;36 }
相应的四种旋转函数为：
1 BTree *singleRotateWithLeft(BTree *&root)//以下分别是单旋转和双旋转的函数，每个都返回旋转之后的根节点 2 {//单左旋 3 BTree *k2 = root;//有深度差的被命名为k2 4 BTree *k1 = k2->left; 5 6 //旋转 7 k2->left = k1->right; 8 k1->right = k2; 9 10 return k1;11 }12 13 BTree *doubleRotateWithLeft(BTree *&root)14 {//双左旋15 BTree *k3 = root;16 BTree *k1 = k3->left;17 BTree *k2 = k1->right;18 19 //旋转20 k1->right = k2->left;21 k3->left = k2->right;22 k2->left = k1;23 k2->right = k3;24 25 return k2;26 }27 28 BTree *singleRotateWithRight(BTree *&root)29 {//单右旋30 BTree *k2 = root;31 BTree *k1 = k2->right;32 33 //旋转34 k2->right = k1->left;35 k1->left = k2;36 37 return k1;38 }39 40 BTree *doubleRotateWithRight(BTree *&root)41 {//单右旋42 BTree *k1 = root;43 BTree *k3 = k1->right;44 BTree *k2 = k3->left;45 46 //旋转47 k1->right = k2->left;48 k3->left = k2->right;49 k2->left = k1;50 k2->right = k3;51 52 return k2;53 }
全部代码如下：
1 #include "iostream" 2 3 typedef struct _avlTree_//结构类中的成员默认都是共有的（Public） 4 { 5 int data; 6 struct _avlTree_ *left; 7 struct _avlTree_ *right; 8 int height;//深度标识 9 }BTree; 10 11 int getHeight(const BTree *root) 12 { 13 if (root == nullptr) 14 return -1; 15 else 16 return root->height; 17 } 18 19 int getMax(const int &x,const int &y) 20 { 21 if (x > y) 22 return x; 23 else 24 return y; 25 } 26 27 BTree *singleRotateWithLeft(BTree *&root)//以下分别是单旋转和双旋转的函数，每个都返回旋转之后的根节点 28 {//单左旋 29 BTree *k2 = root;//有深度差的被命名为k2 30 BTree *k1 = k2->left; 31 32 //旋转 33 k2->left = k1->right; 34 k1->right = k2; 35 36 return k1; 37 } 38 39 BTree *doubleRotateWithLeft(BTree *&root) 40 {//双左旋 41 BTree *k3 = root; 42 BTree *k1 = k3->left; 43 BTree *k2 = k1->right; 44 45 //旋转 46 k1->right = k2->left; 47 k3->left = k2->right; 48 k2->left = k1; 49 k2->right = k3; 50 51 return k2; 52 } 53 54 BTree *singleRotateWithRight(BTree *&root) 55 {//单右旋 56 BTree *k2 = root; 57 BTree *k1 = k2->right; 58 59 //旋转 60 k2->right = k1->left; 61 k1->left = k2; 62 63 return k1; 64 } 65 66 BTree *doubleRotateWithRight(BTree *&root) 67 {//单右旋 68 BTree *k1 = root; 69 BTree *k3 = k1->right; 70 BTree *k2 = k3->left; 71 72 //旋转 73 k1->right = k2->left; 74 k3->left = k2->right; 75 k2->left = k1; 76 k2->right = k3; 77 78 return k2; 79 } 80 81 BTree *insertNode(BTree *&root,const int &data) 82 { 83 if (root == nullptr)//如果要被插入节点的树为空树，就初始化它并返回地址 84 { 85 root = new BTree; 86 root->left = nullptr; 87 root->right = nullptr; 88 root->data =http://www.mamicode.com/ data; 89 } 90 else if (root->data > data) 91 { 92 //以下重点理解 93 root->left = insertNode(root->left, data); 94 if (getHeight(root) - getHeight(root->right) >= 2) 95 { 96 if (data < root->left->data) 97 root = singleRotateWithLeft(root); 98 else 99 root = doubleRotateWithLeft(root);100 }101 }102 else if (root->data < data)103 {104 root->right = insertNode(root->right, data);105 if (getHeight(root) - getHeight(root->left) >= 2)106 {107 if (data>root->right->data)108 root = singleRotateWithRight(root);109 else110 root = doubleRotateWithRight(root);111 }112 }113 114 root->height = getMax(getHeight(root->left), getHeight(root->right)) + 1;115 return root;116 }117 118 void deleteTree(BTree *&root)119 {120 if (root->left != nullptr)121 deleteTree(root->left);122 if (root->right != nullptr)123 deleteTree(root->right);124 if (root->left == nullptr && root->right == nullptr)125 {126 delete root;127 root = nullptr;128 }129 }130 131 int main(void)132 {133 BTree *root = nullptr;134 root = insertNode(root, 1);135 root = insertNode(root, 2);136 root = insertNode(root, 3);137 root = insertNode(root, 5);138 root = insertNode(root, 7);139 root = insertNode(root, 9);140 root = insertNode(root, 11);141 deleteTree(root);142 system("pause");143 return 0;144 }
原来是由于插入例程总想自己写所以总是出错，而且似乎书上面的代码跟我这个有一定的出入，譬如在判断高度差那里例程是用的根左子树和右子树的差，得到的结果也是与2比，但是我用根本身的高度和它左右比较却也没有问题，但是例程中的就可能有问题了。
按照书上的总出事故，因此耽搁了好久没做完，今天正好做一下，争取明天完成树部分的基本练习。
以上。
平衡二叉树-AVL树的构建和操作
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。