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

二叉树 binary tree

定义

二叉树是一种树状数据结构，非线性数据结构，代表“祖先”与“后代”之间的派生关系，体现了“一分为二”的分治逻辑。与链表类似，二叉树的基本单元是节点，二叉树的每个节点包含三个主要部分：

节点值：存储该节点的数据。
左子节点（left-child node）：指向该节点左侧的子树或为空。
右子节点（right-child node）：指向该节点右侧的子树或为空。

二叉树节点结构体如下所示：

/* 二叉树节点结构体 */
struct TreeNode {
    int val;          // 节点值
    TreeNode *left;   // 左子节点指针
    TreeNode *right;  // 右子节点指针
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

当给定一个二叉树的节点时，将该节点的左子节点及其以下节点形成的树称为该节点的 左子树（left subtree），同理可得 右子树（right subtree）。

举个例子，下面是一棵简单的二叉树：

在这棵二叉树中：

节点 1 是根节点，它有两个子节点 2 和 3。
节点 2 是节点 1 的左子节点，它有两个子节点 4 和 5。
节点 3 是节点 1 的右子节点，且没有子节点。
节点 4 和节点 5 没有子节点，称为叶节点。

在二叉树中，除叶节点外，其他所有节点都包含子节点和非空子树。如上图所示，如果将“节点 2”视为父节点，则其左子节点和右子节点分别是“节点 4”和“节点 5”，左子树是“节点 4 及其以下节点形成的树”，右子树是“节点 5 及其以下节点形成的树”。

常见术语

二叉树的常用术语如图所示：

根节点 root node ：位于二叉树顶层的节点，没有父节点。
叶节点 leaf node ：没有子节点的节点，其两个指针均指向 None 。
边 edge ：连接两个节点的线段，即节点引用（指针）。
节点所在的 层 level ：从顶至底递增，根节点所在层为 1 。
节点的 度 degree ：节点的子节点的数量。在二叉树中，度的取值范围是 0、1、2 。
二叉树的 高度 height ：从根节点到最远叶节点所经过的边的数量。
节点的 深度 depth ：从根节点到该节点所经过的边的数量。
节点的 高度 height ：从距离该节点最远的叶节点到该节点所经过的边的数量。

二叉树的先序遍历

二叉树的遍历方式主要有以下几种：

先序遍历（Preorder Traversal）：根节点 -> 左子树 -> 右子树。
中序遍历（Inorder Traversal）：左子树 -> 根节点 -> 右子树。
后序遍历（Postorder Traversal）：左子树 -> 右子树 -> 根节点。
层次遍历（Level Order Traversal）：按照树的层级逐层访问节点。

先序遍历是一种访问二叉树节点的顺序，按如下规则遍历每个节点：

首先访问根节点。

递归地先序遍历根节点的左子树。

然后递归地先序遍历根节点的右子树。

举个例子，下面是一棵简单的二叉树：

遍历顺序为：1 -> 2 -> 4 -> 5 -> 3

访问根节点 1。

递归遍历左子树，访问 2，再递归到左子树访问 4，4没有子节点返回上一层。

回到节点 2，然后访问 5，5没有子节点返回。

左子树遍历完成，回到根节点 1，接着访问右子树节点 3。

题目要求

给定一个二叉树的根节点，编写程序实现先序遍历并打印每个节点的值。要求如下：

请实现递归和非递归（使用栈）两种方法（本文中，C使用递归方法，C++使用非递归）。
输出每个节点的值。

做题思路

先序遍历是一种从根节点开始，依次遍历左子树和右子树的树遍历方法。可以用递归和迭代来实现：

递归方法：根据先序遍历的定义，先访问当前节点，然后递归地访问左子树和右子树。
非递归方法：使用栈来模拟递归过程。先将根节点压入栈中，之后在每次迭代中取出栈顶节点并访问其值，接着将右子节点和左子节点分别入栈（保证左节点先出栈）。

运用到的知识点

递归：函数调用自身以简化复杂问题，是二叉树遍历的典型方法。
栈（Stack）：一种后进先出的数据结构，用于实现非递归的先序遍历。
二叉树数据结构：二叉树中每个节点最多有两个子节点，即左子节点和右子节点。

示例代码

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; // 程序正常结束  
}

秒客网