C/C++ 每日一练：二叉树的先序遍历

#include <stdio.h> // 引入标准输入输出库，用于printf函数  
#include <stdlib.h> // 引入标准库，用于malloc函数  
  
// 定义二叉树节点结构体  
struct TreeNode {  
    int val; // 节点的值  
    struct TreeNode *left; // 指向左子节点的指针  
    struct TreeNode *right; // 指向右子节点的指针  
};  
  
// 创建新节点的函数  
// 参数：val - 新节点的值  
// 返回值：指向新创建的节点的指针  
struct TreeNode* createNode(int val) {  
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode)); // 分配内存给新节点  
    node->val = val; // 设置节点的值  
    node->left = NULL; // 初始化左子节点指针为空  
    node->right = NULL; // 初始化右子节点指针为空  
    return node; // 返回新节点的指针  
}  
  
// 先序遍历递归函数  
// 参数：root - 要遍历的二叉树的根节点  
void preorderTraversal(struct TreeNode* root) {  
    if (root == NULL) return; // 如果当前节点为空，则直接返回，不继续遍历  
  
    // 访问根节点  
    printf("%d ", root->val); // 打印当前节点的值  
  
    // 递归遍历左子树  
    preorderTraversal(root->left); // 递归调用先序遍历函数，遍历左子树  
  
    // 递归遍历右子树  
    preorderTraversal(root->right); // 递归调用先序遍历函数，遍历右子树  
}  
  
int main() 
{  
    // 构建示例二叉树  
    // 创建根节点  
    struct TreeNode* root = createNode(1);  
    // 创建左子节点，并连接到根节点  
    root->left = createNode(2);  
    // 创建右子节点，并连接到根节点  
    root->right = createNode(3);  
    // 创建左子节点的左子节点，并连接到左子节点  
    root->left->left = createNode(4);  
    // 创建左子节点的右子节点，并连接到左子节点  
    root->left->right = createNode(5);  
      
    // 打印先序遍历的提示信息  
    printf("递归先序遍历结果：");  
    // 调用先序遍历函数，遍历整棵树  
    preorderTraversal(root);  
  
    // 注意：此代码示例中未包含释放已分配内存的代码，实际使用时应注意内存管理  
    return 0; // 程序正常结束  
}

C++实现（递归实现）

#include <iostream> // 引入输入输出流库，用于cout和endl  
#include <stack> // 引入栈容器库，用于实现非递归遍历  
  
using namespace std; // 使用标准命名空间，避免每次调用标准库时都要加std::前缀  
  
// 定义二叉树节点结构体  
struct TreeNode {  
    int val; // 节点的值  
    TreeNode *left; // 指向左子节点的指针  
    TreeNode *right; // 指向右子节点的指针  
  
    // 构造函数，用于创建新节点并初始化其值和子节点指针  
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
};  
  
// 非递归先序遍历函数  
// 参数：root - 要遍历的二叉树的根节点  
void preorderTraversal(TreeNode* root) {  
    if (root == nullptr) return; // 如果根节点为空，则直接返回  
  
    stack<TreeNode*> s; // 创建一个栈，用于存储待访问的节点指针  
    s.push(root); // 将根节点指针入栈  
  
    // 当栈不为空时，继续循环  
    while (!s.empty()) {  
        // 从栈顶获取节点指针，并访问其值（即先序访问）  
        TreeNode* node = s.top(); // 获取栈顶节点指针  
        s.pop(); // 将栈顶节点指针出栈  
        cout << node->val << " "; // 输出节点的值  
  
        // 注意：这里先将右子节点入栈，再将左子节点入栈  
        // 这样做是为了保证在出栈时左子节点先于右子节点被访问  
        // 因为栈是后进先出（LIFO）的数据结构  
        if (node->right) s.push(node->right); // 如果右子节点存在，则入栈  
        if (node->left) s.push(node->left); // 如果左子节点存在，则入栈  
    }  
}  
  
int main() 
{  
    // 构建示例二叉树  
    // 创建根节点并初始化  
    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);  
  
    // 输出非递归先序遍历的提示信息  
    cout << "非递归先序遍历结果：";  
    // 调用非递归先序遍历函数，遍历整棵树  
    preorderTraversal(root);  
  
    // 注意：此代码示例中未包含释放已分配内存的代码，实际使用时应注意内存管理  
    // 在实际应用中，应在遍历完成后释放所有动态分配的内存，以避免内存泄漏  
    return 0; // 程序正常结束  
}