跳到主要内容

从上往下遍历二元树 ?

参考答案:

从上往下遍历二元树通常指的是深度优先遍历(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的函数,该函数接受一个节点作为参数,并使用递归进行前序遍历。

注意,在遍历过程中,我们首先访问当前节点,然后递归地遍历左子树和右子树。这样,我们就可以确保按照从上到下的顺序遍历整个二元树。