先序序列二叉树的创建
时间: 2023-12-13 08:33:06 浏览: 38
以下是先序序列二叉树的创建方法:
假设先序序列为preorder,我们可以通过递归的方式来创建二叉树。具体步骤如下:
1. 如果preorder为空,返回None。
2. 取出preorder的第一个元素作为根节点。
3. 递归调用函数,将preorder[1:]作为左子树的先序序列,创建左子树。
4. 递归调用函数,将preorder[len(left)+1:]作为右子树的先序序列,创建右子树。
5. 将左右子树分别作为根节点的左右子树。
下面是Python代码实现:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def buildTree(preorder):
if not preorder:
return None
root = TreeNode(preorder[0])
left = [x for x in preorder[1:] if x < root.val]
right = [x for x in preorder[1:] if x > root.val]
root.left = buildTree(left)
root.right = buildTree(right)
return root
```
其中,TreeNode是二叉树的节点类,buildTree函数接收一个先序序列preorder,返回创建好的二叉树的根节点。