根据二叉树的前中序建立二叉树
时间: 2024-09-06 21:02:53 浏览: 16
在计算机科学中,给定二叉树的前序遍历(根节点 -> 左子树 -> 右子树)和中序遍历(左子树 -> 根节点 -> 右子树),可以恢复出原始的二叉树结构。这是因为前序遍历包含了根节点信息,而中序遍历则按顺序展示了左子树和右子树。
重建过程如下:
1. 遍历前序遍历序列,第一个元素就是当前树的根节点。
2. 对于找到的根节点,通过中序遍历找出它在序列中的位置。在中序遍历中,从前往后查找,当遇到的第一个大于当前根节点的值就是根节点左子树的结束位置。
3. 用这个结束位置作为分界点,在中序遍历的剩余部分找到根节点的右子树开始位置。
4. 分别在中序遍历的左右两部分递归地应用上述步骤,构建左子树和右子树。
以下是简单的Python伪代码描述:
```python
def buildTree(preorder, inorder):
if not preorder or not inorder:
return None
root_val = preorder[0]
root = TreeNode(root_val) # 创建根节点
in_order_index = inorder.index(root_val) # 找到根节点在中序遍历中的位置
left_inorder = inorder[:in_order_index] # 左子树的中序遍历
right_inorder = inorder[in_order_index+1:] # 右子树的中序遍历
root.left = buildTree(preorder[1:], left_inorder) # 递归构建左子树
root.right = buildTree(preorder[1+len(left_inorder):], right_inorder)