首页 > 代码库 > 二叉树--已知先序中序求后序--已知中序后序求先序（基本按照网上某大神思路搬过来的）
二叉树--已知先序中序求后序--已知中序后序求先序（基本按照网上某大神思路搬过来的）
思路来自（转载自） http://www.cnblogs.com/fzhe/archive/2013/01/07/2849040.html
题目描述不说了。
前序遍历: GDAFEMHZ
中序遍历: ADEFGHMZ
求中序遍历。
1 确定根,确定左子树，确定右子树。
2 在左子树中递归。
3 在右子树中递归。
4 打印当前根。
代码如下：
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 char pr[1000],in[1000]; 5 int l; 6 struct TreeNode 7 { 8 struct TreeNode* left; 9 struct TreeNode* right;10 char elem;11 };12 void BinTreeFromOrder(char* inorder,char* preorder,int length)13 {14 if (length==0)15 return ;16 TreeNode* node =new TreeNode;17 node->elem= *preorder;18 int rootIndex=0;19 for (;rootIndex<length;rootIndex++)20 {21 if (inorder[rootIndex]==*preorder)22 break;23 }24 BinTreeFromOrder(inorder,preorder+1,rootIndex);25 BinTreeFromOrder(inorder+rootIndex+1,preorder+rootIndex+1,length-1-rootIndex);26 printf("%c",node->elem);27 }28 int main()29 {30 //freopen("de.txt","r",stdin);31 scanf("%s",pr);32 scanf("%s",in);33 l=strlen(pr);34 BinTreeFromOrder(in,pr,l);35 printf("\n");36 return 0;37 }
中序遍历: ADEFGHMZ
后序遍历: AEFDHZMG
1 确定根,确定左子树，确定右子树。
2 在左子树中递归。
3 在右子树中递归。
4 打印当前根。
代码如下：
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 char af[1000],in[1000]; 5 int l; 6 struct TreeNode 7 { 8 struct TreeNode* left; 9 struct TreeNode* right;10 char elem;11 };12 TreeNode* BinTreeFromOrder(char* inorder,char* aftorder,int length)13 {14 if (length==0)15 return NULL;16 TreeNode* node =new TreeNode;17 node->elem= *(aftorder+length-1);18 printf("%c",node->elem);19 int rootIndex=0;20 for (;rootIndex<length;rootIndex++)21 {22 if (inorder[rootIndex]==*(aftorder+length-1))23 break;24 }25 node->left=BinTreeFromOrder(inorder,aftorder,rootIndex);26 node->right=BinTreeFromOrder(inorder+rootIndex+1,aftorder+rootIndex,length-1-rootIndex);27 }28 int main()29 {30 //freopen("de.txt","r",stdin);31 scanf("%s",in);32 scanf("%s",af);33 l=strlen(in);34 BinTreeFromOrder(in,af,l);35 printf("\n");36 return 0;37 }
PS : 已知前序、后序，求中序结果不唯一！！！
二叉树--已知先序中序求后序--已知中序后序求先序（基本按照网上某大神思路搬过来的）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。