C语言数据结构之平衡二叉树（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  namespace 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 element) { insert(x, t->left);//比根结点小，插入左边 if (height(t->left) - height(t->right) == 2)//高度差达到2了 { if (x 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 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 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 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 a; for(int i = 0; i <100; ++i) { a.insert(i); } return 0; }