C语言数据结构之平衡二叉树(AVL树)实现方法示例

本文实例讲述了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语言数据结构之平衡二叉树(AVL树)实现方法示例 的全部内容, 来源链接: utcz.com/z/319334.html

回到顶部