使用二叉链表存储二叉排序树，主要功能有：生成一棵二叉排序树T；计算二叉排序树T的平均查找长度，输出结果；插入元素x，重新计算二叉排序树T的平均查找长度以及统计各结点所在的层次；输入元素x，查找二叉排序树T：若存在含x的结点，则删除该结点；否则输出信息“无x”；判断二叉排序树T是否为平衡二叉树；遍历二叉排序树等；
      实现图形化操作界面；将二叉排序树调整为平衡二叉树

程序
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<stack>

#define LH +1
#define EH 0
#define RH -1
#define NULL 0

using namespace std;

typedef struct BSTNode {
    int data;     
    int bf;                         //节点的平衡因子
    struct BSTNode *lchild,*rchild;    //左右孩子指针
}BSTNode,*BSTree;


void CreatBST(BSTree &T);        //创建平衡二叉树
void R_Rotate(BSTree &p);         //对以*p为根的二叉排序树作右旋处理
void L_Rotate(BSTree &p);         //对以*p为根的二叉排序树作左旋处理
void LeftBalance(BSTree &T);      //对以指针Ｔ所指结点为根的二叉树作左平衡旋转处理
void RightBalance(BSTree &T);    //对以指针Ｔ所指结点为根的二叉树作右平衡旋转处理
bool InsertAVL(BSTree &T,int e,bool &taller);          //插入结点e
bool SearchBST(BSTree &T,int key);                 //查找元素key是否在树T中
void LeftBalance_div(BSTree &p,int &shorter);        //删除结点时左平衡旋转处理
void RightBalance_div(BSTree &p,int &shorter);       //删除结点时右平衡旋转处理
void Delete(BSTree q,BSTree  &r,int &shorter);       //删除结点
int DeleteAVL(BSTree &p,int x,int &shorter);          //平衡二叉树的删除操作
void PrintBST(BSTree T,int m);                     //按树状打印输出二叉树的元素

void preOrder(BSTree T)     //非递归前序遍历
{
    stack<BSTree> s;
    BSTree p=T;
    while(p!=NULL||!s.empty())
    {
        while(p!=NULL)
        {
            cout<<p->data<<" ";
            s.push(p);
            p=p->lchild;
        }
        if(!s.empty())
        {
            p=s.top();
            s.pop();
            p=p->rchild;
        }
    }
}
void inOrder(BSTree T)      //非递归中序遍历
{
    stack<BSTree> s;
    BSTree p=T;
    while(p!=NULL||!s.empty())
    {
        while(p!=NULL)
        {
            s.push(p);
            p=p->lchild;
        }
        if(!s.empty())
        {
            p=s.top();
            cout<<p->data<<" ";
            s.pop();
            p=p->rchild;
        }
    }   
}
void postOrder(BSTree T)     //非递归后序遍历
{
    stack<BSTree> s;
    BSTree c;                      //当前结点
    BSTree e=NULL;                 //前一次访问的结点
    if(T){
      s.push(T);
    }
    while(!s.empty())
    {
        c=s.top();
        if((c->lchild==NULL&&c->rchild==NULL)||
           (e!=NULL&&(e==c->lchild||e==c->rchild)))
        {
            cout<<c->data<<" ";  //如果当前结点没有孩子结点或者孩子节点都已被访问过
              s.pop();
            e=c;
        }
        else
        {
            if(c->rchild!=NULL)
                s.push(c->rchild);
            if(c->lchild!=NULL)   
                s.push(c->lchild);
        }
    }   
}



void CreatBST(BSTree &T)
{
    int depth;
    int e;
    bool taller=false;
    T = NULL;
    printf("\n请输入关键字(继续输入关键字按回车，输入-0则生成二叉树)：");
    scanf("%d",&e);
    getchar();
    while(e != -0)
    {
        
        InsertAVL(T,e,taller);
        printf("\n请输入关键字(继续输入关键字按回车，输入-0则生成二叉树)：");
        scanf("%d",&e);
        getchar();
        taller=false;
    }
    depth=0;
    printf("\n****************************************************\n");
    printf("                 二叉树的遍历结果为\n");
    printf("\n先根遍历：");
    preOrder(T);
    printf("\n中根遍历：");
    inOrder(T);
    printf("\n后根遍历：");
    postOrder(T);
    printf("\n");
    printf("\n****************************************************\n");
    printf("                 您创建的二叉树为\n");
    if(T)
        PrintBST(T,depth);
    else
        printf("这是一棵空树!\n");
}

void R_Rotate (BSTree &p)    //对以*p为根的二叉排序树作右旋处理
{
    BSTree lc;
    lc=p->lchild;
    p->lchild=lc->rchild;
    lc->rchild=p;
    p=lc;
}

