#include <stdio.h>

#include <stdlib.h>

typedef char DataType;

typedef struct Node

{

    DataType data;

    struct Node *LChild;

    struct Node *RChild;

}BiTNode, *BiTree;

 

void CreateBiTree(BiTree *bt)//构建二叉树

{

    char ch;

    ch = getchar();

    if(ch=='#') *bt=NULL;

    else 

    {

        *bt=(BiTree)malloc(sizeof(BiTNode)); //生成一个新结点

        (*bt)->data=ch;

        CreateBiTree(&((*bt)->LChild)); //生成左子树

        CreateBiTree(&((*bt)->RChild)); //生成右子树

    }

}

void Order(BiTree root)//先序遍历二叉树

{

    if(root!=NULL)

    {

        printf("%c", root->data);

        Order(root->LChild);

        Order(root->RChild);

    }   

}

int count;

void pOrder(BiTree root)//总结点的数目

{

    if(root==NULL)

        return 0;

    pOrder(root->LChild);

    pOrder(root->RChild);

    count++;

}

void leafOrder(BiTree root)//先序遍历叶子结点的

{

    if(root!=NULL)

    {

        if(root->LChild==NULL&&root->RChild==NULL)

            printf("%C", root->data);

        leafOrder(root->LChild);

        leafOrder(root->RChild);

    }

}

int LeafCount;

void leaf(BiTree root)//求叶子结点的个数

{

    if(root!=NULL)

    {

        leaf(root->LChild);

        leaf(root->RChild);

        if (root ->LChild==NULL && root ->RChild==NULL)

            LeafCount++;

    }

}

void unleafOrder(BiTree root)//先序遍历非叶子结点

{

    if(root!=NULL)

    {

        if(root->LChild!=NULL||root->RChild!=NULL)

            printf("%c", root->data);

    unleafOrder(root->LChild);

    unleafOrder(root->RChild);

    }

}

int unLeafCount;

void unleaf(BiTree root)//求非叶子结点的个数

{

    if(root!=NULL)

    {

        if(root->LChild!=NULL||root->RChild!=NULL)

        unLeafCount++;

    unleaf(root->LChild);

    unleaf(root->RChild);

    }

}

 

int main()

{

    BiTree T;

    int treeleaf;

    LeafCount = 0;

    printf(" 按扩展先序遍历序列建立二叉树，请输入序列:\n");

    CreateBiTree(&T);

    printf("先序遍历为：");

    Order(T);

 

    pOrder(T);

    printf("\n总结点个数为：%d\n", count);

 

    leaf(T);

    printf("\n\n求得的叶子数目为:%d\n",LeafCount);

 

    printf("先序遍历叶子节点为：");

    leafOrder(T);

 

    unleaf(T);

    printf("\n\n求得的非叶子数目为:%d\n", unLeafCount);

 

    printf("先序遍历叶子节点为：");

    unleafOrder(T);

    getch();

}