AVL树C++实现
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了AVL树C++实现，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3572字，纯文字阅读大概需要6分钟。
内容图文
//AVL树
#include<iostream>
#include<functional>using namespace std;
class avl_tree
{
private:
struct tree
{
int data;
tree* L;
tree* R;
int height;
tree(int data_) :data(data_), L(0), R(0), height(0){}
};
tree* root;
public:
avl_tree() :root(0){}
void Insert(int data)
{
function<void(tree*&, int)> ins = [&](tree*& r, int d)
{
if (r == NULL)
{
r = new tree(d);
}
else if (d < r->data)
{
ins(r->L, d);
if (Height(r->L) - Height(r->R) == 2)
{
if (d < r->L->data)
{
r = LL(r);
}
else
{
r = LR(r);
}
}
}
else if (d > r->data)
{
ins(r->R, d);
if (Height(r->R) - Height(r->L) == 2)
{
if (d > r->R->data)
{
r = RR(r);
}
else
{
r = RL(r);
}
}
}
r->height = Compare(Height(r->L), Height(r->R)) + 1;
};
ins(root, data);
}
void Delete(int data)
{
//不能使用二叉树原先左插右删除方法，那样的话高度差会混乱
function<void(tree*&, int)> del = [&](tree*& r, int d)
{
if (r == NULL)
{
return;
}
if (d < r->data)
{
del(r->L, d);
if (Height(r->R) - Height(r->L) == 2)
{
tree* temp = r->R; // 此时右边高了
if (Height(temp->L) > Height(temp->R)) // 需要双旋转
{
r = RL(r);
}
else //需要单旋转
{
r = RR(r);
}
}
}
else if (d > r->data)
{
del(r->R, d);
if (Height(r->L) - Height(r->R) == 2)
{
tree* temp = r->L;
if (Height(temp->L) >= Height(temp->R))
{
r = LL(r);
}
else
{
r = LR(r);
}
}
}
else
{
if (r->L && r->R) //要删除节点的左右节点都非空
{
if (Height(r->L) > Height(r->R)) //如果要删除节点的左子树比右子树高，则可以把左边最大的节点放在要删除节点上，可以保持树的平衡
{
tree* temp = r->L;
while (temp->R)
{
temp = temp->R;
}
r->data = temp->data;
del(r->L, temp->data);
}
else //如果要删除节点的右子树比左子树高或相等，则可以把右边最小的节点放在要删除节点上，可以保持书的平衡
{
tree* temp = r->R;
while (temp->L)
{
temp = temp->L;
}
r->data = temp->data;
del(r->R, temp->data);
}
}
else //如果左右节点不是全都非空，这个时候不用再分情况讨论了，直接删除该节点
{
tree* temp = r;
r = (r->L != NULL) ? r->L : r->R;
delete temp;
}
}
};
del(root, data);
}
void Destroy()
{
function<void(tree*)> des = [&](tree* r)
{
if (r == NULL)
{
return;
}
des(r->L);
des(r->R);
delete r;
};
des(root);
root = NULL;
}
int Find_max()
{
tree* temp = root;
while (temp->R)
{
temp = temp->R;
}
return temp->data;
}
int Find_min()
{
tree* temp = root;
while (temp->L)
{
temp = temp->L;
}
return temp->data;
}
void Travel_mid()
{
function<void(tree*)> tra = [&](tree* root)
{
if (root == NULL)
{
return;
}
tra(root->L);
/*int temp = root->height;
while (temp)
{
cout << ‘\t‘;
temp--;
}*/
cout << root->data << endl;
tra(root->R);
};
tra(root);
}
tree* LL(tree* t)
{
tree* temp = t->L;
t->L = temp->R;
temp->R = t;
t->height = Compare(Height(t->L), Height(t->R)) + 1;
temp->height = Compare(Height(t->L), Height(t->R)) + 1;
return temp;
}
tree* RR(tree* t)
{
tree* temp = t->R;
t->R = temp->L;
temp->L = t;
t->height = Compare(Height(t->L), Height(t->R)) + 1;
temp->height = Compare(Height(t->L), Height(t->R)) + 1;
return temp;
}
tree* LR(tree* t)
{
t->L = RR(t->L);
return LL(t);
}
tree* RL(tree* t)
{
t->R = LL(t->R);
return RR(t);
}
int Height(tree* t)
{
if (t == NULL)
{
return -1;
}
return t->height;
}
int Compare(int one, int two)
{
return one > two ? one : two;
}
void Travel_tree()
{
function<void(tree*, int)> tra = [&](tree* r, int j)
{
if (r == NULL)
{
return;
}
for (int i = 0; i < j; i++)
{
cout << " ";
}
cout << r->data << endl;
tra(r->L, j+1);
tra(r->R, j+1);
};
int judge = 0;
tra(root, judge);
}
};
int main()
{
avl_tree t;
for (int i = 0; i < 10; i++)
{
t.Insert(i);
}
t.Travel_tree();
t.Delete(5);
t.Travel_tree();
cin.get();
return 0;
}
原文：http://blog.csdn.net/linukey/article/details/45718435
内容总结
以上是互联网集市为您收集整理的AVL树C++实现全部内容，希望文章能够帮你解决AVL树C++实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】