二叉树

二叉树是一种特殊的树形数据结构，其中每个节点最多有两个子节点，通常被称为左子节点和右子节点。遍历二叉树是指按照某种顺序访问树中的所有节点，而前序遍历是其中的一种遍历方式。

前序遍历的定义

在前序遍历中，我们首先访问根节点，然后递归地对左子树进行前序遍历，最后递归地对右子树进行前序遍历。这种遍历方式的顺序可以概括为：根节点 -> 左子树 -> 右子树。

递归实现的步骤

1. 访问根节点：首先打印或访问当前节点的值。
2. 遍历左子树：然后对左子节点递归执行前序遍历。
3. 遍历右子树：最后对右子节点递归执行前序遍历。

递归实现的伪代码

function 前序遍历(node)
    if node is not null then
        访问 node 的数据
        前序遍历(node.left)
        前序遍历(node.right)
    end if
end function

递归实现的示例代码（以C++为例）

#include <iostream>
using namespace std;

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

// 前序遍历的递归实现
void preOrderTraversal(TreeNode* root) {
   
    if (root != NULL) {
   
        // 访问根节点
        cout << root->val << " ";
        // 遍历左子树
        preOrderTraversal(root->left);
        // 遍历右子树
        preOrderTraversal(root->right);
    }
}

// 测试代码
int main() {
   
    // 创建一个示例二叉树
    //       1
    //      / \
    //     2   3
    //    / \
    //   4   5
    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);

    return 0;
}

注意事项

• 在递归实现中，确保对每个节点的访问都是唯一的，避免重复访问。
• 递归实现的前序遍历需要维护一个栈来存储待访问的节点，这个栈由递归调用的调用栈隐式实现。
• 递归实现的前序遍历在最坏情况下的时间复杂度为O(n)，其中n是二叉树中节点的数量，因为每个节点都会被访问一次。