二叉樹的遞歸遍歷，用先序和中序輸出後序，二叉樹遞歸

二叉樹的遞歸遍歷，用先序和中序輸出後序，二叉樹遞歸

Description

 

Little Valentine liked playing with binary trees very much. Her favorite game was constructing randomly looking binary trees with capital letters in the nodes.

This is an example of one of her creations:

 

                                    D
                                   / \
                                  /   \
                                 B     E
                                / \     \
                               /   \     \ 
                              A     C     G
                                         /
                                        /
                                       F

To record her trees for future generations, she wrote down two strings for each tree: a preorder traversal (root, left subtree, right subtree) and an inorder traversal (left subtree, root, right subtree).

For the tree drawn above the preorder traversal is DBACEGF and the inorder traversal is ABCDEFG.

She thought that such a pair of strings would give enough information to reconstruct the tree later (but she never tried it).

 

Now, years later, looking again at the strings, she realized that reconstructing the trees was indeed possible, but only because she never had used the same letter twice in the same tree.

However, doing the reconstruction by hand, soon turned out to be tedious.

So now she asks you to write a program that does the job for her!

 

Input Specification 

The input file will contain one or more test cases. Each test case consists of one line containing two strings preord and inord, representing the preorder traversal and inorder traversal of a binary tree. Both strings consist of unique capital letters. (Thus they are not longer than 26 characters.)

Input is terminated by end of file.

 

Output Specification 

For each test case, recover Valentine's binary tree and print one line containing the tree's postorder traversal (left subtree, right subtree, root).

 

Sample Input 

DBACEGF ABCDEFG
BCAD CBAD

 

Sample Output 

ACBFGED
CDAB



題意：給你一個二叉樹的先序和中序，輸出它的後序。

解題思路：因為先序的第一個就是這個二叉樹的根。通過先序找到根，然後再在中序上找到根，然後從這分開，再找左邊的子樹的根，接下來都是這樣，也就是遞歸了，右邊也是這樣。然後再遞歸的輸出。

（參考了別人的代碼，自己還是有點地方不懂，如果看不懂的話，復制這個鏈接，看看我參考的代碼。）

http://www.cnblogs.com/zsyacm666666/p/4662576.html

（我的注釋，也不一定是對的。╮(╯▽╰)╭，   我是小白，求諒解。   最好是自己把例子帶入代碼，模擬一遍）

 1 #include "iostream"
 2 #include "string.h"
 3 using namespace std;
 4 struct node
 5 {
 6     char dian;   //根（節點）
 7     struct node *lchild;  //左孩子
 8     struct node *rchild;  // 右孩子
 9 };
10 struct node *build(char *pre,char *in,int len)
11 {
12     struct node *p;   //一個node型的指針
13     char *q;          //字符指針
14     p=new (struct node);   //分配一個大小為node的空間給p
15     int k=0;          
16     if(len==0) return NULL;   //判斷到底沒有
17     p->dian=*pre;   //將先序的第一個值給dian
18     //cout<<*pre<<endl;  
19     for(q=in; q<in+len; q++)   //這裡通過首地址循環。
20     {
21         if(*q==*pre) break;   //如果中序的值等於根
22         k++;        //記錄循環了幾次，也是記住位置
23     }
24     p->lchild=build(pre+1,in,k);    //左邊遞歸，
25     p->rchild=build(pre+1+k,q+1,len-k-1); //右邊遞歸
26     return p;
27 }
28 void post(struct node*p)
29 {
30     if(p!=NULL)
31     {
32         post(p->lchild);
33         post(p->rchild);
34         cout<<p->dian;
35     }
36 }
37 int main()
38 {
39     char a[100],b[100];
40     while(cin>>a>>b)
41     {
42         struct node*root;
43         root=build(a,b,strlen(a));
44         post(root);
45         cout<<endl;
46     }
47     return 0;
48 }