采用了递归的思想来解决问题。
先序遍历的第一个结点为该二叉树的根节点。
找到中序遍历中该根节点所在位置，则根节点左侧为该二叉树的左子树的中序遍历（右侧为二叉树的右子树的中序遍历），我们同时也得到了左子树的结点个数。
那么先序遍历去掉第一个结点，数出左子树结点个数个结点，便得到该二叉树左子树的先序遍历（剩下的为二叉树的右子树的先序遍历）。
程序的实现过程中，在Node中定义了一个建立二叉树的方法，三个参数分别为先序遍历字符串，中序遍历字符串，字符串长度。
过程是，创建当前节点p，赋值为先序遍历字符串首字符，判断左非空建立左子树，判断右非空建立右子树，返回该结点。
而后在BinaryTree中对root调用该方法，三个参数相同，返回给root。
#include<iostream> #include<string> using std::cout; using std::endl; using std::string; class Node { public: int data; Node *lchild, *rchild; Node(int _data) { data = _data; lchild = NULL; rchild = NULL; } ~Node() { if (lchild != NULL) { delete lchild; } if (rchild != NULL) { delete rchild; } } void postorder() { if (lchild != NULL) { lchild->postorder(); } if (rchild != NULL) { rchild->postorder(); } cout << data << " "; } // 请在下面实现建立二叉树的方法 build Node* build(const string &pre_str, const string &in_str, int len) { Node *p = new Node(pre_str[0] - '0'); int pos = in_str.find(pre_str[0]); if (pos > 0) { p -> lchild = build(pre_str.substr(1, pos), in_str.substr(0, pos), pos); } if (len - pos - 1 > 0) { p -> rchild = build(pre_str.substr(pos + 1), in_str.substr(pos + 1), len - pos - 1); } return p; } }; class BinaryTree { private: Node *root; public: BinaryTree() { root = NULL; } ~BinaryTree() { delete root; } // 请在下面实现构造函数 BinaryTree(const string &pre_str, const string &in_str, int len) { root = root -> build(pre_str, in_str, len); } void postorder() { root->postorder(); } }; int main() { string pre_str = "136945827"; string in_str = "963548127"; BinaryTree binarytree(pre_str, in_str, in_str.length()); binarytree.postorder(); cout << endl; return 0; }
