根据先序中序还原二叉树

根据先序中序还原二叉树

先序遍历：根 —> 左 —> 右

中序遍历：左 —> 根 —> 右

后序遍历：左 —> 右 —>根

算法思想：

根据先序遍历的特点，第一个遍历的结点就是根结点，我们找到根结点根据中序遍历的特点，我们知道此根结点左边的序列为左子树，根结点右侧的序列为右子树根据原始的先序和中序遍历结果，得到左右子树的先序和中序遍历结果，递归还原二叉树

根据遍历结果构造子树的遍历结果：

后序遍历：[ [ 左子树后序遍历结果 ]，[ 右子树后序遍历结果 ]，根节点]中序遍历：[[ 左子树中序遍历结果 ]，根节点，[ 右子树中序遍历结果 ]]

举例：

preorder = [3,9,20,15,7] inorder = [9,3,15,20,7]

首先我们根据preorder知道结点3为整个树的根结点，然后根据inorder序列知道3左侧的序列[9]为左子树，右侧的序列[15,20,7]为右子树，就像这样

接下来我们构造左右子树的先序和中序遍历序列：

left_preorder = [9] right_preorder = [20,15,7]

left_inorder = [9] right_inorder = [15,20,7]

接下来就是递归的过程了。按照同样的步骤，根据preorder序列的第一个元素得到根结点，根据得到的这个根结点以及inorder得到左右子树，就像这样：

代码如下：

* buildTree(vector& preorder, vector& inorder) { if(inorder.size() == 0){ return nullptr; } TreeNode* cur = new TreeNode(preorder[0]); //找到当前结点在中序遍历中的位置，此索引左边为左子树，右边为右子树 vector::iterator mid = find(inorder.begin(), inorder.end(), preorder[0]); int left_nodes = mid - inorder.begin();//当前结点的左子树有left_nodes个 vector left_inorder(inorder.begin(), mid); vector right_inorder(mid+1, inorder.end()); vector left_preorder(preorder.begin()+1, preorder.begin()+left_nodes+1); vector right_preorder(preorder.begin()+left_nodes+1, preorder.end()); cur->left = buildTree(left_preorder, left_inorder); cur->right = buildTree(right_preorder, right_inorder); return cur; }

注意：我们很容易从整个树的中序遍历结果得到左右子树中序遍历的结果，然而根据整个树的先序遍历结果得到左右子树先序遍历的结果还需要一定的计算

我们从中序遍历结果得到根结点后，获取根结点在当前序列的索引left_nodes，此索引则表明左子树共有left_nodes个结点。

构造左子树的先序遍历序列时，从当前序列的1号元素出发（除开根结点），往后数left_nodes个结点即可。那么此序列剩余部分就是右子树的先序遍历结果

贴一个西电的机试题

#include#include#includeusing namespace std;struct Node{ char data; Node* left; Node* right; Node(char data){ this->data = data; this->left = nullptr; this->right = nullptr; }};vector getCharArray(string str){ vector res; for(char c : str){ res.push_back(c); } return res;}Node* getTree(vector& preOrder, vector& inOrder){ if(preOrder.empty()){ return nullptr; } Node* root = new Node(preOrder[0]);//构造根结点 vector::iterator mid = find(inOrder.begin(), inOrder.end(), preOrder[0]); int left_nodes = mid - inOrder.begin(); vector left_inOrder(inOrder.begin(), mid); vector right_inOrder(mid+1, inOrder.end()); vector left_preOrder(preOrder.begin()+1, preOrder.begin()+1+left_nodes); vector right_preOrder(preOrder.begin()+1+left_nodes, preOrder.end()); root->left = getTree(left_preOrder, left_inOrder); root->right = getTree(right_preOrder, right_inOrder); return root;}void postOrder(Node* root){ if(root == nullptr){ return ; } postOrder(root->left); postOrder(root->right); cout<data;}int main(){ string pre_str; string in_str; while(cin >> pre_str >> in_str){ vector preOrder = getCharArray(pre_str); vector inOrder = getCharArray(in_str); Node* root = getTree(preOrder, inOrder); postOrder(root); cout<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。