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

数据结构实验之二叉树的建立与遍历
Time Limit: 1000 ms Memory Limit: 65536 KiB
Submit Statistic Discuss
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>
struct tree
{
    char data;
    struct tree*right,*left;
}*link[54];
char s[54];
int ans,flag;
struct tree*front_create()
{
    struct tree*root;
    char c=s[ans++];
    if(c==',')root=NULL;//递归的边界，输入的数的最后肯定是','
    else
    {
        root=(struct tree*)malloc(sizeof(struct tree));
        root->data=c;
        root->left=front_create();
        root->right=front_create();
    }
    return root;
}
int depth(struct tree*root)//求深度
{
    int x,y;
    if(!root)return 0;
    else
    {
        x=depth(root->left);
        y=depth(root->right);
        return x>y?x+1:y+1;
    }
}
void mid(struct tree*root)//中序遍历
{
    if(root)
    {
        mid(root->left);
        printf("%c",root->data);
        mid(root->right);
    }
}
void after(struct tree*root)//后序遍历
{
    if(root)
    {
        after(root->left);
        after(root->right);
        printf("%c",root->data);
    }
}
int searchleaf(struct tree*root)//寻找叶子结点，在层序遍历的基础上加点操作即可
{
    if(root)
    {
        int i=0,j=0;
        link[j++]=root;
        while(i<j)
        {
            if(link[i])
            {
                if(link[i]->left==NULL&&link[i]->right==NULL)
                    flag++;
                else
                {
                    link[j++]=link[i]->left;
                    link[j++]=link[i]->right;
                }
            }
            i++;
        }
    }
    return flag;
}
int main()
{
    scanf("%s",s);
    flag=0,ans=0;
    struct tree*root;
    root=front_create();
    mid(root);
    printf("\n");
    after(root);
    printf("\n");
    printf("%d\n",searchleaf(root));
    printf("%d\n",depth(root));
    return 0;
}

再结合利用先序和中序实现后序遍历的那个题和二叉排序