根据二叉树的前序和中序求后序

在面试的过程中，发现有几家公司都喜欢考这样的一道题，就是在一棵二叉树中，已知这棵二叉树的前序和中序遍历结果，要求写出后序遍历结果。

例如：在一棵二叉树总，前序遍历结果为：ABDGCEFH，中序遍历结果为：DGBAECHF，求后序遍历结果。

我们知道：

前序遍历方式为：根节点->左子树->右子树

中序遍历方式为：左子树->根节点->右子树

后序遍历方式为：左子树->右子树->根节点

从这里可以看出，前序遍历的第一个值就是根节点，然后再中序遍历中找到这个值，那么这个值的左边部分即为当前二叉树的左子树部分前序遍历结果，这个值的右边部分即为当前二叉树的右子树部分前序遍历结果。因此，通过这个分析，可以恢复这棵二叉树，得到这样的一段伪码：

节点 getRoot(前序，中序)

c=前序第一个字符

pos=c在中序中的位置

len1=中序pos左半部分长度

len2=中序pos右半部分长度

新建节点r，令r的元素等于c

r的左儿子=getRoot(前序位置1开始的len1长度部分，中序pos位置的左半部分)

r的右儿子=getRoot(前序位置len1开始右半部分，中序pos位置的右半部分)

return r

如图1示：

图1

输入前序ABDGCEFH，中序DGBAECHF，可以得出

A为该二叉树的根节点

1: BDG为该二叉树左子树的前序

2: DGB为该二叉树左子树的中序

根据1和2可以构建一棵左子树

3: CEFH为该二叉树右子树的前序

4: ECHF为该二叉树右子树的中序

根据3和4可以构建一个右子树

执行至该步骤的时候就得到了该二叉树的云结构，如图2所示，A为根节点，BDG在它的左子树上，CEFG在它的右子树上。

如此递归即可以构建一棵完整的二叉树

图2

下面是c语言的实现方法（该代码的变量p1,p2,i1,i2,tmp请参考图1）：

[cpp] view plaincopy

/*   * main.cpp   *   *  Created on: 2011-4-11   *      Author: boyce   *      Email:  [e-mail]   */   #include <stdio.h>   #include <string.h>   struct BTreeNode {       char e;       BTreeNode *left;       BTreeNode *right;   };   typedef BTreeNode* BTree;   BTreeNode *createBTreeNode(char e) {       BTreeNode *nd = new BTreeNode;       nd->e = e;       nd->left = NULL;       nd->right = NULL;       return nd;   }   int findChar(const char *str, int s1, int s2, char c) {       if (!str || s2 < s1 || s1 < 0 || s2 >= strlen(str))           return -1;       for (int i = s1; i <= s2; i++) {           if (str[i] == c)               return i;       }       return -1;   }   BTreeNode *getRoot(char *pre, int p1, int p2, char *in, int i1, int i2) {       char rootCh = pre[p1];       if (!pre || p2 < p1 || p1 < 0 || p2 >= strlen(pre) || !in || i2 < i1 || i1               < 0 || i2 >= strlen(in)) {           return NULL;       }       int tmp = findChar(in, i1, i2, rootCh);       if (tmp < 0) {           return NULL;       }       BTreeNode *nd = createBTreeNode(rootCh);       nd->left = getRoot(pre, p1 + 1, p1 + tmp - i1, in, i1, tmp - 1);       nd->right = getRoot(pre, p1 + tmp - i1 + 1, p2, in, tmp + 1, i2);       return nd;   }   BTree createBTree(char *pre, char *in) {       if (!pre || !in)           return NULL;       return getRoot(pre, 0, strlen(pre) - 1, in, 0, strlen(in) - 1);   }   void printPostOrder(BTree t) {       if (!t)           return;       printPostOrder(t->left);       printPostOrder(t->right);       printf("%c", t->e);   }   void printBTreeNode(BTreeNode *nd, int depth) {       for (int i = 0; i < depth - 1; i++)           printf("  ");       if (depth > 0)           printf("--");       if (!nd) {           printf("*/n");           return;       }       printf("%c/n", nd->e);       printBTreeNode(nd->left, depth + 1);       printBTreeNode(nd->right, depth + 1);   }   void printBTree(BTree t) {       printBTreeNode(t, 0);   }   int countBTree(BTree t) {       if (!t)           return 0;       return countBTree(t->left) + countBTree(t->right) + 1;   }   int main() {       char pre[] = "ABDGCEFH";       char in[] = "DGBAECHF";       BTree t = createBTree(pre, in);       printf("Preorder: %s/n", pre);       printf("Inorder: %s/n", in);       if (countBTree(t) != strlen(pre)) {           printf("No such a binary tree!/n");           return 0;       }       printf("Postorder: ");       printPostOrder(t);       printf("/n");       printf("The BTree is (* means no such node):/n");       printBTree(t);       return 0;   }

分享到：