avl树是其每个节点的左子树和右子树的高度最多差1的二叉查找树。当在一棵avl树中插入节点的时候,很可能把avl树的平衡给破坏掉,在不平衡的情况下,可以通过对树做单次旋转或者复杂些的双旋转来处理。具体的旋转方法Google去 O(∩_∩)O,这里就不做详细介绍啦。下面仅给已实现的avl树的代码。
/*====================*\
| AvlTree.h |
\*====================*/
#ifndef _AVL_TREE_H_
#define _AVL_TREE_H_
#define ElementType int
#define Max(a,b) (a)>(b)?(a):(b)
struct AvlNode;
typedef struct AvlNode * Position;
typedef struct AvlNode * AvlTree;
//释放树空间
void ClearTree(AvlTree t);
//计算节点的高度
int Height(Position p);
//插入节点
AvlTree Insert(ElementType x,AvlTree t);
//先序遍历
void Preorder_TreePrint(AvlTree t);
//中序遍历
void Inorder_TreePrint(AvlTree t);
//后序遍历
void Postorder_TreePrint(AvlTree t);
//针对左子树做单旋转
static Position SingleRotateWithLeft(Position k2);
//针对右子树做单旋转
static Position SingleRotateWithRight(Position k2);
//针对左子树做双旋转
static Position DoubleRotateWithLeft(Position k3);
//针对右子树做双旋转
static Position DoubleRotateWithRight(Position k3);
#endif
//AVL树结构体
struct AvlNode {
ElementType Element;
AvlTree Left;
AvlTree Right;
int Height;
};
/*====================*\
| AvlTree.c |
\*====================*/
#include "AvlTree.h"
#include <stdio.h>
#include <stdlib.h>
//清空树
void ClearTree(AvlTree t)
{
if(t!=NULL)
{
ClearTree(t->Left);
ClearTree(t->Right);
free(t);
}
}
//先序遍历
void Preorder_TreePrint(AvlTree t)
{
if(t!=NULL)
{
printf("%d(%d) \n",t->Element,t->Height);
Preorder_TreePrint(t->Left);
Preorder_TreePrint(t->Right);
}
}
//中序遍历
void Inorder_TreePrint(AvlTree t)
{
if(t!=NULL)
{
Inorder_TreePrint(t->Left);
printf("%d(%d) \n",t->Element,t->Height);
Inorder_TreePrint(t->Right);
}
}
//后续遍历
void Postorder_TreePrint(AvlTree t)
{
if(t!=NULL)
{
Postorder_TreePrint(t->Left);
Postorder_TreePrint(t->Right);
printf("%d(%d) \n",t->Element,t->Height);
}
}
//插入节点
AvlTree Insert(ElementType x,AvlTree t)
{
if (t == NULL)
{
t = (AvlTree)malloc(sizeof(struct AvlNode));
if (t == NULL)
{
printf("out of space!!\n");
}
else
{
t->Element = x;
t->Left = NULL;
t->Right = NULL;
t->Height = 0;
}
}
else if(x < t->Element)
{
t->Left = Insert(x,t->Left);
if (Height(t->Left)-Height(t->Right) == 2)
{
if (x < t->Left->Element)
{
t = SingleRotateWithLeft(t);
}
else
{
t = DoubleRotateWithLeft(t);
}
}
}
else if (x > t->Element)
{
t->Right = Insert(x,t->Right);
if (Height(t->Right)-Height(t->Left) == 2)
{
if (x > t->Right->Element)
{
t = SingleRotateWithRight(t);
}
else
{
t = DoubleRotateWithRight(t);
}
}
}
t->Height = Max(Height(t->Left),Height(t->Right))+1;
return t;
}
//算节点的高度
int Height(Position p)
{
if(p == NULL)
return 0;
else
return Max(Height(p->Left),Height(p->Right))+1;
}
//针对左子树做单旋转
static Position SingleRotateWithLeft(Position k2)
{
Position k1;
k1 = k2->Left;
k2->Left=k1->Right;
k1->Right = k2;
k2->Height = Max(Height(k2->Left),Height(k2->Right))+1;
k1->Height = Max(Height(k1->Left),Height(k1->Right))+1;
return k1;
}
//针对右子树做单旋转
static Position SingleRotateWithRight(Position k2)
{
Position k1;
k1 = k2->Right;
k2->Right = k1->Left;
k1->Left = k2;
k2->Height = Max(Height(k2->Left),Height(k2->Right))+1;
k1->Height = Max(Height(k1->Left),Height(k1->Right))+1;
return k1;
}
//针对左子树做双旋转
static Position DoubleRotateWithLeft(Position k3)
{
k3->Left = SingleRotateWithRight(k3->Left);
return SingleRotateWithLeft(k3);
}
//针对右子树做双旋转
static Position DoubleRotateWithRight(Position k3)
{
k3->Right = SingleRotateWithLeft(k3->Right);
return SingleRotateWithRight(k3);
}
/*====================*\
| main.c |
\*====================*/
#include "AvlTree.h"
#include <stdio.h>
int main()
{
int i = 0;
AvlTree at = NULL;
for(i=0;i<10;i++)
at = Insert(i,at);
Preorder_TreePrint(at);
ClearTree(at);
return 0;
}
分享到:
相关推荐
利用avl树实现hash表,自测通过。下载代码直接编译,即可运行。
avl树实现 数据结构数据结构数据结构数据结构
用Qt制作的登录系统,使用Avl树实现增删改查,UI界面仅有登录系统。
linux下基于C的avl树实现,插入,删除,查找,输出,检查是否平衡等,
数据结构课程设计(AVL树实现图书管理系统)
该资源实现了数据结构的二叉查找树、AVL树旋转用于用户信息存储,并附有详细的实验报告说明
学习AVL树的算法实现,使用c++在vc6.0中进行相应的算法实现,对正在学习算法的孩子有帮助
数据结构课程设计AVL树实现及其分析实验报告.pdf
avl实现的map映射, alv 树 map 映射 c++ 如有bug 请告知2821565468@qq.com
能够在时间复杂度lg(n)内实现查找中位数的平衡二叉树,同时带重复节点计数的
AVL平衡二叉树的C++实现(模板),实现了插入、查找、删除,前序、后序、中序遍历等
基于C++的AVL树实现,
C++平衡树实现
AVL树的C语言实现
红黑树和AVL树的代码实现,并显示树的形状,同时红黑树还可以输出个路径以及黑高度
控制台程序,采用AVL模板,注释详细。
这两个源文件主要实现了基于C++语言编写的AVL树,将AVL树的所有操作都实现了。测试平台为Linux,现将AVL树的源码奉上。
本程序为MFC开发的电话薄,其中使用AVL数实现快速搜索。同时可以分页查看电话信息。为各种C++或MFC初学者提供。
数据结构中avl树的实现,包含avl树的插入,删除节点,并以括号表示法输出结果
AVL树Java中的AVL树实现有两个基本操作,使用这些操作树本身会保持平衡。 左旋转。 右旋。 然后将有四种可能性左-左情况:— x是y的左子代,y是z的左子代。 左右案例:— x是y的右子代,y是z的左子代。 左右案例:—...