前序遍历和后续遍历.doc

首先明确：一颗二叉树的前序遍历=根节点+左子树前序遍历 +右子树前序遍历
一颗二叉树的中序遍历=左子树中序遍历+根节点+右子树中序遍历
那么从前序遍历中取第一个点，就是根节点，知道了根节点，就可以找到中序遍历中跟节点的位置，那么就可以在中序遍历中找到左子树和右子树。

首先，我们看看前序、中序、后序遍历的特性： 
前序遍历： 
    1.访问根节点 
    2.前序遍历左子树 
    3.前序遍历右子树 
中序遍历： 
    1.中序遍历左子树 
    2.访问根节点 
    3.中序遍历右子树 
后序遍历： 
    1.后序遍历左子树 
    2.后序遍历右子树 
    3.访问根节点 

好了，先说说用前序遍历和中序遍历求后序遍历 
假设前序遍历为 adbgcefh, 中序遍历为 dgbaechf 
前序遍历是先访问根节点，然后再访问子树的，而中序遍历则先访问左子树再访问根节点 
那么把前序的 a 取出来，然后查找 a 在中序遍历中的位置就得到 dgb a echf 
那么我们就知道 dgb 是左子树 echf 是右子树，因为数量要吻合 
所以前序中相应的 dbg 是左子树 cefh 是右子树 
然后就变成了一个递归的过程，具体代码如下： 
C++代码  
1. #include <iostream>  
2. #include <string>  
3. using namespace std;  
4.   
5. int find(const string &str, char c)  
6. {  
7.     for (int i = 0; i < str.size(); ++ i)  
8.         if (c == str[i])  
9.             return i;  
10.     return -1;  
11. }  
12.   
13. bool PreMid(const string &pre, const string &mid)  
14. {  
15.     if (pre.size() == 0)  
16.         return false;  
17.     if (pre.size() == 1)  
18.     {  
19.         cout << pre;  
20.         return true;  
21.     }  
22.      
23.     //根节点是第一个元素  
24.     int k = find(mid, pre[0]);  
25.       
26.     string pretmp = pre.substr(1, k);  
27.     string midtmp = mid.substr(0, k);  
28.     PreMid(pretmp, midtmp);  
29.       
30.     pretmp = pre.substr(k + 1, pre.size() - k - 1);  
31.     midtmp = mid.substr(k + 1, mid.size() - k - 1);  
32.     PreMid(pretmp, midtmp);  
33.       
34.     //变成后序遍历要最后输出节点的值  
35.     cout << pre[0];  
36. }  
37.   
38. int main()  
39. {  
40.     string pre, mid;  
41.     while (cin >> pre >> mid)  
42.     {  
43.         PreMid(pre, mid);  
44.         cout << endl;  
45.     }  
46. }  

而已知后序遍历和中序遍历求前序遍历的过程差不多，但由于后序遍历是最后才访问根节点的 
所以要从后开始搜索，例如上面的例子，后序遍历为 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. }  

在二叉树中后序遍历序列为dabec，中序为debac，那它的前序遍历序列是什么?请大家给出详细的解释?
这样理解:
先序遍历是:根\左\右 中序遍历是:左\根\右 后序遍历是:左\右\根
先序,中序,后序的区别就是遍历根的先后,然后知道它们是递归的就ok了.

你看你给的序列,给出了后序遍历,那么我就马上能知道root节点是c了,那么前面的dabe就是c的左子树了,递归的看,dabe也是后序遍历得到的,所以e就是左子树的根节点...接下来就简单了,根据给出的中序遍历...就可以很快的构建出整个二叉树的结构了!