void L_Rotate(BSTree &p)   //对以*p为根的二叉排序树作左旋处理
{
    BSTree rc;
    rc=p->rchild;
    p->rchild=rc->lchild;
    rc->lchild=p;
    p=rc;
}

void LeftBalance(BSTree &T)    //对以指针Ｔ所指结点为根的二叉树作左平衡旋转处理
{
    BSTree lc,rd;
    lc=T->lchild;
    switch(lc->bf)
    {
    case LH:
        T->bf=lc->bf=EH;
        R_Rotate(T);
        break;
    case RH:
        rd=lc->rchild;
        switch(rd->bf)
        {
        case LH:
            T->bf=RH;lc->bf=EH;break;
        case EH:
            T->bf=lc->bf=EH;break;
        case RH:T->bf=EH;lc->bf=LH;break;
        }
        rd->bf=EH;
        L_Rotate(T->lchild);
        R_Rotate(T);
    }
}

void RightBalance(BSTree &T)     //对以指针Ｔ所指结点为根的二叉树作右平衡旋转处理
{
    BSTree rc,ld;
    rc=T->rchild;
    switch(rc->bf)
    {
    case RH:
        T->bf=rc->bf=EH;
        L_Rotate(T);
        break;
    case LH:
        ld=rc->lchild;
        switch(ld->bf)
        {
        case RH:T->bf=LH;rc->bf=EH;break;
        case EH:T->bf=rc->bf=EH;break;
        case LH:T->bf=EH;rc->bf=RH;break;
        }
        ld->bf=EH;
        R_Rotate(T->rchild);
        L_Rotate(T);
    }
}

bool InsertAVL(BSTree &T,int e,bool &taller)  //插入结点e
{
    if(!T)
    {
        T=(BSTree)malloc(sizeof(BSTNode));
        T->data=e;
        T->lchild=T->rchild=NULL;
        T->bf=EH;
        taller=true;
    }
    else{
        if(e==T->data)
        {
            taller=false;
            printf("已存在相同关键字的结点!\n");
            return 0;
        }
        if(e<T->data)
        {
            if(!InsertAVL(T->lchild,e,taller))
                return 0;
            if(taller)
                switch(T->bf)
            {
                case LH:
                    LeftBalance(T);taller=false;break;
                case EH:
                    T->bf=LH;taller=true;break;
                case RH:
                    T->bf=EH;taller=false;break;
            }
        }
        else{
            if(!InsertAVL(T->rchild,e,taller))
                return 0;
            if(taller)
                switch(T->bf)
            {
                case LH:
                    T->bf=EH;taller=false;break;
                case EH:
                    T->bf=RH;taller=true;break;
                case RH:
                    RightBalance(T);taller=false;break;
            }
        }
    }
}

bool SearchBST(BSTree &T,int key)   //查找元素key是否在树Ｔ中
{
    if(!T)
        return false;
    else if(key==T->data)
        return true;
    else if(key<T->data)
        return SearchBST(T->lchild,key);
    else
        return SearchBST(T->rchild,key);
}
void LeftBalance_div(BSTree &p,int &shorter)     //删除结点时左平衡旋转处理
{
    BSTree  p1,p2;
    if(p->bf==1)
    { p->bf=0; shorter=1; }
    else if(p->bf==0)
    { p->bf=-1; shorter=0; }
    else  
    {
        p1=p->rchild;
        if(p1->bf==0)
        {
            L_Rotate(p);
            p1->bf=1; p->bf=-1; shorter=0;
        }
        else if(p1->bf==-1)
        {
            L_Rotate(p);
            p1->bf=p->bf=0; shorter=1;
        }
        else
        {
            p2=p1->lchild;
            p1->lchild=p2->rchild; p2->rchild=p1; p->rchild=p2->lchild; p2->lchild=p;
            if(p2->bf==0)
            { p->bf=0; p1->bf=0; }
            else if(p2->bf==-1)
            { p->bf=1;p1->bf=0; }
            else
            { p->bf=0;p1->bf=-1; }
            p2->bf=0; p=p2; shorter=1;
        }
  }
}
void RightBalance_div(BSTree &p,int &shorter)    //删除结点时右平衡旋转处理
{
    BSTree  p1,p2;
    if(p->bf==-1)
    { p->bf=0; shorter=1; }
    else if(p->bf==0)
    { p->bf=1; shorter=0; }
    else
    {
        p1=p->lchild;
        if(p1->bf==0)
        {
            R_Rotate(p);
            p1->bf=-1; p->bf=1; shorter=0;
        }
        else if(p1->bf==1)
        {
            R_Rotate(p);
            p1->bf=p->bf=0; shorter=1;
        }
        else
        {
            p2=p1->rchild;
            p1->rchild=p2->lchild; p2->lchild=p1; p->lchild=p2->rchild; p2->rchild=p;
            if(p2->bf==0)
            { p->bf=0; p1->bf=0; }
            else if(p2->bf==1)
            { p->bf=-1; p1->bf=0; }
            else
            { p->bf=0; p1->bf=1; }
            p2->bf=0; p=p2; shorter=1;
        }
    }
}
void Delete(BSTree q,BSTree  &r,int &shorter)         //删除结点
{
    if(r->rchild==NULL)
    {
        q->data=r->data; q=r;
        r=r->lchild; free(q);
        shorter=1;
    }
    else
    {
        Delete(q,r->rchild,shorter);
        if(shorter==1)
            RightBalance_div(r,shorter);
    }
}
int DeleteAVL(BSTree &p,int x,int &shorter)      //平衡二叉树的删除操作
{
    int k;
    BSTree q;
    if(p==NULL)  { printf("不存在要删除的关键字!\n"); return 0;}
    else if(x<p->data)
    {
        k=DeleteAVL(p->lchild,x,shorter);
        if(shorter==1)
            LeftBalance_div(p,shorter);
        return k;
    }
    else if(x>p->data)
    {
        k=DeleteAVL(p->rchild,x,shorter);
        if(shorter==1)
            RightBalance_div(p,shorter);
        return k;
    }
    else
    {
        q=p;
        if(p->rchild==NULL)
        { p=p->lchild; free(q); shorter=1; }
        else if(p->lchild==NULL)
        { p=p->rchild; free(q); shorter=1; }
        else
        {
            Delete(q,q->lchild,shorter);
            if(shorter==1)
                LeftBalance_div(p,shorter);
            p=q;
        }
       return 1;
    }
}

