基于标明空子树的先序遍历序列构造一棵采用二叉链表存储的二叉树。
时间: 2024-04-29 08:25:42 浏览: 130
用顺序和二叉链表作存储结构实现二叉排序树
5星 · 资源好评率100%
可以通过递归的方式构造二叉树。具体步骤如下:
1. 读入先序遍历序列中的一个字符,如果是空字符,则返回空指针;否则,创建一个新节点,并将该节点的值设置为该字符。
2. 递归构造左子树,将左子树的根节点设置为刚刚创建的节点的左孩子。
3. 递归构造右子树,将右子树的根节点设置为刚刚创建的节点的右孩子。
4. 返回该节点。
示例代码如下:
```python
class TreeNode:
def __init__(self, val=None, left=None, right=None):
self.val = val
self.left = left
self.right = right
def build_tree(preorder):
"""
根据标明空子树的先序遍历序列构造二叉树
"""
def build_subtree():
nonlocal index
if index >= len(preorder):
return None
val = preorder[index]
index += 1
if val == '#':
return None
root = TreeNode(val)
root.left = build_subtree()
root.right = build_subtree()
return root
index = 0
return build_subtree()
```
例如,对于先序遍历序列为"AB##C##"的二叉树,可以通过以下代码构造:
```python
root = build_tree('AB##C##')
```
阅读全文