/*贴一个二叉平衡排序树让大家实践一下*/
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>


typedef int typekey;
typedef struct avlnode { /*高度平衡树节点 */
typekey k; /*键*/
char *v; /*值 */
int bal;
/*平衡因子，当 bal==[-1,0,1] 时平衡，分别对应于左子树*/
/*高过右子树一层，左右子树高度相同，右子树高过左子树一层 */
struct avlnode *left, *right; /* 指向子树的指针 */
} node, *tree;


tree search(typekey, tree);
tree insert(typekey, tree);
tree deletef(typekey, tree);
int height(tree);
int count(tree);
tree deltree(tree);
static tree lrot(tree);
static tree rrot(tree);
static node* newNode(void);
static void freeNode(node*);
static void Error(void);

static int flag; /* 高度增减标志 */
int Win_x;
/*================================================*/


/*二叉树查找*/

tree search(typekey key, tree t)
{
while(t != NULL)
if (t->k == key)
return t;
else if (t->k < key)
t = t->right;
else
t = t->left;
return NULL;
}
/*插入例程。*/

tree insert(typekey key, tree t)
{

if(t == NULL){ /* 当前节点为空 */
   t = newNode(); /*建立新节点 */
t->k = key;
t->left = NULL;
t->right = NULL;
   t->bal = 0; /* 叶子节点等高平衡 */
   flag = 1; /* 高度增加 */
}
else if(t->k == key)/*键已经在表中*/
   Error();
   else {
   if(t->k < key){
   t->right = insert(key, t->right);
   t->bal += flag; /* 右子树高度增加 */
   } else {
   t->left = insert(key, t->left);
   t->bal -= flag; /*左子树高度增加 */
}
/* 某个子树增加了高度，并且两个子树高度不相同 */
if(flag != 0 && t->bal != 0){
/* 左子树高于右子树两层: 需要右旋 */
if(t->bal < -1) {
/* 当前节点的左子节点偏右平衡 */
if(t->left->bal > 0)
/* 使当前节点的左子节点偏左平衡 */
t->left = lrot(t->left);
t = rrot(t);
flag = 0; /* 本节点的高度不增加 */
}
/* 右子树高于左子树两层: 需要左旋 */
else if(t->bal > 1) {
/*当前节点的右子节点左平衡 */
if(t->right->bal < 0)
/*使当前节点的右子节点偏右平衡 */
t->right = rrot(t->right);
t = lrot(t);
flag = 0; /* 本节点的高度不增加*/
}
else /*某个子树高度增加了，破坏了等高平衡 */
flag = 1; /* 本节点的高度增加 */
  }
     else
/*它的子树未增加高度，或者某个子树增加高度后导致等高平衡 */
     flag = 0;/* 本节点的高度不增加*/
}
return(t);
}
/*删除*/

tree deletef(typekey key, tree t)
{
tree p;
char * temp;
if(t == NULL) /*未找到 */
Error();
/* 键找到 */
else if (t->k == key) {
  /* 有一个子树为空 */
if (t->left == NULL) {
p = t;
t = t->right;
freeNode(p);
flag = 1; /* 高度减少 */
return(t); /* 无需调整平衡 */
}
else if (t->right == NULL) {
p = t;
t = t->left;
freeNode(p);
flag = 1; /* 有高度变化*/
return(t); /* 无需调整平衡 */
/* 没有一个子树为空 */
} else {
if(t->bal<0) {
/* 找到前驱节点 */
p = t->left;
while (p->right != NULL)
p = p->right;
t->k = p->k;
temp = t->v;
t->v = p->v;
p->v = temp;
t->left  = deletef(p->k, t->left);
t->bal += flag; /* 左子树高度减少 */
} else {
/* 找到后继节点 */
p = t->right;
while (p->left != NULL)
p = p->left;
t->k = p->k;
temp = t->v;
t->v = p->v;
p->v = temp;
t->right  = deletef(p->k, t->right);
t->bal -= flag; /* 右子树高度减少*/
}
}
}
/* 当前节点不是要删除的，继续查找*/
else if(t->k < key) {
t->right = deletef(key, t->right);
t->bal -= flag; /* 右子树高度减少 */
}
else {
t->left  = deletef(key, t->left);
t->bal += flag; /*左子树高度减少 */
}
  if (flag == 0 )
return(t); /* 无需调整平衡 */
/*某个子树减少了高度，并且两个子树高度不相同 */
if(t->bal != 0){
/* 左子树高于右子树两层: 需要右旋 */
if(t->bal < -1) {
/* 当前节点的左子节点偏右平衡 */
if(t->left->bal > 0) {
/* 使当前节点的左子节点偏左平衡 */
t->left = lrot(t->left);
flag = 1;/* 本节点的高度减少 */
}
else if (t->left->bal == 0)
flag = 0;/*本节点的高度不减少 */
    else
flag = 1;/* 本节点的高度减少 */
t = rrot(t);
   }
/* 右子树高于左子树两层: 需要左旋 */
else if(t->bal > 1) {
/*当前节点的右子节点左平衡 */
if(t->right->bal < 0) {
/* 使当前节点的右子节点偏右平衡 */
t->right = rrot(t->right);
flag = 1;/* 本节点的高度减少 */
}
else if (t->right->bal == 0)
flag = 0;/*本节点的高度不减少 */
    else
flag = 1;/* 本节点的高度减少 */
     t = lrot(t);
}
else /* 某个子树高度减少了，破坏了等高平衡 */
flag = 0; /* 本节点的高度不减少 */
}
/*某个子树减少高度后导致等高平衡 */
else
flag = 1; /* 本节点的高度减少 */
return(t);
}

