用Python代码采用孩子链存储结构创建二叉树
时间: 2024-05-02 15:22:54 浏览: 101
好的,这里是用Python代码采用孩子链存储结构创建二叉树的示例:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left_child = None
self.right_child = None
def create_tree(data):
if not data: # 数据为空,无法创建节点
return None
root = TreeNode(data[0]) # 创建根节点
stack = [root] # 用栈保存节点
i = 1 # 数据指针
while stack and i < len(data): # 栈不为空且数据还未全部处理完
node = stack.pop(0) # 取出队首元素
left_val, right_val = data[i:i+2] # 取出左右子节点的值
i += 2 # 数据指针后移2位
if left_val is not None: # 左子节点不为空
node.left_child = TreeNode(left_val) # 创建左子节点
stack.append(node.left_child) # 将左子节点入栈
if right_val is not None: # 右子节点不为空
node.right_child = TreeNode(right_val) # 创建右子节点
stack.append(node.right_child) # 将右子节点入栈
return root
```
调用示例:
```python
data = [1, 2, 3, 4, None, 5, 6, None, None, None, None, 7, None, None, None]
root = create_tree(data)
```
这里用一个列表来表示二叉树,每个节点按照层序遍历的顺序存储,如果该节点没有子节点,则用 `None` 表示。采用孩子链存储结构,即每个节点有左右两个指针,指向其左右子节点。通过队列来实现层序遍历,再结合栈来完成创建过程。
阅读全文