本关任务:以二叉链表表示二叉树,用递归的方法实现输出二叉树的中序遍历结果的算法。 编程要求 根据提示,在右侧编辑器补充代码,用递归的方法实现输出二叉树的中序遍历结果的算法。
时间: 2024-11-27 21:17:24 浏览: 5
erchashubianli.rar_用二叉链表 进行 二叉树 遍历
为了使用递归方法实现二叉树的中序遍历,我们需要创建一个节点结构和访问函数。首先,定义一个二叉链表节点(BinaryTreeNode),它包含一个值和左右指针:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
```
然后编写一个用于中序遍历的递归函数 `inorder_traversal`。这个函数会先遍历左子树,然后访问当前节点,最后遍历右子树。如果当前节点不为空,则进行递归调用:
```python
def inorder_traversal(root):
if root is not None: # 当前节点非空,才进行递归
inorder_traversal(root.left) # 遍历左子树
print(root.val, end=" ") # 访问当前节点
inorder_traversal(root.right) # 遍历右子树
```
在这个 `inorder_traversal` 函数里,`end=" "` 参数是为了避免打印每个节点后立即换行,而是将它们连接成一个序列。
现在你可以使用这个函数来遍历任何给定的二叉树实例。例如:
```python
# 创建一个简单的二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
# 调用中序遍历函数
inorder_traversal(root)
```
运行上述代码,你会看到输出类似于 `4 2 5 1 3` 的中序遍历结果。
阅读全文