[color=008000][b]版主求助：平衡二叉树的编程！[/b][/color]
小弟遇到了一道难题：
已知某排序平衡二叉树T具有下列特点：
（1）结点的关键字均在1到9范围为内；
（2）在T中存在一个关键字为n1的叶结点，若删去该结点，立即插入一个关键字为n1的结点，得到的平衡树与原T不同；
（3）在T中存在一个关键字为n2的非叶结点，若删去该结点，立即插入n2结点，得到与原T相同的平衡树；
（4）在T中插入某n3结点并立即删去它，得到的平衡树与原T不同。
试通过程序输出具有上述特点的最简单（结点个数最少）的平衡二叉树T，并写明n1，n2，n3分别等于几？
恳请大家帮忙解决，谢谢！

我的QQ：751217908.
邮箱：ltxbs81@126.com 


书上的是采用AVL方法实现平衡树的。
抄了书本中的相关程序如下：
AVL树的结点声明；
typedef struct avlnode
{
    int height;//比普通二杈有序树多了一个高度信息 
    ElemType data;
    struct bnode *lchild, *rchild;
} *AvlTree, *Position;    
//----------AVL树基本操作------------ ------------------------------
AvlTree MakeEmpty(AvlTree T);
Position Find(ElemType x, AvlTree T);
Position FindMin(AvlTree T);
Position FindMax(AvlTree T);
static int Height(Position P);
AvlTree Insert(ElemType x, AvlTree T);
AvlTree Delete(ElemType x, AvlTree T);
ElemType Retrieve(Position P);

//----------AVL树基本操作的算法实现--------------------
递归算法： 
Position FindMin(AvlTree T)
{
    if(T==NULL)
        return NULL;
    else if(T->lchild == NULL)
        return T;
    else
        return FindMin(T->lchild);
}

Position FindMax(AvlTree T)
{
    if(T==NULL)
        return NULL;
    else if(T->rchild == NULL)
        return T;
    else
        return FindMax(T->rchild);
}
非递归算法：
Position FindMin(AvlTree T)
{
    if(T!=NULL)
    {
        while(T->lchild != NULL)
            T = T->lchild;
    }
    
    return T;
}

Position FindMax(AvlTree T)
{
    if(T!=NULL)
    {
        while(T->rchild != NULL)
            T = T->rchild;
    }
    
    return T;
}
//返回P点的高度 
static int Height(Position P)
{
    if(P==NULL)
        return -1;
    else
        return P->height;
}
//在对一棵AVL树进行插入操作后，可能会破坏它的平衡条件，因此必须对新的AVL树进行调整，
这里用到了“单旋转”或“双旋转”的算法，分别适用于：
单左旋转（SingleRotateWithLeft）；对结点p的左孩子的左子树进行一次插入 
单右旋转（SingleRotateWithRight）；对结点p的右孩子的右子树进行一次插入  
双左旋转（DoubleRotateWithLeft）；对结点p的左孩子的右子树进行一次插入 
双右旋转（DoubleRotateWithRight）；对结点p的右孩子的左子树进行一次插入  
static Position SingleRotateWithLeft(Position K2)
{
    Position K1;
    
    K1 = K2->lchild;  //在K2和K1之间进行一次单左旋转 
    K2->lchild = K1->rchild;
    K1->rchild = K2;
    
    K2->height = Max(Height(K2->lchild), Height(K2->rchild)) + 1;
    K1->height = Max(Height(K1->lchild), Height(K1->rchild)) + 1;
    
    return K1;
}

static Position SingleRotateWithRight(Position K2)
{
    Position K1;
    
    K1 = K2->rchild;    //在K2和K1之间进行一次单右旋转 
    K2->rchild = K1->lchild;
    K1->lchild = K2;
    
    K2->height = Max(Height(K2->lchild), Height(K2->rchild)) + 1;
    K1->height = Max(Height(K1->lchild), Height(K1->rchild)) + 1;
    
    return K1;
}

static Position DoubleRotateWithLeft(Position K3)
{
    K3->lchild = SingleRotateWithRight(K3->lchild); //在K2和K1之间进行一次单右旋转 
    
    return SingleRotateWithLeft(K3); //在K3和K2之间进行一次单左旋转 
}

static Position DoubleRotateWithRight(Position K3)
{
    K3->rchild = SingleRotateWithLeft(K3->rchild); //在K2和K1之间进行一次单左旋转 
    
    return SingleRotateWithRight(K3);//在K3和K2之间进行一次单右旋转 
}

//向AVL树插入结点的操作 
AvlTree Insert(float x, AvlTree T)
{
    if(T == NULL)
    {
        T = (Position)malloc(sizeof(struct avlnode));
        if(T == NULL)
        {
            puts("wrong"); 
            exit(1);
        }
        T->data = x;  
        T->height = 0;
        T->lchild = T->rchild = NULL;
    }
    else if(T->data == x)//不做任何插入操作 
        ;
    else if(T->data > x)//把s所指结点插入到左子树中
    {
          T->lchild = Insert(x, T->lchild);
          if(Height(T->lchild) - Height(T->rchild) == 2) //若平衡被破坏
          {
            if(x < T->lchild->data)     //若x比T的左孩子小，对T单左旋转  
                T = SingleRotateWithLeft(T);
            else                         //否则，对T双左旋转   
                T = DoubleRotateWithLeft(T);
        }
    }
    else      //把s所指结点插入到右子树中
    {
          T->rchild = Insert(x, T->rchild);
          if(Height(T->rchild) - Height(T->lchild) == 2)
          {
            if(x > T->rchild->data)    //若x比T的右孩子大，对T单右旋转  
                T = SingleRotateWithRight(T);
            else                        //否则，对T双右旋转   
                T = DoubleRotateWithRight(T);
        }
    }
    T->height = Max(Height(T->lchild), Height(T->rchild)) + 1;
    
    return T;   
}
int Max(int a, int b)
{
    if(a > b)
        return a;
    else
        return b;
}