알고리즘 문제 17 재구성 트리

제목
이미 알고 있는 두 갈래 나무의 전차와 중차가 수조를 두루 돌아다니며 이 두 갈래 나무를 구축합니다.이미 알고 있는 전서는: abcdf, 중서는: cbdaf, 이 두 갈래 트리를 a로 구축할 수 있습니다
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　/　　\
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　b　　f
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　/　　\
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　c　　d
분석
이미 알고 있는 전차와 중차순 배열 또는 알고 있는 후차순과 중차순 배열은 사고방식은 모두 전차순 또는 후차순을 통해 나무나 하위 나무의 뿌리 노드를 확정하고 중차순을 통해 뿌리 노드가 있는 위치를 찾아낸다.
중서의 뿌리 노드 왼쪽은 왼쪽 트리의 원소(또는 중서)이고 오른쪽은 오른쪽 트리의 원소이다.좌우 트리 원소의 서열 길이를 확정한 후 순서대로 왼쪽 트리와 오른쪽 트리를 구축합니다.
코드

 1 // ， 
 2 TreeNode* ConstructCore(char* start_porder,char* end_porder,char* start_morder,char* end_morder)
 3 {
 4     TreeNode* node=new TreeNode();
 5     node->value=*start_porder;
 6     node->pLeft=NULL;
 7     node->pRight=NULL;
 8 
 9     if (start_morder==end_morder)
10     {
11         return node;
12     }
13 
14     //find the position of the first value of preorder array in the middle order array. 
15     char* p=start_morder;
16     while(start_morder<=end_morder&&*p!=node->value)
17     {
18         p++;
19     }
20 
21     if (p==end_morder&&*p!=node->value)
22         throw std::exception("Invalid input.");
23 
24     int left_len=p-start_morder;
25 
26     if (left_len>0)
27     {
28         node->pLeft=ConstructCore(start_porder+1,start_porder+left_len,start_morder,p-1);
29     }
30     if ((end_porder-start_porder)>left_len)
31     {
32         node->pRight=ConstructCore(start_porder+left_len+1,end_porder,p+1,end_morder);
33     }
34 
35     return node;
36 
37 }
38 
39 TreeNode* ConstructTree(char* arry_porder,char* arry_morder,int len)
40 {
41     TreeNode* root=new TreeNode();
42     
43     return ConstructCore(arry_porder,arry_porder+len-1,arry_morder,arry_morder+len-1);
44 }

 

 1 // ， 
 2 TreeNode* ConstructCore2(char* start_post,char* end_post,char* start_morder,char* end_morder)
 3 {
 4     TreeNode* node=new TreeNode();
 5     node->value=*end_post;
 6     node->pLeft=NULL;
 7     node->pRight=NULL;
 8 
 9     if (start_morder==end_morder)
10     {
11         return node;
12     }
13 
14     //find the position of the last value of post order array in the middle order array. 
15     char* p=start_morder;
16     while(start_morder<=end_morder&&*p!=node->value)
17     {
18         p++;
19     }
20 
21     if (p==end_morder&&*p!=node->value)
22         throw std::exception("Invalid input.");
23 
24     int left_len=p-start_morder;
25 
26     if (left_len>0)
27     {
28         node->pLeft=ConstructCore(start_post,start_post+left_len-1,start_morder,p-1);
29     }
30     if ((end_post-start_post)>left_len)
31     {
32         node->pRight=ConstructCore(start_post+left_len,end_post-1,p+1,end_morder);
33     }
34 
35     return node;
36 
37 }
38 
39 TreeNode* ConstructTree(char* arry_porder,char* arry_morder,int len)
40 {
41     TreeNode* root=new TreeNode();
42     
43     return ConstructCore2(arry_porder,arry_porder+len-1,arry_morder,arry_morder+len-1);
44 }

　　
이미 알고 있는 전차와 후차가 유일한 두 갈래 나무를 확정할 수 없다는 것은 예를 들어 두 갈래 나무 a와 a의 전차는 abc이고 후차는 cba라는 것을 증명할 수 있다.이로부터 알 수 있듯이 만약에 두 갈래 나무 중 하나의 자목 구조가 이런 비만 구조라면 자엽 노드가 왼쪽인지 오른쪽인지 확정할 수 없다
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　/　　　　　　　　\
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　b　　　　　　　　b
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　/　　　　　　　　　　\
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　c　　　　　　　　　　c