Tree Recovery(二叉树递归遍历+求后序遍历模板)
題意:已知先序和中序,將后序求出來
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:?
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
The input 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
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 CBADSample Output
ACBFGED CDAB提供三種解法:
前序遍歷:根左右
中序遍歷:左根右
后序遍歷:左右根
例如上圖:
前序遍歷:ABEHFCGI
中序遍歷:HEBFACIG
1 思路:
前序遍歷第一個字母A,必定是這樹的根節點。
在中序遍歷中找到A的位置,把中序遍歷分成兩個子樹:HEBF和CIG,
取前序遍歷中的第二個點B,在分成的兩個子樹中找到B的位置,再次分成兩個子樹。HE和F,以此類推,分到不能再分了。
回溯到A點,對右子樹CIG進行同樣的操作。
2
思路:
前序遍歷第一個字母A,必定是這樹的根節點。
在中序遍歷中找到A的位置,把中序遍歷分成兩個子樹:HEBF和CIG,
根據A的位置,在前序中找到分界點(分界點+1=右節點)j=l1+(i-l2); 確定左子樹和右子樹在先序遍歷的分界點j,即右子樹的父節點
后序遍歷:左右根,故用棧存入根右左節點
3
利用遞歸,從前序一個個元素開始,m=1; 在中序中找到in[i] == pre[m],
?然后將中序分為兩部分,in[1.....i-1] ?和in[i+1.....n],然后分別遍歷這兩
?部分,直到這兩部分元素為0(s>t) 或1個(s==t);
1.左子樹 ,左子樹范圍必定在begin到i-1之間,下一個根的位置在root+1
2.右子樹,右子樹范圍必定在i+1到end之間,根的位置就是(i-begin)是左子樹
的大小,相當于root位置往后移左子樹的個數再加一
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; const int M=1e3+10; int a[M],b[M]; int n; void dfs(int x,int y,int root) {int i;if(x>y) return ;for(i=x;i<=y;i++)if(a[root]==b[i])break;dfs(x,i-1,root+1);dfs(i+1,y,root+(i-x)/**左子樹大小*/+1);/**右子樹,右子樹范圍必定在i+1到end之間,根的位置就是(i-begin)是左子樹的大小,相當于root位置往后移左子樹的個數再加一*/printf("%d%c",a[root],root==1?'\n':' '); } int main() {while(~scanf("%d",&n)){for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=n;i++)scanf("%d",&b[i]);dfs(1,n,1);}return 0; }?
創作挑戰賽新人創作獎勵來咯,堅持創作打卡瓜分現金大獎總結
以上是生活随笔為你收集整理的Tree Recovery(二叉树递归遍历+求后序遍历模板)的全部內容,希望文章能夠幫你解決所遇到的問題。