采用二叉链表作为存储结构，完成二叉树的建立，前序、中序和后序遍历的操作，求所有叶子及结点总数的操作

#include  

#include  

#include  

using namespace std;  

typedef int Elemtype;  

typedef struct BiTnode  

{  

        Elemtype data;//数据域  

        struct BiTnode* Lchild,*Rchild; //左右子树域；  

}BiTnode,*BiTree;  

int create(BiTree *T)  

{  

        Elemtype ch;  

        Elemtype temp;  

        scanf("%d",&ch);  

        temp=getchar();  

        if(ch==-1)  

        {  

                *T=NULL;  

        }  

        else  

        {  

                *T=(BiTree)malloc(sizeof(BiTnode) );  

                if(!(*T))  

                {  

                    exit(-1);  

                }  

                else  

                {  

                        (*T)->data=ch;  

                        printf("请输入%d的左节点的值",ch);  

                        create(&(*T)->Lchild);  

                        printf("请输入%d的右节点的值",ch);  

                        create(&(*T)->Rchild);  

                }  

        }  

        return 1;  

}  

void Traverse(BiTree T)//前序遍历二叉树  

{  

        if(NULL==T)  

        {  

                return;  

        }  

        else  

        {  

            printf("%d ",T->data);  

            Traverse(T->Lchild);  

            Traverse(T->Rchild);  

        }  

}  

//中序遍历二叉树  

void midTraverse(BiTree T)  

{  

        if(T==NULL){return;}  

        midTraverse(T->Lchild);  

        printf("%d ",T->data);  

        midTraverse(T->Rchild);  

}  

//后序遍历二叉树  

void lasTraverse(BiTree T)  

{  

        if(T==NULL){return;}  

        lasTraverse(T->Lchild);  

        lasTraverse(T->Rchild);  

        printf("%d ",T->data);  

}  

//求二叉树的深度  

int TreeDeep(BiTree T)  

{  

        int deep=0;  

        if(T)  

        {  

                int leftdeep=TreeDeep(T->Lchild);  

                int rightdeep=TreeDeep(T->Rchild);  

                deep=leftdeep>=rightdeep?leftdeep+1:rightdeep+1;  

        }  

        return deep;  

}  

//求二叉树叶子节点个数  

int Leafcount(BiTree T,int &num)  

{  

        if(T)  

        {  

                if(T->Lchild==NULL&&T->Rchild==NULL)  

                {  

                        num++;  

                }  

                Leafcount(T->Lchild,num);  

                Leafcount(T->Rchild,num);  

        }  

        return num;  

}  

int main()  

{  

     BiTree T;  

     BiTree *p=(BiTree*)malloc(sizeof(BiTree));  

     int deepth=0,num=0;  

     printf("请输入第一个节点的值，-1代表没有叶节点:\n");  

     create(&T);  

     printf("先序遍历二叉树：\n");  

     Traverse(T);  

     printf("\n");  

     printf("中序遍历二叉树:\n");  

     midTraverse(T);  

     printf("\n");  

     printf("后序遍历二叉树：\n");  

     lasTraverse(T);  

     printf("\n");  

     deepth=TreeDeep(T);  

     printf("树的深度:%d\n",deepth);  

     printf("\n");  

     Leafcount(T,num);  

     printf("二叉树的叶子节点个数为:%d\n",num);  

     printf("\n");  

     return 0;  

扩展资料：

二叉链表是树的二叉链表实现方式。

树的二叉链表实现方式：（孩子兄弟表示法）

以二叉链表作为树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。

结构描述：

typedef　struct CSNode{

ElemType data；

struct CSNode *firstchild ， *netsibling；

} CSNode，* CSTree；

由于二叉树的存储结构比较简单，处理起来也比较方便，所以有时需要把复杂的树，转换为简单的二叉树后再作处理。