python中用先序遍历和中序遍历构建一个二叉树,并且写出其代码
时间: 2024-02-04 16:02:07 浏览: 88
好的,下面是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, inorder):
if not inorder:
return None
root = TreeNode(preorder.pop(0))
idx = inorder.index(root.val)
root.left = buildTree(preorder, inorder[:idx])
root.right = buildTree(preorder, inorder[idx+1:])
return root
# 测试代码
preorder = [1, 2, 4, 5, 3, 6, 7]
inorder = [4, 2, 5, 1, 6, 3, 7]
root = buildTree(preorder, inorder)
```
这里我们先定义了一个二叉树结点类`TreeNode`,包含了结点值`val`、左子结点`left`和右子结点`right`。然后我们定义了一个`buildTree`函数,用于构建二叉树。这个函数接受两个参数,分别是先序遍历和中序遍历的结果。函数首先判断中序遍历结果是否为空,如果为空则返回`None`。接着从先序遍历结果中取出第一个结点值作为根结点,然后在中序遍历结果中找到根结点的位置,将左子树和右子树分别递归构建,最后返回根结点。
最后我们对函数进行了测试,构建了一个二叉树,并存储在变量`root`中。
阅读全文