重庆分公司,新征程启航
为企业提供网站建设、域名注册、服务器等服务
这期内容当中小编将会给大家带来有关C语言中如何实现一个平衡二叉树,文章内容丰富且以专业的角度为大家分析和叙述,阅读完这篇文章希望大家可以有所收获。
成都创新互联主要企业基础官网建设,电商平台建设,移动手机平台,重庆小程序开发公司等一系列专为中小企业按需网站建设产品体系;应对中小企业在互联网运营的各种问题,为中小企业在互联网的运营中保驾护航。// // AvlTree.h // HelloWorld // Created by feiyin001 on 17/1/9. // Copyright (c) 2017年 FableGame. All rights reserved. // #ifndef __HelloWorld__AvlTree__ #define __HelloWorld__AvlTree__ #includenamespace Fable { int max(int a, int b) { return a > b? a:b; } //二叉查找树,对于Comparable,必须实现了><=的比较 template 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[]) { AvlTreea; for(int i = 0; i < 100; ++i) { a.insert(i); } return 0; }
上述就是小编为大家分享的C语言中如何实现一个平衡二叉树了,如果刚好有类似的疑惑,不妨参照上述分析进行理解。如果想知道更多相关知识,欢迎关注创新互联网站建设公司行业资讯频道。
另外有需要云服务器可以了解下创新互联建站www.cdcxhl.com,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。