建立二叉树,并实现二叉树的遍历,先序遍历采用递归算法实现, 层次遍历用非递归算法来实现。
时间: 2024-03-17 07:45:01 浏览: 95
下面是基于Python语言实现的二叉树遍历代码示例:
```python
# 定义二叉树节点类
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# 先序遍历二叉树(递归算法)
def preorderTraversal(root):
if root:
print(root.val)
preorderTraversal(root.left)
preorderTraversal(root.right)
# 层次遍历二叉树(非递归算法)
def levelTraversal(root):
if not root:
return
queue = [root]
while queue:
node = queue.pop(0)
print(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
# 测试代码
if __name__ == '__main__':
# 构建二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
# 先序遍历二叉树
print("先序遍历结果:")
preorderTraversal(root)
# 层次遍历二叉树
print("层次遍历结果:")
levelTraversal(root)
```
输出结果为:
```
先序遍历结果:
1
2
4
5
3
6
7
层次遍历结果:
1
2
3
4
5
6
7
```
阅读全文