当前位置：首页 > 其他 > 手搓二叉树构建类代码详解：从入门到实践（适合新手小白）

手搓二叉树构建类代码详解：从入门到实践（适合新手小白）

4周前 (06-17)

一、简介和应用

二叉树是数据结构中常见的一种树形结构，每个节点最多有两个子节点（左子节点和右子节点）。它广泛应用于算法设计、数据存储与搜索（如二叉搜索树）、表达式解析等领域。本文将通过手写的C++代码，讲解如何构建一个基础的二叉树类，帮助新手理解其原理与实现逻辑。通过实例代码，读者可快速掌握二叉树的创建、节点连接及遍历方法。

二、特点和注意事项

1. 递归构建：代码采用递归方式创建节点，简洁但需注意递归边界条件（如数组索引越界）。

2. 数组存储：节点通过数组索引关联，需确保数据数组结构符合完全二叉树特性（即节点i的左右子节点索引为2i+1和2i+2）。

3. 内存管理：构造函数中使用new动态分配内存，需注意在程序结束时释放（但示例中未处理，实际应用需补充delete）。

4. 代码优化提示：当前实现未考虑非完全二叉树情况，如需扩展需调整节点创建逻辑。

三、实现步骤

1. 定义节点结构：treenode包含数据data及左右指针left/right，初始化为空。

2. 构造二叉树：提供三种构造函数：

binarytree(int a[], int size)：通过数组创建完全二叉树，使用循环连接节点。

binarytree(int size)：创建指定大小的空节点数组（未初始化数据）。

binarytree()：默认创建10000个节点的数组（不建议使用，易浪费内存）。

3. 递归创建节点：creat()函数通过递归生成子树，核心逻辑：

检查终止条件（索引越界或数据为0）。

创建当前节点并赋值。

递归生成左子树（索引2i+1）和右子树（索引2i+2）。

4. 打印树结构：print()递归遍历，按根-左-右顺序输出节点数据。

四、代码及注释

#include <iostream>
using namespace std;

// 1. 节点定义
struct TreeNode {
    int data = 0;       // 节点数据（默认初始化为0）
    TreeNode* left = nullptr;   // 左子节点指针
    TreeNode* right = nullptr;  // 右子节点指针
};

class BinaryTree {
private:
    TreeNode* nodes;  // 指向节点数组的指针

public:
    // 2. 构造函数（通过数组构建完全二叉树）
    // 注意：此版本无法递归（因构造函数无返回值）
    BinaryTree(int a[], int size) {
        nodes = new TreeNode[size];  // 分配节点数组
        for (int i = 0; i < size; i++) {
            nodes[i].data = a[i];  // 填充节点数据
        }
        // 连接节点（假设完全二叉树结构）
        for (int i = 0; i < size - (size + 1) / 2; i++) {  // 父节点索引范围
            // 计算左/右子节点索引（可能需检查公式是否正确）
            nodes[i].left = &nodes[i * 2 + 1];
            nodes[i].right = &nodes[i * 2 + 2];
        }
    }

    // 3. 其他构造函数（简化版本）
    BinaryTree(int size) {
        nodes = new TreeNode[size];  // 仅分配空间
    }
    BinaryTree() {
        nodes = new TreeNode[10000];  // 默认大容量（不推荐）
    }

    // 4. 递归创建节点（辅助函数）
    TreeNode* creat(int a[], int size, int nodeid) {
        // 终止条件：索引超界或数据为0
        if (nodeid >= size || a[nodeid] == 0) {
            return nullptr;
        }
        // 创建当前节点并赋值
        TreeNode* tmpnode = &nodes[nodeid];
        tmpnode->data = a[nodeid];
        // 递归构建子树
        tmpnode->left = creat(a, size, 2 * nodeid + 1);  // 左子节点索引应为2i+1
        tmpnode->right = creat(a, size, 2 * nodeid + 2);  // 右子节点索引应为2i+2
        return tmpnode;
    }

    // 5. 打印树（递归遍历）
    void print(TreeNode* node) {
        // 前序遍历输出
        if (node!= nullptr && node->data!= 0) {
            cout << node->data;   // 输出根节点
            print(node->left);    // 递归左子树
            print(node->right);   // 递归右子树
        }
    }
    void print() {  // 封装调用
        print(nodes);
    }
};