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

题目描述

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

输入

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

输出

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

示例输入

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

示例输出

cbegdfacgefdba35

提示

#include <stdio.h>
#include <string.h>
using namespace std;
struct bitree
{
    char data;
    struct bitree *left, *right;
} root;
void zhong(bitree *p);
int x=0, y=0;
void creatbitree(bitree *&t)
{
    char c;
    scanf("%c",&c);
    if(c=='\n')
        return;
    if(c==',')
        t=NULL;
    else
    {
        t=new bitree;
        t->data=c;
        creatbitree(t->left);
        creatbitree(t->right);
    }
}
void zhong(bitree *p)
{
    if(p)
    {
        zhong(p->left);
        printf("%c",p->data);
        zhong(p->right);
    }
}
void hou(bitree *p)
{
    if (p)
    {

        hou(p->left);
        hou(p->right);
       printf("%c",p->data);
       if(p->left==NULL&&p->right==NULL)
        x++;
    }
}
int depth(bitree *p)
{
    int ld, rd;
    if(p==NULL)
        return 0;
    ld=depth(p->left)+1;
    rd=depth(p->right)+1;
    return ld>rd?ld:rd;
}
int main()
{
    bitree *N;
    creatbitree(N);
    zhong(N);
    printf("\n");
    hou(N);
    printf("\n");
    printf("%d\n%d\n",x,depth(N));
    return 0;
}