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

水深无声 2022-05-14 02:56 169阅读 0赞

Time Limit: 1000 ms Memory Limit: 65536 KiB  
Submit Statistic Discuss  
Problem Description  
已知二叉树的一个按先序遍历输入的字符序列，如abc,,de,g,,f,,, (其中,表示空结点)。请建立二叉树并按中序和后序的方式遍历该二叉树。  
Input  
连续输入多组数据，每组数据输入一个长度小于50个字符的字符串。  
Output  
每组输入数据对应输出2行：  
第1行输出中序遍历序列；  
第2行输出后序遍历序列。

Sample Input  
abc,,de,g,,f,,,  
Sample Output  
cbegdfa  
cgefdba  
Hint

Source  
xam

#include <iostream>
    
    using namespace std;
    typedef struct nd
    {
        char data;
        nd *left, *right;
    }node, *pnode;
    void createTree(pnode &root, char str[], int &index)
    {
        char c;
        c = str[index];
        if(c == ',')
            root = nullptr;
        else
        {
            root = new node();
            root->left = root->right = nullptr;
            root->data = c;
            createTree(root->left, str, ++index);
            createTree(root->right, str, ++index);
        }
    }
    void mid(node *root)
    {
        if(root != nullptr)
        {
            mid(root->left);
            cout << root->data;
            mid(root->right);
        }
    }
    void hou(node *root)
    {
        if(root != nullptr)
        {
            hou(root->left);
            hou(root->right);
            cout << root->data;
        }
    }
    int main()
    {
        char str[55];
        while(cin >> str)
        {
            pnode root = nullptr;
            int index = 0;
            createTree(root, str, index);
            mid(root);
            cout << endl;
            hou(root);
            cout << endl;
        }
        return 0;
    }