建立二叉树,并实现二叉树的遍历,先序遍历采用递归算法实现,层次遍历用非递归算法来实现。
时间: 2024-03-09 19:47:56 浏览: 11
好的,我来为您解答。首先,我们需要先了解二叉树的定义和遍历方式。
二叉树是一种树形结构,每个节点最多有两个子节点,分别称为左子节点和右子节点。二叉树遍历包括先序遍历、中序遍历、后序遍历和层次遍历。
先序遍历:先访问根节点,然后递归遍历左子树,最后递归遍历右子树。
中序遍历:先递归遍历左子树,然后访问根节点,最后递归遍历右子树。
后序遍历:先递归遍历左子树,然后递归遍历右子树,最后访问根节点。
层次遍历:从根节点开始,按照从上到下、从左到右的顺序依次访问每个节点。
接下来,我们来实现二叉树的建立和遍历。
```python
# 定义节点类
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 先序遍历(递归实现)
def preorderTraversal(root):
if not root:
return []
res = [root.val]
res += preorderTraversal(root.left)
res += preorderTraversal(root.right)
return res
# 层次遍历(非递归实现)
def levelOrderTraversal(root):
if not root:
return []
res = []
queue = [root]
while queue:
node = queue.pop(0)
res.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return res
# 测试代码
# 创建二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
# 先序遍历
print(preorderTraversal(root)) # [1, 2, 4, 5, 3]
# 层次遍历
print(levelOrderTraversal(root)) # [1, 2, 3, 4, 5]
```
以上就是二叉树的建立和遍历的实现代码。