二叉树重构
一、二叉树重构
二叉树重构指的是通过前序和中序，或者中序和后序重新构造出二叉树。
二、中序和前序构造二叉树
给出两个序列：
前序：CBADEFGH
中序：ABEDFCHG
怎么推出后序呢？
首先我们知道前序的遍历顺序是 根左右
中序的遍历顺序是 左根右
因此前序的第一个就是整根数的根节点
然后去中序里面匹配，左边的就是根节点的左子树，右边的就是根节点的右子树
第一次：根为C
左子树：ABEDF
右子树：HG
第二次：根为B
左子树：A
右子树：EDF
第三次：根为A
左子树：无
右子树：无
第四次根为D
左子树：E
右子树：F
第五次根为E
左子树：无
右子树：无
第六次根为F
左子树：无
右子树：无
第七次根为G
左子树：H
右子树：无
第八次根为H
左子树：无
右子树：无
树图为：
后序遍历也很好看出来：AEFDBHGC
那如何进行代码实现呢？
分析：已知了前序，那么每一次左子树的根节点就是上一个+1，右子树的根节点就是中序遍历找到的根节点+1，不断反复就可以重构树了，这里我直接打印出来后序了：
1 #include "bits/stdc++.h" 2 using namespace std; 3 char m[110],p[110];//m是中序，p是前序 4 void printAft(int pmiddle,int ppre,int len) 5 { 6 if(len == 0)//到叶子节点了就返回 7 return; 8 int i = 0; 9 while(m[pmiddle + i] != p[ppre])//根据根节点可以从中序中找到这个根节点的左右子树 10 i++; 11 //后序打印顺序是 左右根 12 printAft(pmiddle,ppre + 1,i);//第一个代表左子树中序的起始位置，第二个参数代表下一个左子树中下一个根节点的下标，第三个代表左子树的长度 13 printAft(pmiddle + i + 1,ppre + i + 1,len - i - 1);//第一个代表右子树中序的起始位置，第二个参数代表前序中下一个根节点的位置，第三个代表右子树的长度，为0是返回打印根节点 14 cout << p[ppre]; 15 } 16 int main() 17 { 18 cin >> m; 19 cin >> p; 20 printAft(0,0,strlen(p)); 21 return 0; 22 }
实现构树再打印：
1 #include "bits/stdc++.h" 2 using namespace std; 3 char m[110],p[110];//m是中序，p是前序 4 struct node{ 5 char date; 6 node *left; 7 node *right; 8 }; 9 node *find_Tree(int pmiddle,int ppre,int len) 10 { 11 if(len == 0)//到叶子节点了就返回 12 return NULL; 13 int i = 0; 14 node *T = new node(); 15 T->date = p[ppre]; 16 while(m[pmiddle + i] != p[ppre])//根据根节点可以从中序中找到这个根节点的左右子树 17 i++; 18 T->left = find_Tree(pmiddle,ppre + 1,i); 19 T->right = find_Tree(pmiddle + i + 1,ppre + i + 1,len - i - 1); 20 return T; 21 } 22 void printAft(node *root) 23 { 24 if(root == NULL) 25 return; 26 printAft(root->left); 27 printAft(root->right); 28 cout << root->date; 29 } 30 int main() 31 { 32 cin >> m; 33 cin >> p; 34 node *root; 35 root = find_Tree(0,0,strlen(p)); 36 printAft(root); 37 return 0; 38 }
三、中序和后序构造二叉树（很容易弄混）
唯一步骤与前序和中序构造二叉树的不同是，后序是从最后开始依次往前找根的
后序：AEFDBHGC
中序：ABEDFCHG
实操：
第一次根为C
查找中序发现
左子树：ABEDF
右子树：HG
第二次根为B
左子树：A
右子树：EDF
第三次根为A
左子树：无
右子树：无
第四次根为D
左子树：E
右子树：F
第五次根为E（注意这个根对应的是中序中找的根的前一位在后序中的位置，不然很容易弄混）
左子树：无
右子树：无
第六次根为F
左子树：无
右子树：无
第七次根为G
左子树：H
右子树：无
第八次根为H
左子树：无
右子树：无
树图为：
那怎么实现代码呢？
1 #include "bits/stdc++.h" 2 using namespace std; 3 char a[110],m[110]; 4 void printPre(int p1,int p2,int root) 5 { 6 if(p1 > p2)//p2是结束位置，p1是开始位置，root是根位置 7 return; 8 int i = p1; 9 while(i < p2 && a[root] != m[i]) 10 i++; 11 cout << a[root]; 12 printPre(p1,i - 1,root - p2 + i - 1);//左子树，p2 - i是右子树的长度,再减1是减去根节点的位置，也就是说左子树的最后一个节点是根节点，右子树的最后一个节点是根节点，因为后序遍历的顺序是左右根 13 printPre(i + 1,p2,root - 1);//右子树 14 } 15 int main() 16 { 17 cin >> m; 18 cin >> a; 19 printPre(0,strlen(a) - 1,strlen(a) - 1); 20 return 0; 21 }
四、总结
二叉树重构的后序+中序容易弄混，所以多推了几遍。