1. 已知一颗二叉树的先序遍历序列为0137849256,中序遍历序列为7381940526,设计程序实现通过输入先序、中序遍历序列建立二叉树。要求程序能够根据输入的序列构建出相应的二叉树。
时间: 2024-10-28 20:13:02 浏览: 31
数据结构C++二叉树的先序遍历、中序遍历和后序遍历实现
5星 · 资源好评率100%
为了根据给定的先序遍历 (Preorder) 和中序遍历 (Inorder) 序列创建一棵二叉树,我们可以采用递归算法。首先理解这两个遍历序列的特点:
- 先序遍历:根节点 -> 左子树 -> 右子树
- 中序遍历:左子树 -> 根节点 -> 右子树
在这个过程中,中序遍历可以帮助我们确定每个节点的位置,因为从左到右的顺序可以告诉我们当前节点应该插入到其父节点的哪个位置。
以下是Python中实现这个功能的一个示例:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def build_tree(preorder, inorder):
if not preorder or not inorder:
return None
# 在中序遍历中找到根节点
root_val = inorder.index(preorder[0])
root = TreeNode(preorder[0])
# 分别在左右子树构造中寻找剩余元素
root.left = build_tree(preorder[1:root_val+1], inorder[:root_val])
root.right = build_tree(preorder[root_val+1:], inorder[root_val+1:])
return root
# 示例:
preorder = [0, 1, 3, 7, 8, 4, 9, 2, 5, 6]
inorder = [7, 3, 8, 1, 9, 4, 0, 2, 5, 6]
root = build_tree(preorder, inorder)
```
这个函数`build_tree`接受两个列表作为输入,并返回对应的二叉树结构。它首先找到先序遍历的第一个元素,这是根节点,然后在中序遍历中找到它的位置,接着分别递归地处理左右子树。最后得到完整的二叉树结构。
阅读全文