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__ #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语言中如何实现一个平衡二叉树了,如果刚好有类似的疑惑,不妨参照上述分析进行理解。如果想知道更多相关知识,欢迎关注创新互联行业资讯频道。
名称栏目:C语言中如何实现一个平衡二叉树
网页网址:http://scyanting.com/article/phodjc.html