AVL搜索树相关源代码

AVL树又被称为平衡二叉树

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<iostream>
using namespace std;
typedef struct AVLTree{
	int nData;
	struct AVLTree *pLeft;
	struct AVLTree *pRight;
	int nHeight;
}AVLTree;
int Max(int a, int b);
int Height(AVLTree * pNode);
AVLTree * Insert(int nData, AVLTree *pNode);
AVLTree * LLRotate(AVLTree * pNode);
AVLTree * RRRotate(AVLTree *pNode);
AVLTree * LRRotate(AVLTree * pNode);
AVLTree * RLRotate(AVLTree * pNode);
void DeleteTree(AVLTree ** ppRoot);
void printTree(AVLTree * pRoot);

int main()
{
	int i;
	AVLTree *pRoot=NULL;
	srand((unsigned int)time(NULL));
	for(i=0;i<10;i++){
		pRoot=Insert(rand()%100, pRoot);
	}
	printTree(pRoot);
	return 0;
}
int Max(int a, int b)
{
	return (a>b?a:b);
}
int Height(AVLTree * pNode)
{
	if(NULL==pNode)
		return -1;
	return pNode->nHeight;
}
AVLTree * Insert(int nData, AVLTree * pNode)
{
	if(NULL==pNode)
	{
		pNode=(AVLTree *)malloc(sizeof(AVLTree));
		pNode->nData=nData;
		pNode->nHeight=0;
		pNode->pLeft=pNode->pRight=NULL;
	}else if(nData<pNode->nData)
	{
		pNode->pLeft=Insert(nData,pNode->pLeft);
		if(Height(pNode->pLeft)-Height(pNode->pRight)==2)
		{
			if(nData<pNode->pLeft->nData){
				pNode=LLRotate(pNode);
			}else{
				pNode=LRRotate(pNode);
			}
		}
	}else if(nData>pNode->nData)
	{
		pNode->pRight=Insert(nData,pNode->pRight);
		if(Height(pNode->pRight)-Height(pNode->pLeft)==2)
		{
			if(nData>pNode->pRight->nData){
				pNode=RRRotate(pNode);
			}else{
				pNode=RLRotate(pNode);
			}
		}
	}
	pNode->nHeight=Max(Height(pNode->pLeft),Height(pNode->pRight))+1;
	return pNode;
}
AVLTree * LLRotate(AVLTree * pNode)
{
	AVLTree * pNode1;
	pNode1=pNode->pLeft;
	pNode->pLeft=pNode1->pRight;
	pNode1->pRight=pNode;
	pNode->nHeight=Max(Height(pNode->pLeft),Height(pNode->pRight))+1;
	pNode1->nHeight=Max(Height(pNode1->pLeft),pNode->nHeight)+1;
	return pNode1;
}
AVLTree * RRRotate(AVLTree * pNode)
{
	AVLTree * pNode1;
	pNode1=pNode->pRight;
	pNode->pRight=pNode1->pLeft;
	pNode1->pLeft=pNode;
	pNode->nHeight=Max(Height(pNode->pLeft),Height(pNode->pRight))+1;
	pNode1->nHeight=Max(Height(pNode1->pRight),pNode->nHeight)+1;
	return pNode1;
}
AVLTree * LRRotate(AVLTree *pNode)
{
	pNode->pLeft=RRRotate(pNode->pLeft);
	return LLRotate(pNode);
}
AVLTree * RLRotate(AVLTree *pNode)
{
	pNode->pRight=LLRotate(pNode->pRight);
	return RRRotate(pNode);
}
void DeleteTree(AVLTree **ppRoot)
{
	if(NULL==ppRoot ||NULL==*ppRoot)
		return ;
	DeleteTree(&((*ppRoot)->pLeft));
	DeleteTree(&((*ppRoot)->pRight));
	free(*ppRoot);
	*ppRoot=NULL;
}
void printTree(AVLTree * pRoot)
{
	if(NULL==pRoot)
	return;
	static int n=0;
	printTree(pRoot->pLeft);
	printf("[%d]nData=%d %d\n",++n,pRoot->nData,pRoot->nHeight);
	printTree(pRoot->pRight);
}