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

╰+哭是因爲堅強的太久メ 2022-07-12 03:20 135阅读 0赞

Problem Description

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

Input

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

Output

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

Example Input

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

Example Output

cbegdfacgefdba35

具体代码如下：

#include<stdio.h> 
    #include<string.h> 
    #include<stdlib.h> 
    typedef struct node { 
        char data ; 
        struct node * lc; 
        struct node * rc; 
    }bitree; 
    int i; 
    int ans; 
    int max; 
    bitree * pre_create(char str[51]) { 
        bitree * t; 
        if(str[++i]!=',') { 
            t=(bitree *)malloc(sizeof(bitree)); 
            t->data=str[i]; 
            t->lc=pre_create(str); 
            t->rc=pre_create(str); } 
        else { 
            t=NULL; 
        } 
        return t; 
    } 
    void inshow(bitree * tree) { 
        bitree * t; 
        t=tree; 
        if(t!=NULL) { 
            inshow(t->lc); 
            printf("%c",t->data); 
            inshow(t->rc); 
        } 
    } 
    void postshow(bitree * tree) { 
        bitree * t; 
        t=tree; 
        if(t!=NULL) { 
            postshow(t->lc); 
            postshow(t->rc); 
            printf("%c",t->data); 
        } 
    } 
    void pre_show(bitree * t) { 
        if(t) { 
            if(t->lc==NULL&&t->rc==NULL) { 
                ans++; 
            } 
            pre_show(t->lc); 
            pre_show(t->rc); 
        } 
    } 
    void preshow(int count,bitree *t) { 
        int k; 
        if(t) { 
            if(count==0) 
                count=1; 
            k=count; 
            if(k>max) 
                max=k; 
            preshow(++count,t->lc); 
            preshow(++k,t->rc); 
        } 
    } 
    int main() { 
        int len; 
        char str[51]; 
        bitree * tree; 
        while(scanf("%s",str)!=EOF) { 
            i=-1; 
            ans=0; 
            max=0; 
            len=strlen(str); 
            tree=pre_create(str); 
            inshow(tree); 
            printf("\n"); 
            postshow(tree); 
            printf("\n"); 
            pre_show(tree); 
            printf("%d\n",ans); 
            preshow(0,tree); 
            printf("%d\n",max); 
        } 
        return 0; 
    }