美文网首页
根据前序遍历与中序遍历 求出后序遍历(C++)

根据前序遍历与中序遍历 求出后序遍历(C++)

作者: 白夜叉小分队 | 来源:发表于2018-04-27 21:18 被阅读389次

    题意大概是以字符串的形式输入前序遍历和中序遍历,输出后序遍历。
    一个栗子 ↓
    输入:ABDEC DBEAC
    输出:DEBCA

    #include <iostream>
    #include <string.h>
    using namespace std;
    
    void findPostorder(string preorder, int low_1, int high_1, string inorder, int low_2, int high_2, char* postorder, int low_3, int high_3) {   
        if (low_1 == high_1) {
            postorder[high_3] = preorder[low_1];
            return; 
        }
        int i;
        for (i = low_2; i <= high_2; i++) {
            if (preorder[low_1] == inorder[i]) {
                break;
            }
        }
        postorder[high_3] = preorder[low_1]; 
        findPostorder(preorder, low_1 + 1, low_1 + i, inorder, low_2, low_2 + i - 1, postorder, low_3, low_3 + i - 1);
        findPostorder(preorder, low_1 + i + 1, high_1, inorder, low_2 + i + 1, high_2, postorder, low_3 + i, high_3 - 1);
    }
    
    int main() {
        string preorder, inorder;
        cin >> preorder >> inorder;
        int length = preorder.size();
        char postorder[length];
        //对后序遍历所在的字符串数组进行填充
        findPostorder(preorder, 0, length - 1, inorder, 0, length - 1, postorder, 0, length - 1);
        for (int i = 0; i < length; i++) {
            cout << postorder[i];
        }
        return 0;
    }
    

    相关文章

      网友评论

          本文标题:根据前序遍历与中序遍历 求出后序遍历(C++)

          本文链接:https://www.haomeiwen.com/subject/ooiilftx.html