写完保存，居然没有成功，一大堆工作白费了。CSDN这个博客真是让我失望啊，Best4c中画图非常辛苦，可是画完了也白费了。
唉呀，现在就先把实现的源代码放这里吧，如果有读者要求我重新写算法分析并加上图片，我也会接着做。
既然如此了，说是修改那就简单提几点吧，AVL平衡树的实现是在二叉查找树的基础上实现的，和二叉查找树的区别只在于插入和删除这两个操作。
插入和删除都是递归的，
1。对于每次递归插入，都需要判断当前节点的左右子树是否平衡，如果不平衡则进行旋转调整，旋转分为左单旋转，左双旋转，右单旋转，和右双旋转.对于四种调整，均由一个单独的函数实现。
2。对于每次删除，如果被删除的节点左右孩子有空的：
如果左孩子为空则用右孩子接上，否则用左孩子接上。
如果左右孩子都不为空，则
当前要删除的节点和其右子树的最小节点交换值，然后递归的删除右子树的最小节点，对于删除路线中的每一个节点都要进行平衡调整（假如必要的话），此调整和1中的类似，只是我把它放在了一个单独的函数AVL_Rebanlence(t)里了。
可见，本AVL树的设计实现是相当优雅的，各功能都分模块实现了。
/***AVL树的实现分为两个文件AVLTree.h与AVLTree.c****/
/**AVLTree.h**/
/**********************************
*author:Felix
*last update:Sat Jan 12 06:12:15 EST 2008
*Address me and exchange our idea ^_^,QQ:349871604,e-mail:lzqziliao2004@163.com
*description:
*
*
*
*/
#ifndef ___AVLTREE___
#define ___AVLTREE___
#include<stdio.h>
#include<stdlib.h>
typedef int AVL_Element;
extern struct AVL_TreeNode;
typedef struct AVL_TreeNode *AVL_Tree;
typedef struct AVL_TreeNode *AVL_Position;
AVL_Tree AVL_MakeEmpty(AVL_Tree t);
AVL_Position AVL_Find(AVL_Element e,AVL_Tree t);
AVL_Position AVL_FindMin(AVL_Tree t);
AVL_Position AVL_FindMax(AVL_Tree t);
AVL_Tree AVL_Delete(AVL_Element e ,AVL_Tree t);
AVL_Tree AVL_Insert(AVL_Element e ,AVL_Tree t);
AVL_Element AVL_Retrieve(AVL_Position p);
#endif
/**AVLTree.c**/
/**********************************
*author:Felix
*last update:Sat Jan 12 06:12:15 EST 2008
*Address me and exchange our idea ^_^,QQ:349871604,e-mail:lzqziliao2004@163.com
*description:
*
*
*
*/
#include "AVLTree.h"
#define MAX(a,b) ((a>b)?a:b)
struct AVL_TreeNode
{
int height;
AVL_Element e;
AVL_Tree left;
AVL_Tree right;
};
static int Height(AVL_Position p)
{
if(p)return p->height;
return -1;
}
/*rotate function*/
AVL_Position AVL_SingleRotateLeft(AVL_Position p)
{
AVL_Position tmp;
tmp=p->left;
p->left=tmp->right;
tmp->right=p;
p->height=MAX(Height(p->left),Height(p->right))+1;
tmp->height=MAX(Height(tmp->left),p->height);
return tmp;
}
AVL_Position AVL_SingleRotateRight(AVL_Position p)
{
AVL_Position tmp;
tmp=p->right;
p->right=tmp->left;
tmp->left=p;
p->height=MAX(Height(p->left),Height(p->right))+1;
tmp->height=MAX(p->height,Height(tmp->right));
return tmp;
}
AVL_Position AVL_DoubleRotateRight(AVL_Position p)
{
p->right=AVL_SingleRotateLeft(p->right);
return AVL_SingleRotateRight(p);
}
AVL_Position AVL_DoubleRotateLeft(AVL_Position p)
{
p->left=AVL_SingleRotateRight(p->left);
return AVL_SingleRotateLeft(p);
}
AVL_Tree AVL_MakeEmpty(AVL_Tree t)
{
if(t)
{
AVL_MakeEmpty(t->left);
AVL_MakeEmpty(t->right);
free(t);
}
return NULL;
}
AVL_Position AVL_Find(AVL_Element e,AVL_Tree t)
{
if(t)
{
if(e>t->e)return AVL_Find(e,t->right);
else if(e<t->e)return AVL_Find(e,t->left);
else return (AVL_Position)t;
}
else return NULL;
}
/*find the minimum element*/
AVL_Position AVL_FindMin(AVL_Tree t)
{
if(t)
while(t->left)t=t->left;
return (AVL_Position)t;
}
/*find the maximum element*/
AVL_Position AVL_FindMax(AVL_Tree t)
{
if(t)
while(t->right)t=t->right;
return (AVL_Position)t;
}
static AVL_Tree AVL_Rebalance(AVL_Position p)
{
if(Height(p->left)-Height(p->right)==2)
{
if(Height(p->left->left)>Height(p->left->right))/*LL**/
{
return AVL_SingleRotateLeft(p);
}
else/*LR*/
{
return AVL_DoubleRotateLeft(p);
}
}
else
if(Height(p->left)-Height(p->right)==-2)
{
if(Height(p->right->right)>Height(p->right->left))/*RR**/
{
return AVL_SingleRotateRight(p);
}/*RL*/
else
{
return AVL_DoubleRotateRight(p);
}
}
}
static AVL_Tree AVL_DeleteMin(AVL_Tree t)
{
if(t->left){
t=AVL_DeleteMin(t->left);
return AVL_Rebalance(t);
}
else
{
free(t);
return NULL;
}
}
AVL_Tree AVL_Delete(AVL_Element e ,AVL_Tree t)
{
AVL_Position p;
if(t)
{
if(e>t->e)t->right=AVL_Delete(e,t->right);
else if(e<t->e) t->left=AVL_Delete(e,t->left);
/*find it*/
else if(t->left&&t->right)
{
p=AVL_FindMin(t->right);
t->e=p->e;
t->right=AVL_DeleteMin(t->right);
}
else
{
p=t;
if(t->left==NULL)t=t->right;
else t=t->left;
free(p);
}
}
return AVL_Rebalance(t);
}
AVL_Tree AVL_Insert(AVL_Element e ,AVL_Tree t)
{
if(t==NULL)/*insert as leaf child*/
{
t=(AVL_Tree)malloc(sizeof(struct AVL_TreeNode));
t->e=e;
t->left=t->right=NULL;
t->height=0;
}
else
if(e>t->e)
{
t->right=AVL_Insert(e,t->right);
if(Height(t->right)-Height(t->left)==2)
if(e>t->right->e)t=AVL_SingleRotateRight(t);
else t=AVL_DoubleRotateRight(t);
}else
if(e<t->e)
{
t->left=AVL_Insert(e,t->left);
if(Height(t->left)-Height(t->right)==2)
if(e<t->left->e)t=AVL_SingleRotateLeft(t);
else t=AVL_DoubleRotateLeft(t);
}
t->height=MAX(Height(t->left),Height(t->right))+1;
return t;
}
AVL_Element AVL_Retrieve(AVL_Position p)
{
return p->e;
}
/**测试文件包括testAVL.c menu_c.h menu_c.c以及前面文件（11）（文章为(12)）所实现drawBitTree.h/drawBitTree.c**/
/**testAVL.c**/
/*vgalib库可能不太稳定。
*author:Felix
*create date:Tue Jan 15 20:14:10 EST 2008
*last update:Tue Jan 15 20:14:10 EST 2008
*description:
*
*/
#include "menu_c.h"
#include<stdio.h>
#include<stdlib.h>
#include"AVLTree.h"
#include"drawBitTree.h"
struct AVL_TreeNode
{
int height;
AVL_Element e;
AVL_Tree left;
AVL_Tree right;
};
/******define some function to show the tree*******/
int getkey(void * t)
{
return ((AVL_Tree)t)->e;
}
void * getchild(void * t,int mode)
{
if(mode==DB_LEFTCHILD)return ((AVL_Tree)t)->left;
else return ((AVL_Tree)t)->right;
}
/*****************/
int main()
{
int n;
AVL_Tree t;
AVL_Position p;
t=AVL_MakeEmpty(NULL);
while(SELECT())
{
switch (SELECTION)
{
case '1':
printf("integer:>");
scanf("%d",&n);
t=AVL_Insert(n,t);
break;
case '2':
printf("integer to delete:>");
scanf("%d",&n);
if(!AVL_Find(n,t))printf("sorry,no integer match");
else {
t=AVL_Delete(n,t);
printf("deletion done");
}
break;
case '3':
while(p=AVL_FindMin(t))
{
printf("%d " ,AVL_Retrieve(p),t);
t= AVL_Delete(AVL_Retrieve(p),t);
}
break;
case '4':
while(p=AVL_FindMax(t))
{
printf("%d " ,AVL_Retrieve(p));
t=AVL_Delete(AVL_Retrieve(p),t);
}
break;
case '5':
if(!(p=AVL_FindMax(t)))printf("sorry,the tree is NULL");
else
printf("%d",AVL_Retrieve(p));
break;
case '6':
if(!(p=AVL_FindMin(t)))printf("sorry ,the tree is NULL");
else
printf("%d",AVL_Retrieve(p));
break;
case '7':
DB_DrawBitTree(t,getchild,getkey);
break;
case '9':
system("less ../AVL_tree.h");
break;
default:break;
}
}
return 0;
}
/**menu_c.h**/
/*///////////////////////
*author:Felix
*create date:Fri Jan 11 03:45:18 EST 2008
*last update:Fri Jan 11 03:45:18 EST 2008
*description:
*
*
*/////////////////////
#include <stdio.h>
#ifndef __MENU____
#define __MENU____
#define SELECT() ((___sel=___select())!='0')
#define SELECTION ___sel
char ___sel;
char ___select();
/*
define the menu:
*/
#endif
/**menu_c.c**/
/*///////////////////////
*author:Felix
*create date:Fri Jan 11 03:45:18 EST 2008
*last update:Fri Jan 11 03:45:18 EST 2008
*description:
*
*
*/////////////////////
#include "menu_c.h"
char *___menu[]={
"1.Insert a integer.",
"2.Delete an integer from the tree.",
"3.Sort and show from small to big(will delete the tree)",
"4.Sort and show from big to small(will delete the tree)",
"5.show the max",
"6.show the min", "9.Print the file ST_tree.h",
"7.show the tree",
"0.EXIT",
NULL
};
void ___showMenu()
{
printf("please select:/n");
char **p=___menu;
while(*p)printf("%s/n",*p++);
printf(":>");
}
char ___select()
{
char c;
___showMenu();
while((c=getchar())=='/n');
return c;
}
/**drawBitTree.h与drawBitTree.c的实现：***/
http://blog.csdn.net/liuzongqiang/archive/2008/01/16/2046194.aspx