编程实现以先序遍历序列输入,创建一棵二叉树的整个完整代码
时间: 2024-12-01 13:30:40 浏览: 10
C++求先序序列(二叉树中,给出中序和后序,求先序,代码经过编译后,绝对可运行).rar
在Python中,我们可以使用递归的方式来实现从先序遍历序列构建二叉树。这里有一个简单的例子,假设我们有一个函数`preorder`提供先序遍历的列表:
```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):
if not preorder:
return None
# 先序遍历的第一个元素作为根节点
root_val = preorder[0]
root = TreeNode(root_val)
# 找到根节点的位置,以便分割成左右子序列
index = preorder.index(root_val) + 1
# 分别对左子序列和右子序列进行递归构建
root.left = build_tree(preorder[1:index]) if index > 1 else None
root.right = build_tree(preorder[index:]) if index < len(preorder) else None
return root
```
这个函数接受一个先序遍历的列表,比如`[3,9,20,None,None,15,7]`(其中None表示空节点),然后返回对应的二叉树结构。
阅读全文