数据结构实验之二叉树的建立与遍历

题目描述

       已知一个按先序序列输入的字符序列，如abc,,de,g,,f,,,(其中逗号表示空节点)。请建立二叉树并按中序和后序方式遍历二叉树，最后求出叶子节点个数和二叉树深度。

输入

 输入一个长度小于50个字符的字符串。

输出

输出共有4行： 第1行输出中序遍历序列； 第2行输出后序遍历序列； 第3行输出叶子节点个数； 第4行输出二叉树深度。

示例输入

abc,,de,g,,f,,,

示例输出

cbegdfa cgefdba 3 5

提示

#include<stdio.h> #include<string.h> #include<stdlib.h> typedef char Status; typedef char telemtype; typedef struct BiTNode {     Status data;     struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; Status str[55]; int i,count; int CreateBiTree(BiTree &T)//建二叉树； {         if(str[i++]==',') T=NULL;         else         {         T=(BiTNode *)malloc(sizeof(BiTNode));         if(!T)         exit(0);         T->data=str[i-1];         CreateBiTree(T->lchild);         CreateBiTree(T->rchild);        }     return 1; } void inorder(BiTree &T)//中序二叉树 {     if(T)     {         inorder(T->lchild);         printf("%c",T->data);         inorder(T->rchild);     } } void postorder(BiTree &T)//后序二叉树 {     if(T)     {        postorder(T->lchild);        postorder(T->rchild);        printf("%c",T->data);     } } void CountLeaf(BiTree T,int &count)//树中叶子的统计； {     if(T)     {         if((!T->rchild)&&(!T->lchild))             ++count;         CountLeaf(T->rchild,count);         CountLeaf(T->lchild,count);     } } int depth(BiTree T)//树的深度； {     int lth,rth;     if(!T)  return 0;     else     {         lth=depth(T->lchild);         rth=depth(T->rchild);         if(lth>rth)             return lth+1;         else             return rth+1;     } } int main() {     BiTree T;     while(~scanf("%s",str))     {        i=0;        CreateBiTree(T);//生成树；        inorder(T);//中序二叉树        printf("\n");        postorder(T);//后序二叉树       printf("\n");       count=0;       CountLeaf(T,count);//树叶子的统计；       printf("%d\n",count);       int h=depth(T);//树深度；       printf("%d\n",h);     }     return 0; }