二叉树是一种递归形式的双链表，二叉树的实现主要是利用双重递归的调用来创建左子树和右子树的。二叉树的遍历分为三种方式：一种是先序遍历，即根左右。另一种是中序遍历，即左根右。最后一种是后序遍历，即左右根。本文是以先序的方式创建的二叉树。二叉树的递归形式代码如下：

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

//定义树的结构
typedef struct BiTNode{
    char data;//数据域 
    struct BiTNode *lchild,*rchild;//左结点和右节点 
}BiTNode,*BiTree;

//创建二叉树,利用先序递归的方式(根左右) 
BiTree CreateBiTree(BiTree &T){
    char x;
    scanf("%c",&x);
    if(x=='#'){
        return T=NULL;
    }else{
        T = (BiTNode*)malloc(sizeof(BiTNode));//创建结点
        T->data = x;
        T->lchild = CreateBiTree(T->lchild);//创建左子树
        T->rchild = CreateBiTree(T->rchild);//创建右子树 
        return T;   
    }
}

//遍历二叉树(先序遍历)
void  preTree(BiTree T){//T始终指向的是根结点,然后通过根结点依次链接 
    if(T!=NULL){
        printf("%c\t",T->data);
        preTree(T->lchild);
        preTree(T->rchild);
    }
}

//遍历二叉树(中序遍历)
void  inTree(BiTree T){//T始终指向的是根结点,然后通过根结点依次链接 
    if(T!=NULL){
        inTree(T->lchild);
        printf("%c\t",T->data);
        inTree(T->rchild);
    }
}

//遍历二叉树(后序遍历)
void  finishTree(BiTree T){//T始终指向的是根结点,然后通过根结点依次链接 
    if(T!=NULL){
        finishTree(T->lchild);
        finishTree(T->rchild);
        printf("%c\t",T->data);
    }
}

//二叉树结点总数
int Count(BiTree T){
    if(T==NULL){//空二叉树结点数为0
        return 0;
    }else{//左右子树结点总数加1
        return Count(T->lchild)+Count(T->rchild)+1;
    }
}
//叶子数 
int LeafCount(BiTree T){
    if(T == NULL){
        return 0;
    }else if((T->lchild==NULL) && (T->rchild==NULL)){
        return 1;
    }else{
        return LeafCount(T->lchild)+LeafCount(T->rchild);
    }
}

//统计叶子结点 
int Leaf(BiTree T)
{
    int LeafCount = 0;
    if(T!=NULL)
    {
        Leaf(T->lchild);
        Leaf(T->rchild);
        if(T->lchild==NULL && T->rchild==NULL)
        {
            LeafCount++;   //统计叶子结点数目
        }
    }
    return LeafCount;
} 

int main(int argc, char** argv) {
    BiTree T;
    printf("请输入创建结点的观察值:\n");
    CreateBiTree(T);
    printf("创建成功!\n");
    printf("先序遍历:\n");
    preTree(T);
    printf("\n中序遍历:\n");
    inTree(T);
    printf("\n后序遍历:\n");
    finishTree(T);
    printf("\n二叉树结点总数:\n");
    Count(T);
    printf("二叉树叶子结点总数:\n");
    LeafCount(T);
    Leaf(T);
    return 0;
}