实现二叉树各种基本运算的算法

编写一个程序，实现二叉树的各种运算，并在此基础上设计一个主程序完成如下功能；

（1）输出二叉树b；

（2）输出H结点的左、右孩子结点值；

（3）输出二叉树b的深度；

（4）输出二叉树b的宽度；

（5）输出二叉树b的结点个数；

（6）输出二叉树b的叶子结点个数。

注：输入数据为  A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))

示例输出：

（1）输出二叉树：A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))

（2）‘H’结点：左孩子为J 右孩子为K

（3）二叉树b的深度：7

（4）二叉树b的宽度：4

（5）二叉树b的结点个数：14

（6）二叉树b的叶子结点个数：6

#include<stdio.h>
#include<malloc.h>
#define MaxSize 100

typedef char ElemType;
typedef struct node{
    ElemType data;      //数据元素
    struct node *lchild;    //指向左孩子
    struct node *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];
    }
}

BTNode *FindNode(BTNode *b,ElemType x){     //返回data域为x的结点指针
    BTNode *p;
    if(b==NULL)
        return NULL;
    else if(b->data==x)
        return b;
    else{
        p=FindNode(b->lchild,x);
        if(p!=NULL)
            return p;
        else
            return FindNode(b->rchild,x);
    }
}

BTNode *LchildNode(BTNode *p){      //返回*p结点的左孩子结点指针
    return p->lchild;
}

BTNode *RchildNode(BTNode *p){      //返回*p结点的右孩子结点指针
    return p->rchild;
}

int BTNodeDepth(BTNode *b){     //求二叉树b的深度
    int lchilddep,rchilddep;
    if(b==NULL)
        return 0;       //空树的深度为0
    else{
        lchilddep=BTNodeDepth(b->lchild);       //求左子树的深度为lchild
        rchilddep=BTNodeDepth(b->rchild);       //求右子树的深度为rchild
        return (lchilddep>rchilddep)?(lchilddep+1):(rchilddep+1);
    }
}

void DispBTNode(BTNode *b){     //以括号表示法输出二叉树
    if(b!=NULL){
        printf("%c",b->data);
        if(b->lchild!=NULL || b->rchild!=NULL){
            printf("(");
            DispBTNode(b->lchild);
            if(b->rchild!=NULL)
                printf(",");
            DispBTNode(b->rchild);
            printf(")");
        }
    }
}

int BTWidth(BTNode *b){      //求二叉树b的宽度
    struct{
        int lno;        //结点的层次编号
        BTNode *p;      //结点指针
    }Qu[MaxSize];       //定义顺序非循环队列
    int front,rear;     //定义队首和队尾指针
    int lnum,max,i,n;
    front=rear=0;       //置队列为空队
    if(b!=NULL){
        rear++;
        Qu[rear].p=b;       //根结点指针入队
        Qu[rear].lno=1;     //根结点的层次编号为1
        while(rear!=front){     //此循环通过层次遍历求每个结点的层次
            front++;
            b=Qu[front].p;      //队头出列
            lnum=Qu[front].lno;
            if(b->lchild!=NULL){        //左孩子入队
                rear++;
                Qu[rear].p=b->lchild;
                Qu[rear].lno=lnum+1;
            }
            if(b->rchild!=NULL){        //右孩子入队
                rear++;
                Qu[rear].p=b->rchild;
                Qu[rear].lno=lnum+1;
            }
        }
        max=0;lnum=1;i=1;       //lnum从第i层开始
        while(i<=rear){     //通过比较相同层次的结点数求树的宽度
            n=0;
            while(i<=rear && Qu[i].lno==lnum){
                n++;        //n累计lnum层中的结点个数
                i++;
            }
            lnum=Qu[i].lno;     //取一个新的结点层次
            if(n>max)
                max=n;      //将最大层次结点数赋给max
        }
        return max;     //返回max值
    }
    else
        return 0;
}

int Nodes(BTNode *b){       //求二叉树b的结点个数
    int num1,num2;
    if(b==NULL)
        return 0;       //树空的情况
    else if(b->lchild==NULL && b->rchild==NULL) //为叶子结点的情况
        return 1;
    else{   //其他情况
        num1=Nodes(b->lchild);
        num2=Nodes(b->rchild);
        return (num1+num2+1);       //返回左右子树结点数加1
    }
}

int LeafNodes(BTNode *b){       //求二叉树b的叶子结点个数
    int num1,num2;
    if(b==NULL)     //树空的情况
        return 0;
    else if(b->lchild==NULL && b->rchild==NULL) //为叶子结点的情况
        return 1;
    else{       //其他情况
        num1=LeafNodes(b->lchild);
        num2=LeafNodes(b->rchild);
        return num1+num2;       //返回左右子树叶子结点数
    }
}

int main(){
    BTNode *b,*p,*lp,*rp;
    CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
    printf("(1)输出二叉树：");DispBTNode(b);printf("\n");
    printf("(2)'H'结点：");
    p=FindNode(b,'H');
    if(p!=NULL){
        lp=LchildNode(p);
        if(lp!=NULL)
            printf("左孩子为%c",lp->data);
        else
            printf("无左孩子");
        rp=RchildNode(p);
        if(rp!=NULL)
            printf("右孩子为%c",rp->data);
        else
            printf("无右孩子");
    }
    printf("\n");
    printf("(3)二叉树b的深度：%d\n",BTNodeDepth(b));
    printf("(4)二叉树b的宽度：%d\n",BTWidth(b));
    printf("(5)二叉树b的结点个数：%d\n",Nodes(b));
    printf("(6)二叉树b的叶子结点个数：%d\n",LeafNodes(b));
    return 0;
}