前序遍历二叉树代码实现

前序遍历是一种常见的二叉树遍历方法，它的顺序是先访问根节点，然后递归地遍历左子树，最后遍历右子树。以下是使用递归方式在Python中实现前序遍历的一个简单示例：

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

def preorder_traversal(node):
    if node is not None:
        # 访问当前节点
        print(node.val)
        # 递归遍历左子树
        preorder_traversal(node.left)
        # 递归遍历右子树
        preorder_traversal(node.right)

# 创建一个简单的二叉树实例
root = Node(1,
            Node(2, Node(4), Node(5)),
            Node(3, Node(6), Node(7)))

# 调用前序遍历函数
preorder_traversal(root)

在这个例子中，`preorder_traversal`函数会按照“根-左-右”的顺序打印出每个节点的值。

相关问题

前序遍历二叉树代码实现c++

前序遍历是一种常见的二叉树遍历方法，它按照“根节点-左子树-右子树”的顺序访问每个节点。以下是C++中使用递归实现前序遍历二叉树的代码：

#include <iostream>

// 定义二叉树结点结构
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 前序遍历函数
void preorderTraversal(TreeNode* root) {
    if (root != NULL) { // 如果当前节点不为空
        std::cout << root->val << " "; // 访问根节点
        preorderTraversal(root->left); // 递归遍历左子树
        preorderTraversal(root->right); // 递归遍历右子树
    }
}

int main() {
    // 创建一个简单的二叉树示例
    TreeNode* tree = new TreeNode(1);
    tree->left = new TreeNode(2);
    tree->right = new TreeNode(3);
    tree->left->left = new TreeNode(4);
    tree->left->right = new TreeNode(5);

    std::cout << "Preorder traversal of the binary tree is: ";
    preorderTraversal(tree);
    return 0;
}

在这个例子中，`preorderTraversal` 函数首先检查根节点是否为空，如果不空则先打印值，然后递归地遍历左子树和右子树。

采用前序序列构建二叉树并且前序遍历二叉树，中序遍历二叉树，后序遍历二叉树和层次遍历二叉树的代码

在Python中，我们可以使用递归或栈来构建二叉树并进行各种遍历。这里是一个使用前序（pre-order）、中序（in-order）和后序（post-order）遍历构建二叉树的例子：

首先，我们需要创建一个二叉树节点的结构：

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

接下来，我们可以通过前序遍历构建二叉树：

def build_tree(preorder):
    if not preorder:
        return None
    root_val = preorder[0]
    root = TreeNode(root_val)
    index = inorder.index(root_val)  # 假设inorder已知
    root.left = build_tree(preorder[1:index])
    root.right = build_tree(preorder[index+1:])
    return root

# 假设inorder列表已知
inorder = ...  # 中序遍历的结果
tree = build_tree(preorder)

中序遍历二叉树，如果我们已经有了前序遍历和后序遍历，可以通过两者的组合找到每个节点的位置，如下所示：

def in_order_traversal(root):
    if root is not None:
        in_order_traversal(root.left)
        print(root.val, end=" ")
        in_order_traversal(root.right)

in_order_traversal(tree)

后序遍历也可以类似处理：

def post_order_traversal(root):
    if root is not None:
        post_order_traversal(root.left)
        post_order_traversal(root.right)
        print(root.val, end=" ")

post_order_traversal(tree)

至于层次遍历（广度优先搜索），通常使用队列：

from collections import deque

def level_order_traversal(root):
    if root is None:
        return []
    queue = deque([root])
    result = []
    while queue:
        level_size = len(queue)
        current_level = [queue.popleft().val for _ in range(level_size)]
        result.append(current_level)
        if root.left:
            queue.append(root.left)
        if root.right:
            queue.append(root.right)
    return result

level_orders = level_order_traversal(tree)

注意：在这个例子中，我们需要预先知道中序遍历的结果，因为它是构造二叉树的关键。如果你只有前序和后序遍历，你需要另外一种方法来解决，比如利用线索二叉树。