二叉树的遍历

适用级别：普及组
难度系数：4

洛谷：P1827
OJ平台：U0306

深度优先遍历(Depth First Traversals )：
1、前序遍历(Preorder)：先访问根结点，然后再前序遍历左子树，再前序遍历右子树(Root,Left,Right)
2、中序遍历(Inorder)：先遍历根结点的左子树，然后是访问根结点，最后遍历右子树(Left,Root,Right)
3、后序遍历(Postorder)：从左到右先叶子后结点的方式遍历访问左右子树，最后访问根结点(Left,Right,Root)
广度优先遍历(Breadth First Traversals )：
层序遍历(Level Order )：从根结点从上往下逐层遍历，在同一层，按从左到右的顺序对结点访问

树的四种遍历方式

前序遍历结果为：ABDFECGHI

中序遍历结果为：DBEFAGHCI

后序遍历结果为：DEFBHGICA

层序遍历结果为：ABCDFGIEH

树的深度遍历代码实现：

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2025-01-11 05:03:55
 * 最后修改: 2025-01-11 05:11:07
 * 文件描述: 二叉树的深度遍历
****************************************************************/


#include <iostream>
using namespace std;

// 定义二叉树节点的结构体
struct Node {
    int data;            // 节点数据
    struct Node *left;   // 指向左子节点的指针
    struct Node *right;  // 指向右子节点的指针
};

// 创建新节点的函数
Node* newNode(int data) {
    Node* temp = new Node;    // 动态分配内存创建一个新的节点
    temp->data = data;        // 节点数据赋值
    temp->left = NULL;        // 左子节点初始化为 NULL
    temp->right = NULL;       // 右子节点初始化为 NULL
    return temp;              // 返回新创建的节点
}

// 中序遍历函数（递归实现）：左子树 -> 根节点 -> 右子树
void printInorder(struct Node* node) {
    if (node == NULL) return;       // 递归终止条件：当前节点为空
    printInorder(node->left);       // 递归遍历左子树
    cout << node->data << " ";      // 输出当前节点的数据
    printInorder(node->right);      // 递归遍历右子树
}

// 前序遍历函数（递归实现）：根节点 -> 左子树 -> 右子树
void printPreorder(struct Node* node) {
    if (node == NULL) return;       // 递归终止条件：当前节点为空
    cout << node->data << " ";      // 输出当前节点的数据
    printPreorder(node->left);      // 递归遍历左子树
    printPreorder(node->right);     // 递归遍历右子树
}

// 后序遍历函数（递归实现）：左子树 -> 右子树 -> 根节点
void printPostorder(struct Node* node) {
    if (node == NULL) return;       // 递归终止条件：当前节点为空
    printPostorder(node->left);     // 递归遍历左子树
    printPostorder(node->right);    // 递归遍历右子树
    cout << node->data << " ";      // 输出当前节点的数据
}

// 主函数
int main() {
    // 手动创建二叉树的节点
    struct Node* root = newNode(1);               // 创建根节点，数据为 1
    root->left = newNode(2);                      // 创建左子节点，数据为 2
    root->right = newNode(3);                     // 创建右子节点，数据为 3
    root->left->left = newNode(4);                // 创建左子节点的左子节点，数据为 4
    root->left->right = newNode(5);               // 创建左子节点的右子节点，数据为 5

    // 输出前序遍历结果
    cout << "\nPreorder traversal of binary tree is \n";
    printPreorder(root);

    // 输出中序遍历结果
    cout << "\nInorder traversal of binary tree is \n";
    printInorder(root);

    // 输出后序遍历结果
    cout << "\nPostorder traversal of binary tree is \n";
    printPostorder(root);

    return 0; // 程序结束
}

广度优先遍历代码实现：

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2025-01-11 05:16:26
 * 最后修改: 2025-01-11 05:25:54
 * 文件描述: 二叉树的层遍历
****************************************************************/

#include <iostream>
#include <queue> // 引入队列头文件
using namespace std;

// 定义二叉树节点结构体
struct node {
    int data;          // 节点数据
    node* left;        // 左子节点指针
    node* right;       // 右子节点指针
};

// 创建新节点的函数
node* newNode(int data) {
    node* Node = new node(); // 动态分配新节点内存
    Node->data = data;       // 设置节点数据
    Node->left = NULL;       // 初始化左子节点为空
    Node->right = NULL;      // 初始化右子节点为空
    return Node;             // 返回新节点
}

// 使用队列实现二叉树的层序遍历
void printLevelOrder(node* root) {
    if (root == NULL) return; // 空树直接返回

    queue<node*> q;           // 定义一个队列，用于存储节点
    q.push(root);             // 将根节点入队

    while (!q.empty()) {      // 当队列不为空时
        node* current = q.front(); // 获取队首节点
        q.pop();                  // 将队首节点出队

        cout << current->data << " "; // 输出当前节点的数据

        // 将当前节点的左子节点入队（如果存在）
        if (current->left != NULL) 
            q.push(current->left);

        // 将当前节点的右子节点入队（如果存在）
        if (current->right != NULL) 
            q.push(current->right);
    }
}

// 主函数
int main() {
    // 手动构造二叉树
    node* root = newNode(1);         // 创建根节点，数据为 1
    root->left = newNode(2);         // 创建左子节点，数据为 2
    root->right = newNode(3);        // 创建右子节点，数据为 3
    root->left->left = newNode(4);   // 左子节点的左子节点，数据为 4
    root->left->right = newNode(5);  // 左子节点的右子节点，数据为 5

    // 打印二叉树的层序遍历结果
    cout << "Level Order traversal of binary tree is ";
    printLevelOrder(root);

    return 0; // 程序结束
}

洛谷：U0306/P1827 P1030 B3642

Quizzes

Back to Lesson

Next Quiz

数据结构与算法

二叉树的遍历