#include
     
      #include
      
       #include
       
        using namespace std;#define MaxSize 100#define MaxWidth 40typedef char ElemType;typedef struct Node2{    char data;//数据域            struct Node2*lchild,*rchild;//左指针域，右指针域}BTNode;void CreateBTNode(BTNode *&b,char *str)//由str串创建二叉链{    BTNode *St[MaxSize],*p=NULL;    int top=-1,k,j=0;    char ch;    b=NULL;//建立二叉链初始时为空    ch=str[j];    while(ch!='\0')//str未扫描完时循环    {        switch(ch)        {        case'(':top++;St[top]=p;k=1;break;//为左结点        case')':top--;break;        case',':k=2;break;//为右结点        default:p=(BTNode *)malloc(sizeof(BTNode));            p->data=ch;            p->lchild=p->rchild=NULL;            if(b==NULL)//p指向二叉树的根结点                b=p;            else//已建立二叉树根结点            {                switch(k)                {                case 1:St[top]->lchild=p;break;                case 2:St[top]->rchild=p;break;                }            }        }        j++;        ch=str[j];    }}void createbitree(BTNode *&T)//先序产生二叉树{    char ch;    scanf("%c",&ch);    if(ch==' ')T=NULL;    else    {        T=(BTNode*)malloc(sizeof(BTNode));        T->data=ch;        createbitree(T->lchild);        createbitree(T->rchild);    }}BTNode *CreateBT1(char *pre,char *in,int n)//由先序和中序遍历序列构造二叉树{    BTNode *s;    char *p;    int k;    if(n<=0)return NULL;    s=(BTNode *)malloc(sizeof(BTNode));//创建二叉树结点*s    s->data=*pre;    for(p=in;p
        
         lchild=CreateBT1(pre+1,in,k);        s->rchild=CreateBT1(pre+k+1,p+1,n-k-1);        return s;}BTNode *CreateBT2(char *post,char *in,int n,int m)//由中序和后序遍历序列构造二叉树{    BTNode *s;    char *p,*q,*maxp;    int maxpost,maxin,k;    if(n<=0)return NULL;    maxpost=-1;    for(p=in;p
         
          maxpost)                {                    maxpost=k;                    maxp=p;                    maxin=p-in;                }            }    s=(BTNode *)malloc(sizeof(BTNode));//创建二叉树结点*s    s->data=post[maxpost];    s->lchild=CreateBT2(post,in,maxin,m);    s->rchild=CreateBT2(post,maxp+1,n-maxin-1,m);    return s;}void DispLeaf(BTNode *b)//输出一颗给二叉树放入所有叶子结点{    if(b!=NULL)    {        if(b->lchild==NULL&&b->rchild==NULL)            printf("%c",b->data);        else        {            DispLeaf(b->lchild);            DispLeaf(b->rchild);        }    }}BTNode*InsertLeftNode(BTNode *p,char x)//左结点插入{    BTNode *s,*t;    if(p==NULL)        return NULL;    t=p->lchild;    s=(BTNode*)malloc(sizeof(BTNode));    s->data=x;    s->lchild=t;    s->rchild=NULL;    p->lchild=s;    return p->lchild;}BTNode*InsertRightNode(BTNode *p,char x)//右结点插入   {    BTNode *s,*t;    if(p==NULL)        return NULL;    t=p->rchild;    s=(BTNode*)malloc(sizeof(BTNode));    s->data=x;    s->rchild=t;    s->lchild=NULL;    p->rchild=s;    return p->rchild;}BTNode *DleteLeaftTree(BTNode *p)//删除左结点{    BTNode *q;    if(p==NULL||p->lchild==NULL)        return NULL;    q=p->lchild;    p->lchild=NULL;    free(q);    q=NULL;    return p;}BTNode *DleteRightTree(BTNode *p)//删除右结点{    BTNode *q;    if(p==NULL||p->rchild==NULL)        return NULL;    q=p->rchild;    p->rchild=NULL;    free(q);    q=NULL;                                                                                                                                                                                                            return p;}BTNode *SearchNode(BTNode *b,char x)//查找结点{    BTNode *p;    if(b==NULL)        return NULL;    else if (b->data==x) return b;    else    {        p=SearchNode(b->lchild,x);        if(p!=NULL)            return p;        else            return SearchNode(b->rchild,x);    }}BTNode *lchildNode(BTNode *p)//查找左子树结点{    return p->lchild;}BTNode *RchildNode(BTNode *p)//查找右子树结点{    return p->rchild;}int BiTreeDepth(BTNode *b)//求高度{    int lchilddep,rchilddep;    if(b==NULL)return 0;    else    {        lchilddep=BiTreeDepth(b->lchild);        rchilddep=BiTreeDepth(b->rchild);        return (lchilddep>rchilddep)?(lchilddep+1):(rchilddep+1);    }}void DispBiTree(BTNode *b)//输出二叉树{    if(b!=NULL)    {        printf("%c",b->data);        if(b->lchild!=NULL||b->rchild!=NULL)        {            printf("(");            DispBiTree(b->lchild);            if(b->rchild!=NULL)            {                printf(",");                DispBiTree(b->rchild);            }            printf(")");        }    }}void DispBTNode1(BTNode *b)//以凹入表示法输出一颗二叉树{    BTNode *St[MaxSize],*p;    int level[MaxSize][2],top=-1,n,i,width=4;    char type;    if(b!=NULL)    {        top++;        St[top]=b;//根结点入栈        level[top][0]=width;        level[top][1]=2;//2表示是根        while(top>-1)        {            p=St[top];//退桟并凹入显示该结点值            n=level[top][0];            switch(level[top][1])            {            case 0:type='L';break;//左结点之后输出(L)            case 1:type='R';break;//右结点之后输出(R)            case 2:type='B';break;//根结点之后输出(B)            }            for(i=1;i<=n;i++)//其中n为显示场宽，字符以右对齐显示                printf(" ");            printf("%c(%c)",p->data,type);            for(i=n+1;i<=MaxWidth;i+=2)                printf("--");            printf("\n");            top--;            if(p->rchild!=NULL)            {                top++;//将右子树根结点入栈                St[top]=p->rchild;                level[top][0]=n+width;//显示场宽增width                level[top][1]=1;//1表示是右子树            }            if(p->lchild!=NULL)            {                top++;//将左子树根结点入栈                St[top]=p->lchild;                level[top][0]=n+width;//显示场宽增width                level[top][1]=0;//0表示是左子树            }        }    }}void PreOrder(BTNode *p)//先序遍历二叉树{    if(p!=NULL)    {        printf("%c",p->data);        PreOrder(p->lchild);        PreOrder(p->rchild);    }}void PreOrder1(BTNode *b)//先序遍历的非递归算法{    BTNode *St[MaxSize],*p;    int top=-1;    if(b!=NULL)    {        top++;//根结点入栈        St[top]=b;        while(top>-1)//桟不为空时循环        {            p=St[top];//退桟并访问该结点            top--;            printf(" %c ",p->data);            if(p->rchild!=NULL)//右孩子入桟            {                top++;                St[top]=p->rchild;            }            if(p->lchild!=NULL)//左孩子入桟            {                top++;                St[top]=p->lchild;            }        }        printf("\n");    }}void InOrder(BTNode *p)//中序遍历二叉树{    if(p!=NULL)    {        InOrder(p->lchild);        printf("%c",p->data);        InOrder(p->rchild);    }}void InOrder1(BTNode *b)//中序遍历的非递归算法{    BTNode *St[MaxSize],*p;    int top=-1;    if(b!=NULL)    {        p=b;        while(top>-1||p!=NULL)        {            while(p!=NULL)            {                top++;                St[top]=p;                p=p->lchild;            }            if(top>-1)            {                p=St[top];                top--;                printf(" %c ",p->data);                p=p->rchild;            }        }        printf("\n");    }}void PostOrder(BTNode *p)//后序遍历二叉树{    if(p!=NULL)    {        PostOrder(p->lchild);        PostOrder(p->rchild);        printf("%c",p->data);    }}void PostOrder1(BTNode *b)//后序遍历的非递归算法{    BTNode *St[MaxSize],*p;    int flag,top=-1;//桟指针初值    if(b!=NULL)    {        do        {            while(b!=NULL)//将b的所有左结点入桟            {                top++;                St[top]=b;                b=b->lchild;            }            p=NULL;//p指向当前结点的前一个访问的结点            flag=1;//设置b的访问标记为已访问过            while(top!=-1&&flag)            {                b=St[top];//取出当前的桟顶元素                if(b->rchild==p)//右子树不存在或已被访问,访问之                {                    printf(" %c ",b->data);//访问*b结点                    top--;                    p=b;//p指向刚被访问的结点                }                else                {                    b=b->rchild;//指向右子树                    flag=0;//设置未被访问的标记                }            }        }while(top!=-1);        printf("\n");    }}void TravLevel(BTNode *b)//层次遍历{    BTNode *Qu[MaxSize];//定义顺序循环队列    int front,rear;//定义队首和队尾指针    front=rear=0;//置队列为空队列    if(b!=NULL)        printf(" %c ",b->data);    rear++;//结点指针进入队列    Qu[rear]=b;    while(rear!=front)//队列不为空    {        front=(front+1)%MaxSize;        b=Qu[front];        if(b->lchild!=NULL)//队头出队列        {            printf(" %c ",b->lchild->data);//输出左孩子，并入队列            rear=(rear+1)%MaxSize;            Qu[rear]=b->lchild;        }        if(b->rchild!=NULL)//输出右孩子，并入队列        {            printf(" %c ",b->rchild->data);            rear=(rear+1)%MaxSize;            Qu[rear]=b->rchild;        }    }    printf("\n");}void InTongji(BTNode *t,int &m,int &n)//中序遍历的方法求叶子结点的个数{    if(t!=NULL)    {        InTongji(t->lchild,m,n);        printf("%c",t->data);        m++;//结点计数        if((t->lchild==NULL)&&(t->rchild==NULL))            n++;//叶子结点计数        InTongji(t->rchild,m,n);    }}int CountLeaf(BTNode *T)//返回二叉树所有叶子结点个数{    int m,n;    if(!T)return 0;    if(!T->lchild&&!T->rchild)return 1;    else    {        m=CountLeaf(T->lchild);        n=CountLeaf(T->rchild);        return m+n;    }}int Count(BTNode *T)//返回二叉树所有结点个数{    int m,n;    if(!T)        return 0;    //if(!T->lchild&&!T->rchild)return 1;    else    {        m=Count(T->lchild);        n=Count(T->rchild);        return m+n+1;    }}BTNode *GetTreeNode(char item,BTNode*lptr,BTNode *rptr)//其数据域为item,左指针域为lptr,右指针域为rptr{    BTNode *T;    T=new BTNode;    T->data=item;    T->lchild=lptr;    T->rchild=rptr;    return T;}BTNode *CopyTree(BTNode *T){    BTNode *newlptr,*newrptr,*newT;    if(!T)return NULL;    if(T->lchild)        newlptr=CopyTree(T->lchild);//复制左子树    else        newlptr=NULL;    if(T->rchild)        newrptr=CopyTree(T->rchild);    else        newrptr=NULL;    newT=GetTreeNode(T->data,newlptr,newrptr);//复制右子树    return newT;}BTNode*DestoryTree(BTNode *&T){    if(T==NULL)return 0;    DestoryTree(T->lchild);    DestoryTree(T->rchild);    delete(T);    T=NULL;    return 0;}void output(){    int i;    for(i=0;i<10;i++)        printf(" ");    for(i=0;i<32;i++)        printf("*");    printf("\n");}void mainpp(){    int i;    output();    for(i=0;i<10;i++)printf(" ");printf("*    ");    printf("1.构建一颗二叉树");    for(i=0;i<10;i++)printf(" ");printf("*");printf("\n");    for(i=0;i<10;i++)printf(" ");printf("*    ");    printf("2.先序输出二叉树");    for(i=0;i<10;i++)printf(" ");printf("*");printf("\n");    for(i=0;i<10;i++)printf(" ");printf("*    ");    printf("3.中序输出二叉树");    for(i=0;i<10;i++)printf(" ");printf("*");printf("\n");    for(i=0;i<10;i++)printf(" ");printf("*    ");    printf("4.后序输出二叉树");    for(i=0;i<10;i++)printf(" ");printf("*");printf("\n");    for(i=0;i<10;i++)printf(" ");printf("*    ");    printf("5.层序输出二叉树");    for(i=0;i<10;i++)printf(" ");printf("*");printf("\n");    for(i=0;i<10;i++)printf(" ");printf("*    ");    printf("6.求二叉树的高度");    for(i=0;i<10;i++)printf(" ");printf("*");printf("\n");    for(i=0;i<10;i++)printf(" ");printf("*    ");    printf("7.输出二叉树叶结点");    for(i=0;i<8;i++)printf(" ");printf("*");printf("\n");    for(i=0;i<10;i++)printf(" ");printf("*    ");    printf("8.以括号形式输出所有结点");    for(i=0;i<2;i++)printf(" ");printf("*");printf("\n");    for(i=0;i<10;i++)printf(" ");printf("*    ");    printf("9.输出二叉树所有结点总数");    for(i=0;i<2;i++)printf(" ");printf("*");printf("\n");    for(i=0;i<10;i++)printf(" ");printf("*    ");    printf("10.删除二叉树");    for(i=0;i<13;i++)printf(" ");printf("*");printf("\n");    for(i=0;i<10;i++)printf(" ");printf("*    ");    printf("0.退            出");    for(i=0;i<8;i++)printf(" ");printf("*");printf("\n");    output();}int main(){    int m=0,n=0,k=1,t;    BTNode*root=NULL;    mainpp();    t=0;    while(k)    {        printf("请选择0--10:  ");        scanf("%d",&m);        getchar();        switch(m)        {        case 0:return 0;        case 1:printf("输入字符，构建二叉树:\n");createbitree(root);break;        case 2:printf("先序输出二叉树各结点:\n");            printf("递归算法:\n");PreOrder(root);printf("\n");            printf("非递归算法:\n");PreOrder1(root);printf("\n");break;        case 3:printf("中序输出二叉树各结点:  ");            printf("递归算法:\n");InOrder(root);printf("\n");            printf("非递归算法:\n");InOrder1(root);printf("\n");break;        case 4:printf("后序输出二叉树各结点:  ");               printf("递归算法:\n");PostOrder(root);printf("\n");            printf("非递归算法:\n");PostOrder1(root);printf("\n");break;        case 5:printf("层序输出二叉树各结点:\n");            TravLevel(root);printf("\n");break;        case 6:t=BiTreeDepth(root);printf("二叉树的高度=%3d\n",t);break;        case 7:printf("输出一颗给定二叉树的所有叶子结点:");            DispLeaf(root);            n=CountLeaf(root);printf("\n叶子结点总数:  n=%3d\n",n);break;        case 8:printf("以嵌套形式输出所有结点:\n");            DispBiTree(root);            printf("\n");            break;        case 9:printf("输出二叉树所有结点总数%3d\n",Count(root));            break;        case 10:printf("删除二叉树结点");            DestoryTree(root);            break;        default:return 0;        }        printf("继续运行吗Y(1)/N(0):  ");        scanf("%d",&k);        if(!k)return 0;    }    return 0;}