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

谁借莪１个温暖的怀抱￠ 2022-05-31 01:53 171阅读 0赞

数据结构实验之二叉树的建立与遍历  
Time Limit: 1000MS Memory Limit: 65536KB  
Submit Statistic  
Problem Description

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

Input

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

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

abc,,de,g,,f,,,  
Example Output

cbegdfa  
cgefdba  
3  
5

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    char s[60];
    int i, num;
    struct node
    {
        char data;
        struct node *l, *r;
    };
    int max(int a, int b)
    {
        if(a > b)
            return a;
        else
            return b;
    }
    struct node *creat()
    {
        i++;
        if(s[i] == ',')
            return NULL;
        else
        {
            struct node *root;
            root = (struct node*) malloc (sizeof(struct node));
            root -> data = s[i];
            root -> l = creat();
            root -> r = creat();
            return root;
        }
    };
    struct node *houxv(struct node *root)
    {
        if(root)
        {
            root -> l = houxv(root -> l);
            root -> r = houxv(root -> r);
            printf("%c", root -> data);
        }
        return root;
    };
    struct node *zhongxv(struct node *root)
    {
        if(root)
        {
            root -> l = zhongxv(root -> l);
            printf("%c", root -> data);
            root -> r = zhongxv(root -> r);
        }
        return root;
    };
    struct node *yezi(struct node *root)
    {
        if(root)
        {
            if(root -> l == NULL && root -> r == NULL)
            {
                num++;
            }
            else
            {
                yezi(root -> l);
                yezi(root -> r);
            }
        }
        return root;
    };
    int deep(struct node *root)
    {
        if(root == NULL)
            return 0;
        else
            return max(deep(root -> l), deep(root -> r)) + 1;
    }
    int main()
    {
        scanf("%s", s);
        struct node *root;
        i = -1;
        num = 0;
        root = creat();
        zhongxv(root);
        printf("\n");
        houxv(root);
        printf("\n");
        yezi(root);
        printf("%d\n", num);
        printf("%d\n", deep(root));
        return 0;
    }