数据结构与算法之前序遍历

前序遍历（Preorder Traversal）是二叉树遍历的一种方式。在前序遍历中，先遍历根节点，然后遍历左子树，最后遍历右子树。

具体实现方法如下：

1. 首先访问根节点。
2. 如果左子树非空，则递归遍历左子树。
3. 如果右子树非空，则递归遍历右子树。

在代码实现中，可以用递归来实现前序遍历：

def preorder_traversal(root):
    if not root:
        return
    
    print(root.val)     # 访问根节点
    preorder_traversal(root.left)   # 遍历左子树
    preorder_traversal(root.right)  # 遍历右子树
1
2
3
4
5
6
7

在非递归实现中，可以通过栈来实现前序遍历。具体过程如下：

1. 将根节点入栈。
2. 取出栈顶元素，访问该节点。
3. 如果该节点右子树非空，则将右子树入栈。
4. 如果该节点左子树非空，则将左子树入栈。
5. 重复步骤2-4，直到栈为空。

代码实现如下：

def preorder_traversal(root):
    stack = [root]
    while stack:
        node = stack.pop()
        if node:
            print(node.val)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
1
2
3
4
5
6
7
8
9
10

前序遍历的时间复杂度为O(n)，其中n为二叉树中节点的个数。

一、C 实现 前序遍历 及代码详解

前序遍历是二叉树遍历的一种方法，其遍历顺序为先访问根节点，然后再依次访问其左子树和右子树。

以下是 C 语言实现二叉树前序遍历的代码详解：

#include <stdio.h>
#include <stdlib.h>

// 定义二叉树结点
struct TreeNode {
    int val;              // 结点值
    struct TreeNode* left;   // 左子树指针
    struct TreeNode* right;  // 右子树指针
};

// 前序遍历函数
void preorderTraversal(struct TreeNode* root) {
    if (!root) {
        return;   // 如果根节点为空，直接返回
    }
    printf("%d ", root->val);   // 输出根节点值
    preorderTraversal(root->left);   // 递归遍历左子树
    preorderTraversal(root->right);  // 递归遍历右子树
}

// 测试代码
int main() {
    // 创建一个二叉树
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = 1;
    root->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->left->val = 2;
    root->left->left = NULL;
    root->left->right = NULL;
    root->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->val = 3;
    root->right->left = NULL;
    root->right->right = NULL;

    // 前序遍历
    printf("前序遍历结果：");
    preorderTraversal(root);
    printf("\n");

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

运行结果：

前序遍历结果：1 2 3
1

上述代码中，定义了一个二叉树结点结构体 TreeNode，包含了结点值 val 和左右子树指针。实现了 preorderTraversal 函数，该函数接受一个二叉树结点指针作为参数，用于进行前序遍历，并依次输出根节点值、左子树结点值、右子树结点值，遍历过程通过递归进行。同时，实现了一个简单的测试代码，创建了一个二叉树并进行了前序遍历输出。

二、C++ 实现 前序遍历 及代码详解

前序遍历是二叉树遍历的一种方式，主要特点是先访问根节点，然后再分别递归遍历左子树和右子树。以下是使用 C++ 实现前序遍历的代码及详解：

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

// 前序遍历函数
vector<int> preorderTraversal(TreeNode* root) {
    vector<int> res;
    if (!root) return res;  // 如果根节点为空，直接返回空vector
    stack<TreeNode*> st;    // 创建一个栈
    st.push(root);          // 将根节点压入栈中
    while (!st.empty()) {
        TreeNode* node = st.top();
        st.pop();           // 弹出栈顶节点
        res.push_back(node->val);   // 记录节点值
        if (node->right) st.push(node->right);  // 右子树节点入栈
        if (node->left) st.push(node->left);    // 左子树节点入栈，先访问左子树
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

代码中，我们首先定义了一个 TreeNode 结构体，表示二叉树节点。然后定义了 preorderTraversal 函数，该函数接收一个二叉树的根节点指针作为参数，并返回一个vector，存储前序遍历的结果。如果根节点为空，直接返回空vector。

接着，我们创建一个栈 st，将根节点压入栈中。然后进入循环，每次从栈中取出栈顶节点，并记录该节点的值（即遍历到了该节点）。接着，我们先把右子树节点入栈，再把左子树节点入栈。因为栈是后进先出的，我们需要先访问左子树，所以先将左子树入栈。

最后，循环结束后，vector中存储的就是前序遍历的结果。

三、Java 实现 前序遍历 及代码详解

前序遍历是二叉树遍历的一种方式，其遍历顺序为：根节点 -> 左子树 -> 右子树。下面是 Java 实现前序遍历的示例代码及详解。

/**
 * 前序遍历二叉树
 * @param root 二叉树根节点
 */
public void preorderTraversal(TreeNode root) {
    if (root != null) {
        System.out.print(root.val + " "); //输出当前节点的值
        preorderTraversal(root.left); //递归遍历左子树
        preorderTraversal(root.right); //递归遍历右子树
    }
}
1
2
3
4
5
6
7
8
9
10
11

上述代码中，我们定义了一个 preorderTraversal 方法，其中 root 参数为二叉树的根节点。在方法的内部，我们首先判断根节点是否为空，如果不为空，则先输出当前节点的值，然后递归遍历左子树和右子树。递归遍历左子树和右子树时，我们也先判断当前节点是否为空，如果不为空，则继续递归遍历其左右子树。

下面是一个测试代码，用于验证上述前序遍历方法的正确性。

public static void main(String[] args) {
    //构建一颗二叉树
    TreeNode root = new TreeNode(1);
    root.left = new TreeNode(2);
    root.right = new TreeNode(3);
    root.left.left = new TreeNode(4);
    root.left.right = new TreeNode(5);

    //前序遍历二叉树
    preorderTraversal(root);
}
1
2
3
4
5
6
7
8
9
10
11

输出结果为：1 2 4 5 3，验证了前序遍历方法的正确性。

需要注意的是，上述代码中的 TreeNode 类需要自行实现，其定义类似于下面这样：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
1
2
3
4
5
6