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

大家好，欢迎来到IT知识分享网。

前序遍历（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. 重复步骤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) 

前序遍历的时间复杂度为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 

上述代码中，定义了一个二叉树结点结构体 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; } 

代码中，我们首先定义了一个 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); //递归遍历右子树 } } 

上述代码中，我们定义了一个 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 4 5 3，验证了前序遍历方法的正确性。

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

class TreeNode { 
    int val; TreeNode left; TreeNode right; TreeNode(int x) { 
    val = x; } }