二叉树的建立和遍历

建立以二叉链作为存储结构的二叉树，实现 1）先序遍历； 2）中序遍历； 3）后序遍历； 4）编程计算二叉树的叶子结点个数。

输入描述:

按照先序遍历序列输入二叉树中数据元素的值，没有的输入0表示。

输出描述:

第一行输出先序遍历序列 第二行输出中序遍历序列 第三行输出后序遍历序列 第四行输出叶子结点的个数。

A B C 0 0 0 D E 0 F 0 0 G 0 0

A B C D E F G 
C B A E F D G 
C B F E G D A 
3

#include <stdio.h>
#include <stdlib.h>
 
typedef struct BiNode{
    char data;
    struct BiNode *lchild;
    struct BiNode *rchild;
}*Bitree;
 
int create(Bitree &L);
void visit(Bitree L);
void Preorder(Bitree L);  //先序遍历
void Inorder(Bitree L);  //中序遍历
void Postorder(Bitree L); //后序遍历
void find(Bitree L,int &sum);  //查找叶子结点
 
int main(){
    Bitree L;
    create(L);
    Preorder(L);
    printf("\n");
    Inorder(L);
    printf("\n");
    Postorder(L);
    printf("\n");
    int sum=0;
    find(L,sum);
    printf("%d",sum);
    return 0;
}
 
int create(Bitree &L){  //先序遍历生成树
    char e;
    scanf("%c",&e);
    getchar();
    if(e=='0') L=NULL;
    else {
        L=(Bitree )malloc(sizeof(Bitree));
        L->data=e;
        create(L->lchild);
        create(L->rchild);
    }
    return 1;
}
 
void visit(Bitree L){  //输出
    printf("%c ",L->data);
}
 
void Preorder(Bitree L)  //先序遍历
{
    if(L!=NULL)
    {
        visit(L);
        Preorder(L->lchild);
        Preorder(L->rchild);
    }
}
 
 
void Inorder(Bitree L){  //中序遍历
    if(L!=NULL)
    {
        Inorder(L->lchild);
        visit(L);
        Inorder(L->rchild);
    }
}
 
void Postorder(Bitree L){  //后序遍历
    if(L!=NULL){
        Postorder(L->lchild);
        Postorder(L->rchild);
        visit(L);
    }
}
 
void find(Bitree L,int &sum)  //查找叶子结点
{
    if(L!=NULL)
    {
        if(L->lchild==NULL&&L->rchild==NULL)
            sum++;
        find(L->lchild,sum);
        find(L->rchild,sum);
    }
}
 
void order(Bitree L)//二叉树层次遍历
{
 
    Bitree queue[7];
    int front=0,rear=0;
    queue[rear]=L;
    rear++;
    while(front!=rear)
    {
        visit(queue[front]);
        if(queue[front]->lchild!=NULL)
        {
            queue[rear]=queue[front]->lchild;
            rear++;
        }
        if(queue[front]->rchild!=NULL)
        {
            queue[rear]=queue[front]->rchild;
            rear++;
        }
        front++;
    }
}

运行结果：