python实现先根遍历

在Python中，先根遍历（Preorder Traversal）是一种用于访问树或二叉树节点的算法，它的顺序是根节点 -> 左子树 -> 右子树。下面是使用递归方法实现先根遍历的一种常见方式：

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def preorder_traversal(node):
    if node is not None:
        # 输出当前节点
        print(node.value, end=" -> ")
        # 递归遍历左子树
        preorder_traversal(node.left)
        # 递归遍历右子树
        preorder_traversal(node.right)

# 创建一个简单的二叉树示例
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

# 先根遍历
preorder_traversal(root)

运行这段代码，你会看到输出类似于 `1 -> 2 -> 4 -> 5 -> 3 ->` 的结果。

相关问题

用Python实现二叉树的遍历

可以回答这个问题。二叉树的遍历有三种方式：前序遍历、中序遍历和后序遍历。以下是Python实现二叉树前序遍历的代码：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        res = []
        stack = [root]
        while stack:
            node = stack.pop()
            res.append(node.val)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return res

这段代码使用了栈来实现前序遍历，先将根节点入栈，然后弹出栈顶元素，将其值加入结果列表中，再将右子节点和左子节点依次入栈。重复这个过程直到栈为空。

python实现bst中序遍历

BST（二叉搜索树）的中序遍历是将左子树、根节点、右子树按照从小到大的顺序遍历输出。可以使用递归或者迭代的方式实现。

递归实现:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        self.helper(root, res)
        return res
    
    def helper(self, root, res):
        if root:
            self.helper(root.left, res)
            res.append(root.val)
            self.helper(root.right, res)

迭代实现:

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        stack = []
        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            res.append(root.val)
            root = root.right
        return res

其中，使用了一个栈来模拟递归调用的过程。先将左子树全部入栈，然后弹出最底层的左子树，记录值，并将右子树入栈，重复该过程直到栈为空。