已知前序和中序求后序

假设前序遍历为 adbgcefh, 中序遍历为 dgbaechf
前序遍历是先访问根节点，然后再访问子树的，而中序遍历则先访问左子树再访问根节点
那么把前序的 a 取出来，然后查找 a 在中序遍历中的位置就得到 dgb a echf
那么我们就知道 dgb 是左子树 echf 是右子树，因为数量要吻合
所以前序中相应的 dbg 是左子树 cefh 是右子树 ；

下图为求出的二叉树的图形：

代码如下：

#include <iostream> #include <string> using namespace std; int find(const string &str, char c) { for (int i = 0; i < str.size(); ++ i) if (c == str[i]) return i; return -1; } bool PreMid(const string &pre, const string &mid) { if (pre.size() == 0) return false; if (pre.size() == 1) { cout << pre; return true; } //根节点是第一个元素 int k = find(mid, pre[0]); string pretmp = pre.substr(1, k); string midtmp = mid.substr(0, k); PreMid(pretmp, midtmp); pretmp = pre.substr(k + 1, pre.size() - k - 1); midtmp = mid.substr(k + 1, mid.size() - k - 1); PreMid(pretmp, midtmp); //变成后序遍历要最后输出节点的值 cout << pre[0]; } int main() { string pre, mid; while (cin >> pre >> mid) { PreMid(pre, mid); cout << endl; } }