在一棵二叉树总,前序遍历结果为:DBACEGF,中序遍历结果为 ABCDEFG,求后序遍历结果。
我们知道:
前序遍历方式为:根节点->左子树->右子树
中序遍历方式为:左子树->根节点->右子树
后序遍历方式为:左子树->右子树->根节点
从这里可以看出,前序遍历的第一个值就是根节点,然后再中序遍历中找到这个值,那么这个值的左边部分即为当前二叉树的左子树部分前序遍历结果,这个值的右边部分即为当前二叉树的右子树部分前序遍历结果。因此,通过这个分析,可以恢复这棵二叉树,得到这样的一段伪码:
节点 getRoot(前序,中序)
c=前序第一个字符
pos=c在中序中的位置
len1=中序pos左半部分长度
len2=中序pos右半部分长度
新建节点r,令r的元素等于c
r的左儿子=getRoot(前序位置1开始的len1长度部分,中序pos位置的左半部分)
r的右儿子=getRoot(前序位置len1开始右半部分,中序pos位置的右半部分)
return r
下面有两种求法:
1.不建立树,直接输出结果
#include<stdio.h> #include<string.h> char ans[8]; char *S1 = "DBACEGF"; char *S2 = "ABCDEFG"; void build(int n, char *s1, char *s2, char *s) { if(n <= 0) return; int p = strchr(s2,s1[0]) - s2; build(p,s1+1,s2,s); build(n-p-1,s1+p+1,s2+p+1,s+p); s[n-1] = s1[0]; } int main() { int n = strlen(S1); build(n,S1,S2,ans); ans[n] = '\0'; printf("%s\n",ans); }
2.建立二叉树
#include <iostream> #include <fstream> #include <string> using namespace std; struct TreeNode { struct TreeNode* left; struct TreeNode* right; char elem; }; TreeNode* BinaryTreeFromOrderings(char* inorder, char* preorder, int length) { if(length == 0) return NULL; TreeNode* node = new TreeNode;//Noice that [new] should be written out. node->elem = *preorder; node->left = node ->right = NULL; int rootIndex = 0; for(;rootIndex < length; rootIndex++)//a variation of the loop { if(inorder[rootIndex] == *preorder) break; } node->left = BinaryTreeFromOrderings(inorder, preorder +1, rootIndex); node->right = BinaryTreeFromOrderings(inorder + rootIndex + 1, preorder + rootIndex + 1, length - (rootIndex + 1)); cout << node->elem << " "; return node; } int main() { char* pr="DBACEGF"; char* in="ABCDEFG"; BinaryTreeFromOrderings(in, pr, 7); printf("\n"); return 0; }