/*
* 左旋例程
*            X              Y
*           / \            / \
*          A   Y    ==>   X   C
*             / \        / \
*            B   C      A   B
* 前提：X 偏右不平衡, Y 偏右或等高平衡。
*/

/*------------------------------------------*/
static tree lrot(tree t)
{
tree temp;
int x,y;

temp = t;
t = t->right;
temp->right = t->left;  
t->left = temp;
x = temp->bal;
y = t->bal;
/*旋转之前：*/
/* 假定 X 的平衡因子是 x, Y 的平衡因子是 y,
/* * 设 A 的高度为 h, 则 Y 的高度为 h+x
 /** 节点 B 高度为 h+x-1-max(y,0);
 /** 节点 C 的高度为 h+x-1+min(y,0);
 /** 旋转之后：
/* * 节点 X 的新平衡因子是 x-1-max(y,0);
/* * 节点 Y 的新平衡因子是 C-(max(A,B)+1) => min(C-A-1,C-B-1)
/* *     => min(x-2+min(y,0),y-1) => min(min(x+y-2,x-2),y-1)*/

temp->bal = x-1-max(y, 0);
t->bal = min(x-2+min(y, 0), y-1);
return(t);
}
/*
* 右旋例程
*            X              Y
*           / \            / \
*          Y   C    ==>   A   X
*         / \                / \
*        A   B              B   C
* 前提：X 偏左不平衡，Y 偏左或等高平衡。
*/
static tree rrot(tree t)
{
tree temp;
int x,y;

temp = t;
t = t->left;
temp->left = t->right;
t->right = temp;
x = temp->bal;
y = t->bal;
/** 旋转之前：
/** 假定 X 的平衡因子是 x, 节点 Y 的平衡因子是 y,
 /** 设 C 的高度为 h, 则 Y 的高度为 h-x-1
 /** 节点 A 高度为 h-x-1-max(y,0);
 /** 节点 B 的高度为 h-x-1+min(y,0);
 /** 旋转之后：
 /** 节点 X 的新平衡因子是 x+1-min(y,0)
 /** 节点 Y 的新平衡因子是 max(B,C)+1-A => max(B-A+1,C-A+1)
 /**     => max(y+1,x+2+max(y,0))*/
 
temp->bal = x+1-min(y, 0);
t->bal = max(x+2+max(y, 0), y+1);
return(t);
}

static void Error(void)
{
printf("\nError: insert or delete key\n");
}
static node* newNode(void)
{
node* p;
p=(node*)calloc(1,sizeof(node));
p->v=NULL;
return p;
}

static void freeNode(node * p)
{
if (p->v != NULL)
free(p->v);
free(p);
}

int height(tree t)
{
if (t == NULL)
return 0;
else
return 1+max(height(t->left),height(t->right));
}
int count(tree t)
{
if (t == NULL)
return 0;
else
return 1+count(t->left)+count(t->right);
}

tree deltree(tree t)
{
if (t != NULL) {
t->left=deltree(t->left);
t->right=deltree(t->right);
freeNode(t);
}
return NULL;
}
void preorder(tree p){
if(p!=NULL){
printf("%d,",p->k);
preorder(p->left);
preorder(p->right);
}
}
void inorder(tree p,int y){

if(p!=NULL){

inorder(p->left,y+2);
gotoxy(Win_x-1,y);
printf("(%d)",p->k);
Win_x=Win_x+1;
inorder(p->right,y+2);
}
else
{
gotoxy(Win_x,y);
printf(" . ");
Win_x=Win_x+2;
}
}

/*void print(tree b)/*输出二叉树函数
{
   if(b!=NULL)
   {
   printf("%d",b->k);
   if(b->left!=NULL||b->right!=NULL)
   {
   printf("(");
   print(b->left);
   if(b->right!=NULL)
   printf(",");
       printf(")");
   }
   }
}*/
main(){
tree T=NULL;
typekey key=0;
int a;
int y=1;
Win_x=1;
printf("\nCreat the tree:(Break after zero)(0)\n");
do{
scanf("%d",&key);
        if(key!=0)
T=insert(key,T);
}while(key!=0);
for(;;){
printf("\n");
    printf("\n\n1..Insert. 2..Del key! 3..dispay! 4..exit!\n");
scanf("%d",&a);
switch(a){
case 1:
printf("What insert?\n");
scanf("%d",&key);
T=insert(key,T);
break;
case 2:
printf("Del witch one?\n");
scanf("%d",&key);
T=deletef(key,T);
break;
case 3:

printf("\n\n");
getch();
clrscr();
Win_x=2;
inorder(T,y);
printf("\n\n");
 break;
case 4: exit(0);
}
}
}

/*Use turboc2 please!*/


没人顶一下吗？

不错

不错

对于我来说还是有点深奥,因为我还没有学到,但无论如何都一个很好的函数,那就顶一下啦