C语言中如何实现一个平衡二叉树
这期内容当中小编将会给大家带来有关C语言中如何实现一个平衡二叉树，文章内容丰富且以专业的角度为大家分析和叙述，阅读完这篇文章希望大家可以有所收获。
成都创新互联是一家集网站建设,西华企业网站建设,西华品牌网站建设,网站定制,西华网站建设报价,网络营销,网络优化,西华网站推广为一体的创新建站企业，帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿，时刻以成就客户成长自我，坚持不断学习、思考、沉淀、净化自己，让我们为更多的企业打造出实用型网站。
//
// AvlTree.h
// HelloWorld
// Created by feiyin001 on 17/1/9.
// Copyright (c) 2017年 FableGame. All rights reserved.
//
#ifndef __HelloWorld__AvlTree__
#define __HelloWorld__AvlTree__
#include <iostream>
namespace Fable
{
int max(int a, int b)
{
return a > b? a:b;
}
//二叉查找树，对于Comparable,必须实现了><=的比较
template<typename Comparable>
class AvlTree
{
public:
//构造函数
AvlTree(){}
//复制构造函数
AvlTree(const AvlTree& rhs)
{
root = clone(rhs.root);
}
//析构函数
~AvlTree()
{
makeEmpty(root);
}
//复制赋值运算符
const AvlTree& operator=(const AvlTree& rhs)
{
if (this != &rhs)
{
makeEmpty(root);//先清除
root = clone(rhs.root);//再复制
}
return *this;
}
//查找最小的对象
const Comparable& findMin()const
{
findMin(root);
}
//查找最大的对象
const Comparable& findMax()const
{
findMax(root);
}
//是否包含了某个对象
bool contains(const Comparable& x)const
{
return contains(x, root);
}
//树为空
bool isEmpty()const
{
return root == nullptr;
}
//打印整棵树
void printTree()const
{
printTree(root);
}
//清空树
void makeEmpty()
{
makeEmpty(root);
}
//插入某个对象
void insert(const Comparable& x)
{
insert(x, root);
}
//移除某个对象
void remove(const Comparable& x)
{
remove(x, root);
}
private:
struct AvlNode
{
Comparable element;
AvlNode* left;
AvlNode* right;
int height;
AvlNode(const Comparable& theElement, AvlNode* lt, AvlNode* rt, int h = 0)
:element(theElement), left(lt), right(rt), height(h){}
};
typedef AvlNode* AvlNodePtr;
AvlNodePtr root;//根结点
//顺时针旋转
void clockwiseRotate(AvlNodePtr& a)
{
AvlNodePtr b = a->left;//左叶子
a->left = b->right;//a的左叶子变为b的右叶子，b本来的子结点都比a小的。
b->right = a;//b的右结点指向a，b的高度上升了。
a->height = max(height(a->left), height(a->right)) + 1;//重新计算a的高度
b->height = max(height(b->left), a->height) + 1;//重新计算b的高度
a = b;//a的位置现在是b，当前的根结点
}
//逆时针旋转
void antiClockWiseRotate(AvlNodePtr& a)
{
AvlNodePtr b = a->right;//右结点
a->right = b->left;//a接收b的左结点
b->left = a;//自己成为b的左结点
a->height = max(height(a->left), height(a->right)) + 1;//计算高度
b->height = max(b->height, height(a->right)) + 1;//计算高度
a = b;//新的根结点
}
//对左边结点的双旋转
void doubleWithLeftChild(AvlNodePtr& k3)
{
antiClockWiseRotate(k3->left);//逆时针旋转左结点
clockwiseRotate(k3);//顺时针旋转自身
}
//对右边结点的双旋转
void doubleWithRightChild(AvlNodePtr& k3)
{
clockwiseRotate(k3->right);//顺时针旋转有节点
antiClockWiseRotate(k3);//逆时针旋转自身
}
//插入对象，这里使用了引用
void insert(const Comparable& x, AvlNodePtr& t)
{
if (!t)
{
t = new AvlNode(x, nullptr, nullptr);
}
else if (x < t->element)
{
insert(x, t->left);//比根结点小，插入左边
if (height(t->left) - height(t->right) == 2)//高度差达到2了
{
if (x < t->left->element)//插入左边
{
clockwiseRotate(t);//顺时针旋转
}
else
{
doubleWithLeftChild(t);//双旋转
}
}
}
else if (x > t->element)
{
insert(x, t->right);//比根结点大，插入右边
if (height(t->right) - height(t->left) == 2)//高度差达到2
{
if (t->right->element < x)//插入右边
{
antiClockWiseRotate(t);//旋转
}
else
{
doubleWithRightChild(t);//双旋转
}
}
}
else
{
//相同的
}
t->height = max(height(t->left), height(t->right)) + 1;//计算结点的高度
}
void removeMin(AvlNodePtr& x, AvlNodePtr& t)const
{
if (!t)
{
return;//找不到
}
if (t->left)
{
removeMin(t->left);//使用了递归的方式
}
else
{
//找到最小的结点了
x->element = t->element;
AvlNodePtr oldNode = t;
t = t->right;
delete oldNode;//删除原来要删除的结点
}
if (t)
{
t->height = max(height(t->left), height(t->right)) + 1;//计算结点的高度
if(height(t->left) - height(t->right) == 2)
{ //如果左儿子高度大于右儿子高度
if(height(t->left->left) >= height(t->left->right))//并且左儿子的左子树高度大于左儿子的右子树高度
{
clockwiseRotate(t); //顺时针旋转
}
else
{
doubleWithLeftChild(t);//双旋转左子树
}
}
else
{
if(height(t->right->right) - height(t->right->left) == 2) //如果右子树大于左子树
{
antiClockWiseRotate(t);//逆时针旋转
}
else
{
doubleWithRright(t);//双旋转右子树
}
}
}
}
//删除某个对象，这里必须要引用
void remove(const Comparable& x, AvlNodePtr& t)const
{
if (!t)
{
return;//树为空
}
else if (x < t->element)
{
remove(x, t->left);//比根结点小，去左边查找
}
else if (x > t->element)
{
remove(x, t->right);//比根结点大，去右边查找
}
else if (!t->left && !t->right)//找到结点了，有两个叶子
{
removeMin(t, t->right);//这里选择的方法是删除右子树的最小的结点
}
else
{
AvlNodePtr oldNode = t;
t = (t->left) ? t->left : t->right;//走到这里，t最多只有一个叶子，将t指向这个叶子
delete oldNode;//删除原来要删除的结点
}
if (t)
{
t->height = max(height(t->left), height(t->right)) + 1;//计算结点的高度
if(height(t->left) - height(t->right) == 2)
{ //如果左儿子高度大于右儿子高度
if(height(t->left->left) >= height(t->left->right))//并且左儿子的左子树高度大于左儿子的右子树高度
{
clockwiseRotate(t); //顺时针旋转
}
else
{
doubleWithLeftChild(t);//双旋转左子树
}
}
else
{
if(height(t->right->right) - height(t->right->left) == 2) //如果右子树大于左子树
{
antiClockWiseRotate(t);//逆时针旋转
}
else
{
doubleWithRright(t);//双旋转右子树
}
}
}
}
//左边子树的结点肯定比当前根小的，所以一直往左边寻找
AvlNodePtr findMin(AvlNodePtr t)const
{
if (!t)
{
return nullptr;//找不到
}
if (!t->left)
{
return t;
}
return findMin(t->left);//使用了递归的方式
}
//右边子树的结点肯定比当前根大，所以一直往右边找
AvlNodePtr findMax(AvlNodePtr t)const
{
if (t)
{
while (t->right)//使用了循环的方式
{
t = t->right;
}
}
return t;
}
//判断是否包含某个对象，因为要使用递归，所以还有一个public版本的
bool contains(const Comparable& x, AvlNodePtr t)const
{
if (!t)
{
return false;//空结点了
}
else if (x < t->element)
{
//根据二叉树的定义，比某个结点小的对象，肯定只能存在与这个结点的左边的子树
return contains(x, t->left);
}
else if (x > t->element)
{
//根据二叉树的定义，比某个结点大的对象，肯定只能存在与这个结点的右边的子树
return contains(x, t->right);
}
else
{
//相等，就是找到啦。
return true;
}
}
//清空子树
void makeEmpty(AvlNodePtr& t)
{
if (t)
{
makeEmpty(t->left);//清空左边
makeEmpty(t->right);//清空右边
delete t;//释放自身
}
t = nullptr;//置为空
}
//打印子树，这里没有使用复杂的排位，纯属打印
void printTree(AvlNodePtr t)const
{
if (!t)
{
return;
}
std::cout << t->element << std::endl;//输出自身的对象
printTree(t->left);//打印左子树
printTree(t->right);//打印右子树
}
AvlNodePtr clone(AvlNodePtr t)const
{
if (!t)
{
return nullptr;
}
return new AvlNode(t->element, clone(t->left), clone(t->right));
}
int height(AvlNodePtr t)const
{
return t == nullptr ? -1 : t->height;
}
};
}
#endif简单测试一下。
//
// AvlTree.cpp
// HelloWorld
// Created by feiyin001 on 17/1/9.
// Copyright (c) 2017年 FableGame. All rights reserved.
//
#include "AvlTree.h"
using namespace Fable;
int main(int argc, char* argv[])
{
AvlTree<int> a;
for(int i = 0; i < 100; ++i)
{
a.insert(i);
}
return 0;
}上述就是小编为大家分享的C语言中如何实现一个平衡二叉树了，如果刚好有类似的疑惑，不妨参照上述分析进行理解。如果想知道更多相关知识，欢迎关注创新互联行业资讯频道。
网页题目：C语言中如何实现一个平衡二叉树
本文路径：https://www.cdcxhl.com/article22/phodjc.html
成都网站建设公司_创新互联，为您提供用户体验、网站建设、企业网站制作、外贸网站建设、营销型网站建设、域名注册
声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联
- 深圳龙岗网站建设外贸网站建设专业的专家 2015-06-20
- 临沂外贸网站建设：做外贸网站要注意哪些问题呢？ 2021-08-15
- 如何做一个高端外贸网站建设？ 2021-12-03
- 外贸网站建设对外贸企业有多重要？ 2016-03-14
- 外贸网站建设的主要规划目标 2023-02-27
- 企业网站如何提高网站内容的质量度成都外贸网站建设公司为您讲解 2021-10-25
- 佛山外贸网站建设好后如何进行推广 2022-11-14
- 成都外贸网站建设服务 2016-11-02
- 外贸网站建设成功后早期怎么提高流量? 2022-09-22
- 成都外贸网站建设公司谈外贸网站建设的注意事项 2022-06-14
- 外贸网站建设中的网站优化技巧 2019-12-04
- 佛山外贸网站建设要考虑什么? 2022-08-15