从上往下遍历二元树 ?
参考答案:
从上往下遍历二元树通常指的是深度优先遍历(Depth-First Search, DFS)中的前序遍历(Pre-order Traversal)。在这种遍历方式中,我们首先访问当前节点,然后遍历左子树,最后遍历右子树。
以下是一个用Python实现的简单示例,用于从上往下(前序)遍历二元树:
class TreeNode:
def __init__(self, value=0, left=None, right=None):
self.value = value
self.left = left
self.right = right
def preorder_traversal(node):
if node is None:
return
# 访问当前节点
print(node.value, end=" ")
# 遍历左子树
preorder_traversal(node.left)
# 遍历右子树
preorder_traversal(node.right)
# 示例
# 1
# / \
# 2 3
# / \
# 4 5
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print("前序遍历结果:")
preorder_traversal(root)
输出:
前序遍历结果:
1 2 4 5 3
在上面的代码中,我们首先定义了一个TreeNode
类来表示二元树的节点。然后,我们定义了一个名为preorder_traversal
的函数,该函数接受一个节点作为参数,并使用递归进行前序遍历。
注意,在遍历过程中,我们首先访问当前节点,然后递归地遍历左子树和右子树。这样,我们就可以确保按照从上到下的顺序遍历整个二元树。