C语言数据结构之平衡二叉树(AVL树)实现方法示例
更新时间:2020年4月25日 17:28 点击:1279
本文实例讲述了C语言数据结构之平衡二叉树(AVL树)实现方法。分享给大家供大家参考,具体如下:
AVL树是每个结点的左子树和右子树的高度最多差1的二叉查找树。
要维持这个树,必须在插入和删除的时候都检测是否出现破坏树结构的情况。然后立刻进行调整。
看了好久,网上各种各种的AVL树,千奇百怪。
关键是要理解插入的时候旋转的概念。
// // 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语言学生信息管理系统小项目
下一篇: C语言学生学籍管理系统课程设计
相关文章
- 这篇文章主要为大家详细介绍了C语言实现放烟花的程序,有音乐播放,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-23
- 本篇文章主要介绍C语言中char的知识,并附有代码实例,以便大家在学习的时候更好的理解,有需要的可以看一下...2020-04-25
- 这篇文章主要介绍了详解如何将c语言文件打包成exe可执行程序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-25
- 这篇文章主要介绍了C#数据结构之队列(Quene),结合实例形式较为详细的讲述了队列的功能、原理与C#实现队列的相关技巧,需要的朋友可以参考下...2020-06-25
- free函数是释放之前某一次malloc函数申请的空间,而且只是释放空间,并不改变指针的值。下面我们就来详细探讨下...2020-04-25
- 这篇文章主要介绍了C语言中计算正弦的相关函数总结,包括正弦和双曲线正弦以及反正弦的函数,需要的朋友可以参考下...2020-04-25
详解C语言中的rename()函数和remove()函数的使用方法
这篇文章主要介绍了详解C语言中的rename()函数和remove()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25- 这篇文章主要介绍了C语言中求和、计算平均值、方差和标准差的实例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-12-10
- 本篇文章主要讲解C语言 基本语法,这里提供简单的示例和代码来详细讲解C语言的基本语法,开始学习C语言的朋友可以看一下,希望能够给你带来帮助...2021-09-18
- 这篇文章主要介绍了C语言中send()函数和sendto()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25
- 今天小编就为大家分享一篇C语言实现从文件读入一个3*3数组,并计算每行的平均值,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了C语言中memcpy 函数的用法详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了使用C语言操作文件的基本函数整理,包括创建和打开以及关闭文件的操作方法,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C#常用数据结构和算法,这里我们总结了一些知识点,可以帮助大家理解这些概念。...2020-06-25
- 这篇文章主要介绍了C语言中查找字符在字符串中出现的位置的方法,分别是strchr()函数和strrchr()函数的使用,需要的朋友可以参考下...2020-04-25
- 很多同学在学习c语言的时候是不是会碰到a++和++a都有甚么作用啊。今天我们就来探讨下...2020-04-25
- 这篇文章主要对C语言中const关键字的用法进行了详细的分析介绍,需要的朋友可以参考下...2020-04-25
- 下面小编就为大家带来一篇C语言实现时间戳转日期的算法(推荐)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了C语言之整数划分问题(递归法)实例代码的相关资料,需要的朋友可以参考下...2020-04-25
C语言正则表达式详解 regcomp() regexec() regfree()用法详解
C语言处理正则表达式常用的函数有regcomp()、regexec()、regfree()和regerror(),这里就为大家介绍一下,需要的朋友可以参考一下啊...2020-04-25