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

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

Time Limit: 1000 ms Memory Limit: 65536 KiB

Submit Statistic

Problem Description

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

Input

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

Output

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

Sample Input

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

Sample Output

cbegdfa
cgefdba
3
5

Hint

Source

ma6174

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char a[101];
int l;
struct node//二叉树的定义
{
    char data;
    struct node *lc;
    struct node *rc;
};
struct node *creat()//老套路了，知道先序和中序搞出整棵树
{
    struct node *root;
    char c;
    c = a[l++];
    if(c == ',')
    {
        return NULL;
    }
    else
    {
        root = (struct node *)malloc(sizeof(struct node));
        root->data = c;
        root->lc = creat();
        root->rc = creat();
    }
    return root;
}
void mid(struct node *root)
{

    if(root != 0)
    {
        mid(root->lc);
        printf("%c", root->data);
        mid(root->rc);
    }
}
void after(struct node *root)
{
    if(root != 0)
    {
        after(root->lc);
        after(root->rc);
        printf("%c", root->data);
    }
}
int leav(struct node *root)
{
    if(root == NULL)
    {
        return 0;
    }
    if(root->lc == NULL && root->rc == NULL)
    {
        return 1;
    }
    else
    {
        return leav(root->lc) + leav(root->rc);
    }
}
int deep(struct node *root)//求深度的话，就看左右子树哪个更深就返回哪个的深度，最后加个1就是整棵树的深度了
{
    int d = 0;
    if(root != NULL)
    {
        int d1 = deep(root->lc);
        int d2 = deep(root->rc);
        if(d1 >= d2)
        {
            d = d1 + 1;
        }
        else
        {
            d = d2 + 1;
        }
    }
    else
    {
        return 0;//一定到最后没有左右子树的话要返回0，这样就不会又加1了
    }
    return d;
}
int main()
{
    int k;
    struct node *root;
    while(scanf("%s", a) != EOF)
    {
        l = 0;
        root = (struct node *)malloc(sizeof(struct node));
        root =creat();
        mid(root);
        printf("\n");
        after(root);
        printf("\n");
        k = leav(root);
        printf("%d\n", k);
        printf("%d\n", deep(root));
    }
    return 0;
}