数据结构实验之二叉树二：遍历二叉树

阳光穿透心脏的1/2处 2022-07-12 06:51 156阅读 0赞

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

已知二叉树的一个按先序遍历输入的字符序列，如abc,,de,g,,f,,, (其中,表示空结点)。请建立二叉树并按中序和后序的方式遍历该二叉树。  
Input

连续输入多组数据，每组数据输入一个长度小于50个字符的字符串。  
Output

每组输入数据对应输出2行：  
第1行输出中序遍历序列；  
第2行输出后序遍历序列。

Example Input

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

cbegdfa  
cgefdba  
Hint

这题真不难，逻辑简单思路清晰，不过我就是定义LEN那里出了问题，花了一个早上的时间还没解决。现在可要记住了，字符类不能用\#define LEN sizeof(struct node)定义！！！

#include <stdio.h>
    #include <stdlib.h>
    #define LEN sizeof(struct node)//字符类型可拉几把倒吧，不能用这样定义大小
    
    char str[51];
    int i;
    
    typedef struct node
    {
        char data;
        struct node *l,*r;
    }node;
    
    node *create()
    {
        node *root;
        if(str[i]==','){
       //如果str为“，” 那么该子树就是空的
            i++;
            root = NULL;
        }
        else{
            root = (node *)malloc(sizeof(struct node));//先序建立
            root->data = str[i++];
            root->l = create();
            root->r = create();
        }
        return root;
    }
    
    void inOrder(node *root)
    {
        if(root){
       //中序输出
            inOrder(root->l);
            printf("%c",root->data);
            inOrder(root->r);
        }
    }
    
    void postOrder(node *root)
    {
        if(root){
       //后序输出
            postOrder(root->l);
            postOrder(root->r);
            printf("%c",root->data);
        }
    }
    
    int main()
    {
        while(~scanf("%s",str)){
            i = 0;
            node *root = create();
            inOrder(root);
            printf("\n");
            postOrder(root);
            printf("\n");
        }
        return 0;
    }