二叉树的创建，遍历以及叶子结点数

首先在写二叉树时遇到一个问题：scanf和输入缓冲区以及getchar和输入缓冲区之间关系

scanf是读入一个字符，而你在输入时实际上输入的是:某个字符+Enter,Enter 产生的也会停留在输入缓冲区中,下次调用 scanf %c 时就会直接读到它而不是等待你再次输入!

对于这个问题找到了两种解决方式，我自己也尝试了

（1）scanf(" %c", &ch); //(前边添加一个空格)消除上一个'/n'，因为遇到空格，TAB或回车作间即认为该数据结束。

（2）不加空格情况下，可以在后面加上getchar()一句，getchar是从输入缓冲区读取一个字符，所以读取是scanf输入留下的换行符‘/n‘

本次建立二叉树采用递归创建，

叶子结点数：当一个结点的左孩子和右孩子都为空时。他是叶子结点。使用递归如果能找到就返回1，如果节点为NULL返回0，否则返回count(t->lchild)+ count(t->rchild)

程序：

#include <stdio.h>
#include <stdlib.h>
//定义结二叉树的构体
typedef struct BTree
{
    char data;
    struct BTree *lChild;
    struct BTree *rChild;
}BinTree;

//二叉树的创建
BinTree* CreateTree(BinTree *T)
{
    char temp;
   scanf(" %c", &temp); //注意这里前面为什么加一个空格，因为scanf输入形式是实际上输入的是:某个字符+Enter,Enter 产生的也会停留在输入
缓冲区中,下次调用 scanf %c 时就会直接读到它而不是等待你再次输入! 所以加入空格是为了消除上次输入留下的'/n'
        //getchar(); //这句也是可以消除上面的问题,当上面不加空格时，加上这句也可以,因为getchar是从输入缓冲区读取一个字符，所以读取是scanf输入留下的换行符‘/n’
    if(temp == '@'){
                T=NULL;
        }else{
                 T = (BinTree *)malloc(sizeof(BinTree));
                 T->data = temp;
                 printf("输入%c的左孩子:",temp);
                 T->lChild = CreateTree(T->lChild);//递归创建左子数
                 printf("输入%c的右孩子:",temp);
                 T->rChild = CreateTree(T->rChild);
             }
    return T;
}

//先序遍历二叉树
void PreOrderTraverse(BinTree *T)
{
    if(T)
    {
        printf("%c", T->data);
        PreOrderTraverse(T->lChild);
        PreOrderTraverse(T->rChild);
    }
}
//中序遍历二叉树
void InOrderTraverse(BinTree *T)
{
    if(T)
    {
        InOrderTraverse(T->lChild);
        printf("%c", T->data);
        InOrderTraverse(T->rChild);
    }
}
//后序遍历二叉树
void PostOrderTraverse(BinTree *T)
{
    if(T)
    {
        PostOrderTraverse(T->lChild);
        PostOrderTraverse(T->rChild );
        printf("%c",T->data );
   }
}

//叶子结点数

int Count(BinTree * T){
    if(T == NULL){
        return 0;
    }
    else if ((T->lChild==NULL) && (T->rChild==NULL)){
        return 1;
    }
    else{
        return Count(T->lChild)+Count(T->rChild);
    }
}
int main()
{
    BinTree *Tree;
    printf("输入root:");
    Tree = CreateTree(Tree);
    printf("=========分隔符============ ");
    printf("二叉树的先序遍历： ");
    PreOrderTraverse(Tree);
    printf(" ");
    printf("二叉树的中序遍历： ");
    InOrderTraverse(Tree);
    printf(" ");
    printf("二叉树的后序遍历： ");
    PostOrderTraverse(Tree);
    printf(" ");
    printf(" ========================= ");
    return 0;
}
结果：

android@android-Latitude-E4300:~/work/c/erchashu$ ./jiedian

输入root:a
输入a的左孩子:b
输入b的左孩子:c
输入c的左孩子:@
输入c的右孩子:@
输入b的右孩子:d
输入d的左孩子:@
输入d的右孩子:@
输入a的右孩子:e
输入e的左孩子:@
输入e的右孩子:@
=========分隔符============

二叉树的先序遍历：
abcde
二叉树的中序遍历：
cbdae
二叉树的后序遍历：
cdbea

=========================
叶子节点的个数： 3

82,3 Bot