数据结构上机测试4.1:二叉树的遍历与应用1

短命女 2022-05-14 03:35 56阅读 0赞

Time Limit: 1000 ms Memory Limit: 65536 KiB  
Submit Statistic Discuss  
Problem Description  
输入二叉树的先序遍历序列和中序遍历序列，输出该二叉树的后序遍历序列。  
Input  
第一行输入二叉树的先序遍历序列；  
第二行输入二叉树的中序遍历序列。  
Output  
输出该二叉树的后序遍历序列。  
Sample Input  
ABDCEF  
BDAECF  
Sample Output  
DBEFCA  
Hint

Source

#include <iostream>
    #include <string>
    #include <typeinfo>
    using namespace std;
    typedef struct nd
    {
        char data;
        nd *left, *right;
    } node, *pnode;
    const char gen = ',';
    const int LEN = 55;
    //无返回值形式，树使用引用
    void createTree(pnode &root, char str[], int &index)
    {
        char c;
        c = str[index];
        if(c == gen)
            root = nullptr;
        else
        {
            root = new node();
            root->left = root->right = nullptr;
            root->data = c;
            createTree(root->left, str, ++index);
            createTree(root->right, str, ++index);
        }
    }
    //以返回值的形式,树不使用引用
    pnode createtree(char str[], int &index)
    {
        char c;
        c = str[index];
        pnode root = nullptr;
        if(c != gen)
        {
            root = new node();
            root->data = c;
            root->left = createtree(str, ++index);
            root->right = createtree(str, ++index);
        }
        return root;
    }
    //中序遍历
    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;
        }
    }
    //先序中序还原二叉树
    //先序遍历获得树根
    //中序遍历获得左右子树
    pnode xianzhong(string xian, string zhong, int xl, int xr, int zl, int zr)
    {
    // cout << xl << " "
    // << xr << " "
    // << zl << " "
    // << zr << " " << endl;
        pnode root = nullptr;
        if(xl <= xr && zl <= zr)
        {
            char c = xian[xl];
            //i指向根节点
            int i = zl;
            //从中序遍历中找到树根，分开获得左右子树的字符串
            while(i < zr)
            {
                if(zhong[i] == c)
                    break;
                i++;
            }
            int len = i - zl;//左子树的长度
            root = new node();
            root->data = c;
            root->left = xianzhong(xian, zhong, xl+1, xl + len, zl, i-1);
            root->right = xianzhong(xian, zhong, xl + len +1, xr, i+1, zr);
        }
    
    
        return root;
    }
    int main()
    {
        pnode root = nullptr;
        string strx, strz;
        cin >> strx >> strz;
    
        int lenx = strx.length();
        root = xianzhong(strx, strz, 0, lenx-1, 0, lenx-1);
        hou(root);
        cout << endl;
    
        return 0;
    }