void PrintBST(BSTree T,int depth)
{
    int i;
        if(T->rchild)
            PrintBST(T->rchild,depth+1);
        for(i=1;i<=depth;i++)
            printf("     ");
        printf("%d\n",T->data);
        if(T->lchild)
            PrintBST(T->lchild,depth+1);
}

//主函数
void main()
{
    BSTree T;
    int sear,cmd,depth;
    char ch;
    int shorter=0;
    bool taller=false;
    T=(BSTree)malloc(sizeof(BSTNode));
    T=NULL;

    do
    {   
        printf("\t\t\t   程序主菜单\n");
        printf("\t☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆\n");
            printf("\t★                                              ★\n");
        printf("\t☆\t  1. 输入节点生成二叉树及遍历           ☆\n");
            printf("\t★                                              ★\n");
        printf("\t☆\t  2. 查找并删除节点                     ☆\n");
            printf("\t★                                              ★\n");
            printf("\t☆\t  3. 插入节点                           ☆\n");
            printf("\t★                                              ★\n");
        printf("\t☆\t  4. 清空并结束                         ☆\n");
            printf("\t★                                              ★\n");
        printf("\t☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆\n");
        printf("请输入上述序号进行操作：");
        scanf("%d",&cmd);
        getchar();
        switch(cmd)
        {
        case 1:
            CreatBST(T);break;
        case 2:
            depth=0;
            printf("请输入要查找的关键字：");
                scanf("%d",&sear);getchar();
            if(SearchBST(T,sear))   
            {    DeleteAVL(T,sear,shorter);
            PrintBST(T,depth);
            printf("关键字%d已找到!\n",sear);}
            else printf("查找失败!\n");
            break;
        case 3:
            printf("请输入要插入的关键字：");
                scanf("%d",&sear);getchar();
            InsertAVL(T,sear,taller);depth=0;
            PrintBST(T,depth);
            break;
        
        case 4:
            printf("结束!\n");
            break;
        default:
            printf("输入错误!\n");
        }
        if(cmd==5)
            break;
        printf("\n继续吗？ y/n：");
        scanf("%s",&ch);
        getchar();
        printf("\n");
    }while(ch=='y');
    printf("\n");
}

既然用C++ 为什么不 封装 起来

你未实现那些功能？没思路还是写不来？

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)< (b))
#define LQ(a,b) ((a)<=(b))

#define TRUE 1
#define FALSE 0
#define OVERFLOW -2
#define N 50


typedef int KeyType;
typedef int Status;

typedef struct{
    KeyType key; /*关键字域*/
}SElemType;
typedef struct BitNode{
    SElemType data; /*存储空间基址,建表时按实际长度分配，0号单元留空*/
    struct BitNode *lchild,*rchild;
}BitNode,* BiTree;

