AvLTree-豆柴文库

您所在位置：网站首页 / AvLTree.doc / 文档详情

免费试读已结束，剩余 2 页请下载文档后查看

16 金币

下载文档

/ 7

下载提示

如果您无法下载资料，请参考说明：

1、部分资料下载需要金币，请确保您的账户上有足够的金币

2、已购买过的文档，再次下载不重复扣费

3、资料包下载后请先用软件解压，在使用对应软件打开

文本预览

峻岭云松
avltree
#ifndefAVLTREE_H
#defineAVLTREE_H1
typedefstructAvlNode*Position;
typedefstructAvlNode*AvlTree;
typedefintElementType;
structAvlNode
{
	intElement;
	AvlTreeLeft;
	AvlTreeRight;
	intHeight;
};
PositionFind(ElementTypex,AvlTreeT);
PositionFindMax(AvlTreeT);
PositionFindMin(AvlTreeT);
Max(inta,intb);
AvlTreeMakeEmpty(AvlTreeT);
AvlTreeInsert(ElementTypex,AvlTreeT);
AvlTreeDelete(ElementTypex,AvlTreeT);
ElementTypeRetrieve(PositionP);
voiddayin(AvlTreeT);
intHeight(PositionP);
#endif

#include<stdio.h>
#include<malloc.h>
#include"AvlTree.h"
intHeight(PositionP)
{
	if(P==NULL)
		return-1;
	elsereturnP->Height;
}
PositionFindMax(AvlTreeT)
{
	if(T!=NULL)
		while(T->Right!=NULL)
			T=T->Right;
		returnT;
}
PositionFindMin(AvlTreeT)
{
	if(T==NULL)
		returnNULL;
	else
		if(T->Left==NULL)
			returnT;
		else
			returnFindMin(T->Left);
}
Max(inta,intb)
{
	if(a>b)
		returna;
	else
		returnb;
	
	returnb;
}
staticPositionSingleRotateWithLeft(Positionk2)
{
	Positionk1;
	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),k2->Height)+1;
	returnk1;
}
staticPositionSingleRotateWithRight(Positionk3)
{
	Positionk4;
	k4=k3->Right;
	k3->Right=k4->Left;
	k4->Left=k3;
	k3->Height=Max(Height(k3->Right),Height(k3->Left))+1;
	k4->Height=Max(Height(k4->Right),k4->Height)+1;
	returnk4;
}
staticPositionDoubleRotateWithLeft(Positionk5)
{
	k5->Left=SingleRotateWithRight(k5->Left);
	returnSingleRotateWithLeft(k5);
}
staticPositionDoubleRotateWithRight(Positionk6)
{
	k6->Right=SingleRotateWithLeft(k6->Right);
	returnSingleRotateWithRight(k6);
}

AvlTreeMakeEmpty(AvlTreeT)
{
	T=(structAvlNode*)malloc(sizeof(structAvlNode));
	if(T!=NULL)
	{
		T->Left=T->Right=NULL;
T->Height=0;	
	}
	returnT;
}
AvlTreeInsert(ElementTypex,AvlTreeT)
{
	if(T==NULL)
	{
		T=(structAvlNode*)malloc(sizeof(structAvlNode));
		if(T==NULL)
			printf("Outofspace");
		else
		{
			T->Element=x;
			T->Height=0;
			T->Left=T->Right=NULL;