当前位置：首页 > article >正文

二叉树遍历：C++ 实现指南

article 2025/1/6 14:11:42

二叉树是计算机科学中一个基础且重要的数据结构，广泛应用于算法和各种应用中。掌握二叉树的遍历是学习数据结构的关键一步。本文将详细介绍二叉树的前序、中序和后序遍历，使用C++语言编写，适合新手入门。

什么是二叉树？

二叉树是一种特殊的树形数据结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。它具有以下特点：
- 每个节点至多有两个子节点。
- 节点的子节点分为左子节点和右子节点。
- 左子节点的值总是小于或等于它的父节点的值。
- 右子节点的值总是大于或等于它的父节点的值。

二叉树的遍历

二叉树的遍历指的是按照某种顺序访问树中的每个节点，使得每个节点都被访问一次。常见的遍历方式有三种：前序遍历、中序遍历和后序遍历。

1. 前序遍历（Pre-order Traversal）

前序遍历的顺序是：根节点 -> 左子树 -> 右子树。

步骤：
1. 访问根节点。
2. 遍历左子树。
3. 遍历右子树。

2. 中序遍历（In-order Traversal）

中序遍历的顺序是：左子树 -> 根节点 -> 右子树。

步骤：
1. 遍历左子树。
2. 访问根节点。
3. 遍历右子树。

3. 后序遍历（Post-order Traversal）

后序遍历的顺序是：左子树 -> 右子树 -> 根节点。

步骤：
1. 遍历左子树。
2. 遍历右子树。
3. 访问根节点。

二叉树节点定义

首先，我们需要定义一个二叉树节点的结构体：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

前序遍历（Pre-order Traversal）

void preOrderTraversal(TreeNode* root) {
    if (root == nullptr) return;
    std::cout << root->val << " ";
    preOrderTraversal(root->left);
    preOrderTraversal(root->right);
}

中序遍历（In-order Traversal）

void inOrderTraversal(TreeNode* root) {
    if (root == nullptr) return;
    inOrderTraversal(root->left);
    std::cout << root->val << " ";
    inOrderTraversal(root->right);
}

后序遍历（Post-order Traversal）

void postOrderTraversal(TreeNode* root) {
    if (root == nullptr) return;
    postOrderTraversal(root->left);
    postOrderTraversal(root->right);
    std::cout << root->val << " ";
}

迭代前序遍历

#include <stack>
void iterativePreOrderTraversal(TreeNode* root) {
    if (!root) return;
    std::stack<TreeNode*> stack;
    stack.push(root);
    while (!stack.empty()) {
        TreeNode* node = stack.top();
        stack.pop();
        std::cout << node->val << " ";
        if (node->right) stack.push(node->right);
        if (node->left) stack.push(node->left);
    }
}

迭代中序遍历

void iterativeInOrderTraversal(TreeNode* root) {
    if (!root) return;
    std::stack<TreeNode*> stack;
    TreeNode* current = root;
    while (current || !stack.empty()) {
        while (current) {
            stack.push(current);
            current = current->left;
        }
        current = stack.top();
        stack.pop();
        std::cout << current->val << " ";
        current = current->right;
    }
}

迭代后序遍历

void iterativePostOrderTraversal(TreeNode* root) {
    if (!root) return;
    std::stack<TreeNode*> stack1, stack2;
    stack1.push(root);
    while (!stack1.empty()) {
        TreeNode* node = stack1.top();
        stack1.pop();
        stack2.push(node);
        if (node->left) stack1.push(node->left);
        if (node->right) stack1.push(node->right);
    }
    while (!stack2.empty()) {
        std::cout << stack2.top()->val << " ";
        stack2.pop();
    }
}

主函数示例

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);

    // 执行遍历
    std::cout << "Pre-order Traversal: ";
    preOrderTraversal(root);
    std::cout << std::endl;

    std::cout << "In-order Traversal: ";
    inOrderTraversal(root);
    std::cout << std::endl;

    std::cout << "Post-order Traversal: ";
    postOrderTraversal(root);
    std::cout << std::endl;

    // 迭代遍历
    std::cout << "Iterative Pre-order Traversal: ";
    iterativePreOrderTraversal(root);
    std::cout << std::endl;

    std::cout << "Iterative In-order Traversal: ";
    iterativeInOrderTraversal(root);
    std::cout << std::endl;

    std::cout << "Iterative Post-order Traversal: ";
    iterativePostOrderTraversal(root);
    std::cout << std::endl;

    return 0;
}