二叉树有中序前序求后序

已知二叉树的前序/后序遍历和中序遍历，求后序/前序遍历

博客分类：

•

算法与数据结构

CC++C#

首先，我们看看前序、中序、后序遍历的特性：前序遍历：

1.访问根节点

2.前序遍历左子树

3.前序遍历右子树

中序遍历：

1.中序遍历左子树

2.访问根节点

3.中序遍历右子树

后序遍历：

1.后序遍历左子树

2.后序遍历右子树

3.访问根节点

好了，先说说用前序遍历和中序遍历求后序遍历

假设前序遍历为 adbgcefh, 中序遍历为 dgbaechf

前序遍历是先访问根节点，然后再访问子树的，而中序遍历则先访问左子树再访问根节点

那么把前序的 a 取出来，然后查找 a 在中序遍历中的位置就得到 dgb a echf

那么我们就知道 dgb 是左子树 echf 是右子树，因为数量要吻合

所以前序中相应的 dbg 是左子树 cefh 是右子树

然后就变成了一个递归的过程，具体代码如下：

C++代码

1. #include

2. #include 3. using namespace std; 4. int find(const string &str, char c) 5. { 6. for (int i = 0; i < str.size(); ++ i) 7. if (c == str[i]) 8. return i; 9. return -1; 10. } 11. bool PreMid(const string &pre, const string &mid) 12. { 13. if (pre.size() == 0) 14. return false;

15. if (pre.size() == 1) 16. { 17. cout << pre; 18. return true; 19. } 20. 21. //根节点是第一个元素 22. int k = find(mid, pre[0]); 23. 24. string pretmp = pre.substr(1, k); 25. string midtmp = mid.substr(0, k); 26. PreMid(pretmp, midtmp); 27.

28. pretmp = pre.substr(k + 1, pre.size() - k - 1); 29. midtmp = mid.substr(k + 1, mid.size() - k - 1); 30. PreMid(pretmp, midtmp); 31. 32. //变成后序遍历要最后输出节点的值 33. cout << pre[0]; 34. } 35. int main() 36. { 37. string pre, mid; 38. while (cin >> pre >> mid) 39. { 40. PreMid(pre, mid);

41. cout << endl; 42. } 43. } 而已知后序遍历和中序遍历求前序遍历的过程差不多，但由于后序遍历是最后才访问根节点的

所以要从后开始搜索，例如上面的例子，后序遍历为 gbdehfca，中序遍历为 dgbaechf

后序遍历中的最后一个元素是根节点，a，然后查找中序中a的位置

把中序遍历分成 dgb a echf，而因为节点个数要对应

后序遍历分为 gbd ehfc a，gbd为左子树，ehfc为右子树，这样又可以递归计算了

其他一些附带的代码上面已经有，这里就不重复贴了，具体代码如下：

C++代码

1. bool BackMid(const string &back, const string &mid) 2. {

3. if (back.size() == 0) 4. return false; 5. 6. if (back.size() == 1) 7. { 8. cout << back; 9. return true; 10. } 11. 12. //根节点是最后一个元素 13. int k = find(mid, back[back.size() - 1]); 14. 15. //变成前序遍历要先输出节点的值

16. cout << back[back.size() - 1]; 17. 18. string backTmp = back.substr(0, k); 19. string midTmp = mid.substr(0, k); 20. BackMid(backTmp, midTmp); 21. 22. backTmp = back.substr(k, back.size() - k - 1); 23. midTmp = mid.substr(k + 1, mid.size() - k - 1); 24. BackMid(backTmp, midTmp); 25. }