建立二叉树,并实现二叉树的遍历,先序遍历采用递归算法实现,层次遍历用非递归算法来实现。
时间: 2024-03-09 13:46:24 浏览: 16
以下是 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 preorder:
return None
# 前序遍历的第一个节点是根节点
root_val = preorder[0]
root = TreeNode(root_val)
# 在中序遍历中找到根节点的位置
idx = inorder.index(root_val)
# 递归构建左右子树
root.left = buildTree(preorder[1:idx+1], inorder[:idx])
root.right = buildTree(preorder[idx+1:], inorder[idx+1:])
return root
# 先序遍历(递归实现)
def preorderTraversal(root):
if not root:
return []
res = [root.val]
res += preorderTraversal(root.left)
res += preorderTraversal(root.right)
return res
# 层次遍历(非递归实现)
def levelOrder(root):
if not root:
return []
res = []
queue = [root]
while queue:
level = []
for i in range(len(queue)):
node = queue.pop(0)
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(level)
return res
# 测试代码
preorder = [1, 2, 4, 5, 3, 6, 7]
inorder = [4, 2, 5, 1, 6, 3, 7]
root = buildTree(preorder, inorder)
print(preorderTraversal(root))
print(levelOrder(root))
```
以上代码中,`buildTree` 函数通过递归方式构建二叉树,`preorderTraversal` 函数通过递归方式实现先序遍历,`levelOrder` 函数通过队列实现二叉树的层次遍历。