Creation, Input, Output Of A Binary Tree

2010/12/04

#include <stdio.h>/*实现先序建立、中序遍历*/
#include <malloc.h>
#include <stdlib.h>

typedef struct BiTNode{
    char data;
    BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

int InitBiTree(BiTree T){
    T=NULL;
    return 1;//初始化成功
}
BiTree CreateBiTree()//先序建立一个二叉树
{
    char x; //x为根节点
    BiTree t;
    scanf("%c",&x);/*输入要创建的根结点值*/
    if (x==' ') /* 判断当前子树是否创建完成*/
        return NULL;
    else
    {
        t=(BiTree)malloc(sizeof(BiTNode));
        t->data=x;
        t->lchild=CreateBiTree();
        t->rchild=CreateBiTree();
    }
    return t;
}
int CountLeaf(BiTree T)//返回二叉树的叶子节点数目
{
    if(!T)
        return 0;
    else
    {
        if(!T->lchild&&!T->rchild)
            return 1;
        return (CountLeaf(T->lchild)+CountLeaf(T->rchild));
    }
}

void InOrderTraverse(BiTree ptr)//这是中序遍历的算法。
{
    if(ptr)
    {
        InOrderTraverse(ptr->lchild);
        printf("%c ",ptr->data);
        InOrderTraverse(ptr->rchild);
    }
}

int main()
{
    printf("构建一个二叉树:/n");
    BiTree T =CreateBiTree();
    printf("中序遍历二叉树:/n");
    InOrderTraverse(T);
    printf("/n");
    printf("二叉树的叶子结点个数为%d/n",CountLeaf(T));
    return 0;
}

这样的一个二叉树,输入的顺序应该是:AB[][]CD[][]E[][]。