根据先序和中序序列创建一颗二叉树
时间: 2024-12-21 22:24:06 浏览: 32
根据先序遍历和中序遍历创建二叉树通常涉及到递归的过程。假设我们有两串序列,先序遍历(Preorder)表示根节点 -> 左子树 -> 右子树,而中序遍历(Inorder)表示左子树 -> 根节点 -> 右子树。
以下是创建过程:
1. **确定根节点**:先序遍历的第一个元素总是当前节点,因此通过这个元素找到对应的索引。
- 先序遍历的首字符作为根节点。
2. **构建左右子树**:
- 对于先序遍历,剩下的部分从第二个元素开始,利用中序遍历来确定左右子树。
- 中序遍历的根节点之前的部分对应的是左子树的中序遍历序列。
- 同样,右子树的中序遍历序列是从左子树之后到结束的所有元素。
**递归算法示例**(假设两个字符串分别是`preOrder`和`inOrder`):
```python
def buildTree(preOrder, inOrder):
if not preOrder or not inOrder:
return None
root_val = preOrder[0] # 根节点值
root_index = inOrder.index(root_val) # 根节点在中序中的位置
# 创建根节点
root = TreeNode(root_val)
# 递归构建左右子树
root.left = buildTree(preOrder[1:root_index+1], inOrder[:root_index])
root.right = buildTree(preOrder[root_index+1:], inOrder[root_index+1:])
return root
```
在这个函数中,`TreeNode`是一个假设存在的二叉树节点类,它有一个包含`val`, `left`, 和`right`属性的结构。这个过程会一直递归下去,直到遇到空的预序序列或中序序列为止。
阅读全文
相关推荐


