/*二叉排序树的插入*/
Status InsertBST(BiTree &T,KeyType key){
    BiTree s;
    if(!T){
        s=(BiTree)malloc(sizeof(BitNode));
        s->data.key=key;
        s->lchild=s->rchild=NULL;
        T=s;
    }
    else if LT(key,T->data.key)
        InsertBST(T->lchild,key);
    else InsertBST(T->rchild,key);
    return TRUE;
}
/*创建二叉排序树*/
void CreateBST(BiTree &T){
    KeyType key;
    T=NULL;
    scanf("%d",&key);
    while(key!=0){
        InsertBST(T,key);
        scanf("%d",&key);
    }
}
/*中序遍历*/
void InOrderTraverse(BiTree T){
    if(T){
        InOrderTraverse(T->lchild);
        printf("%4d",T->data.key);
        InOrderTraverse(T->rchild);
    }
}
/*输出二叉树*/
Status PrintTree(BiTree T,int n){
    if(T==NULL)return FALSE;
    PrintTree(T->rchild,n+1);
    for(int i=0;i<n;i++)
        printf("   ");
    printf("%d\n",T->data.key);
    PrintTree(T->lchild,n+1);
    return TRUE;
}



/*二叉排序树的查找*/
BiTree SearchBST(BiTree T,KeyType key){
    if(!T){return T;}
    else if EQ(key,T->data.key){return T;}
    else if LT(key,T->data.key) return SearchBST(T->lchild,key);
    else return SearchBST(T->rchild,key);
}


/*二叉排序树的删除*/

Status Delete(BiTree &p){
    BiTree q,s;
    if(!p->rchild){
        q=p;
        p=p->lchild;
        free(q);
    }
    else if(!p->lchild){
        q=p;
        p=p->rchild;
        free(q);
    }
    else{
        q=p;
        s=p->lchild;
        while(s->rchild){q=s;s=s->rchild;}
        p->data=s->data;
        if(q!=p) q->rchild=s->lchild;
        else  q->lchild=s->lchild;
        delete s;
    }
    return TRUE;
}

Status DeleteBST(BiTree &T,KeyType key){
    if(!T)return FALSE;
    else{
        if (EQ(key,T->data.key))return Delete(T);
        else
            if(LT(key,T->data.key))return DeleteBST(T->lchild,key);
            else return DeleteBST(T->rchild,key);
    }
}

void main() {
    BiTree b1,b2;
    KeyType key;
    int t;
begin:
   
   
     printf("\t\t\t   程序主菜单\n");
        printf("\t☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆\n");
            printf("\t★\t       1:创建二叉排序树                 ★\n");
        printf("\t☆\t       2:输出排序树                     ☆\n");
            printf("\t★\t       3:查找并删除结点                 ★\n");
        printf("\t☆\t       4:中序遍历                       ☆\n");
            printf("\t★\t       5:插入结点                       ★\n");
        printf("\t☆\t                                        ☆\n");
            printf("\t★\t       0:退出                           ★\n");
        printf("\t☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆\n");
        printf("请选择要进行的操作:");
    scanf("%d",&t);
    switch(t){
    case 1:
        printf("请输入关键字(0 为结束):");
        CreateBST(b1);
        PrintTree(b1,0);//排序树的结果打输出
        
        goto begin;
    case 2:PrintTree(b1,0);goto begin;
    case 3:
        printf("请输入要查找的关键字:");
        scanf("%d",&key);
        if(SearchBST(b1, key))
        {DeleteBST(b1, key);
            printf("\n发现该关键字\n 删除完毕！\n");
        }
        else printf("没有该关键字!!\n 删除失败\n");
        goto begin;
    case 4:InOrderTraverse(b1);
        printf("\n");
        goto begin;
    case 5:
        printf("输入要插入的数据：");
        scanf("%d",&key);
        if(InsertBST(b1, key))printf("\n插入完毕！\n");
        else printf("插入失败\n");
        goto begin;
    case 0:goto end;break;
    default: printf("输入错误\n");
    }
end:
    printf("\n谢谢使用!\n");
}



谢谢版主的指教。
不知道这个怎么加计算二叉排序树T的平均查找长度，输出结果，插入元素x，重新计算二叉排序树T的平均查找长度以及统计各结点所在的层次，判断二叉排序树T是否为平衡二叉树，将二叉排序树调整为平衡二叉树。

// 返回成功查找的总查找次数
int GetSumSearchLength(
BiTree root,  // 二叉树的根节点
int    depth; // 当前节点所在层数，初始传入 1
)
{
  if (null == root)  return 0;
  return depth + GetSumSearchLength(root->lchild, depth + 1)
               + GetSumSearchLength(root->rchild, depth + 1);
}

// 返回二叉树的节点总数
int GetNodeCount(
BiTree root   // 二叉树的根节点
)
{
    ....
}

// 返回二叉树查找成功的平均查找长度
double GetAvgSearchLength(
BiTree root   // 二叉树的根节点
)
{
    return (double) GetSumSearchLength(root, 1)
                  / GetNodeCount(root);
}

剩下的自己试着添，平衡树调整网上很多，就不多说了

恩，谢谢版主。