C++如何建立链式二叉树

链式二叉树是一种常见的树形数据结构，它通过指针将节点连接起来。每个节点包含数据域和两个指针域，分别指向左子树和右子树。本文将介绍如何使用C++语言建立链式二叉树。

1. 定义二叉树节点结构

首先，我们需要定义一个结构体来表示二叉树的节点。每个节点包含三个部分：数据域、左子树指针和右子树指针。

struct TreeNode {
    int data;           // 数据域
    TreeNode* left;     // 左子树指针
    TreeNode* right;    // 右子树指针

    // 构造函数
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

在这个结构体中，data用于存储节点的值，left和right分别指向左子树和右子树。构造函数用于初始化节点的值和指针。

2. 创建二叉树

接下来，我们可以通过手动创建节点并连接它们来构建一个简单的二叉树。以下是一个示例：

int main() {
    // 创建根节点
    TreeNode* root = new TreeNode(1);

    // 创建左子树
    root->left = new TreeNode(2);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    // 创建右子树
    root->right = new TreeNode(3);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);

    // 输出二叉树的结构
    // 这里可以添加遍历代码来验证二叉树的结构

    return 0;
}

在这个示例中，我们创建了一个包含7个节点的二叉树。根节点的值为1，左子树的节点值为2、4、5，右子树的节点值为3、6、7。

3. 遍历二叉树

为了验证二叉树的结构是否正确，我们可以编写遍历代码来访问每个节点。常见的遍历方式有前序遍历、中序遍历和后序遍历。

3.1 前序遍历

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

void preOrder(TreeNode* root) {
    if (root == nullptr) return;

    std::cout << root->data << " ";  // 访问根节点
    preOrder(root->left);            // 遍历左子树
    preOrder(root->right);           // 遍历右子树
}

3.2 中序遍历

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

void inOrder(TreeNode* root) {
    if (root == nullptr) return;

    inOrder(root->left);             // 遍历左子树
    std::cout << root->data << " ";  // 访问根节点
    inOrder(root->right);            // 遍历右子树
}

3.3 后序遍历

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

void postOrder(TreeNode* root) {
    if (root == nullptr) return;

    postOrder(root->left);           // 遍历左子树
    postOrder(root->right);          // 遍历右子树
    std::cout << root->data << " ";  // 访问根节点
}

4. 释放二叉树内存

在使用完二叉树后，为了避免内存泄漏，我们需要手动释放每个节点的内存。可以通过后序遍历的方式依次释放节点。

void deleteTree(TreeNode* root) {
    if (root == nullptr) return;

    deleteTree(root->left);  // 释放左子树
    deleteTree(root->right); // 释放右子树
    delete root;             // 释放当前节点
}

5. 完整示例

以下是一个完整的示例，展示了如何创建、遍历和释放二叉树。

#include <iostream>

struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

void preOrder(TreeNode* root) {
    if (root == nullptr) return;

    std::cout << root->data << " ";
    preOrder(root->left);
    preOrder(root->right);
}

void inOrder(TreeNode* root) {
    if (root == nullptr) return;

    inOrder(root->left);
    std::cout << root->data << " ";
    inOrder(root->right);
}

void postOrder(TreeNode* root) {
    if (root == nullptr) return;

    postOrder(root->left);
    postOrder(root->right);
    std::cout << root->data << " ";
}

void deleteTree(TreeNode* root) {
    if (root == nullptr) return;

    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right = new TreeNode(3);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);

    std::cout << "Pre-order traversal: ";
    preOrder(root);
    std::cout << std::endl;

    std::cout << "In-order traversal: ";
    inOrder(root);
    std::cout << std::endl;

    std::cout << "Post-order traversal: ";
    postOrder(root);
    std::cout << std::endl;

    deleteTree(root);

    return 0;
}

6. 总结

通过以上步骤，我们可以在C++中建立链式二叉树，并进行遍历和内存释放。链式二叉树是一种灵活且常用的数据结构，适用于各种需要树形结构的场景。掌握其基本操作对于理解和应用更复杂的树形结构（如二叉搜索树、AVL树等）具有重要意义。