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

题目描述

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

输入

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

输出

输出共有4行：

第1行输出中序遍历序列；

第2行输出后序遍历序列；

第3行输出叶子节点个数；

第4行输出二叉树深度。

示例输入

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

示例输出

cbegdfacgefdba35

#include
    
     #include
     
      int ans = 0;struct node{    char ch;    struct node *l;    struct node *r;};node *creat(node *p){    char c;    scanf("%c", &c);    if(c == ',')        p = NULL;    else    {        p = (node *)malloc(sizeof(node));        p->ch = c;        p->l = creat(p->l);        p->r = creat(p->r);    }    return p;}void mid(node *p){    if(p != NULL)    {        mid(p->l);        printf("%c", p->ch);        mid(p->r);    }}void last(node *p){    if(p != NULL)    {        last(p->l);        last(p->r);        printf("%c", p->ch);    }}void sta(node *p){    if(p != NULL)    {        if(p->l == NULL && p->r == NULL)            ans++;        sta(p->l);        sta(p->r);    }}int depth(node *p){    int ldep, rdep;    if(!p)        return 0;    else    {        ldep = depth(p->l);        rdep = depth(p->r);    }    if(ldep > rdep)        return ldep+1;    else        return rdep+1;}int main(){    node *p;    p = creat(p);    mid(p);    printf("\n");    last(p);    printf("\n");    sta(p);    printf("%d\n", ans);    printf("%d\n", depth(p));    return 0;}