从零开始手搓链表二叉树：新手小白也能看懂的实现指南

一、简介和特点

链表二叉树是一种利用链表（动态内存分配）实现的二叉树数据结构。它通过节点间的指针连接形成树状结构，每个节点包含数据及指向左右子节点的指针。相比数组实现的二叉树，链表版本更灵活，无需预先分配固定空间，适合节点动态增删的场景。本文代码实现了一个简易链表二叉树类，支持数据添加、节点查找等基础功能，适合新手理解二叉树的底层逻辑。

二、与其他相比的优点

1. 动态内存管理：采用new动态分配节点，无需提前指定树大小，避免空间浪费。

2. 插入效率高：添加节点时通过数学公式计算位置，无需遍历查找父节点，适合构建完全二叉树。

3. 代码简洁：核心逻辑集中在add和find方法，递归结构清晰，便于学习递归算法。

三、实现步骤

1. 定义节点：使用TreeNode结构体，包含data、left、right成员，分别存储数据和子节点指针。

2. 构建二叉树类：BinaryTree类包含sum（节点总数）和root（根节点），构造函数初始化根节点。

3. 添加数据：

若树为空（sum=0），将数据存入根节点。

若树非空，计算新节点索引tmp（当前节点总数+1），通过find()找到父节点，根据tmp奇偶性将新节点挂载为左/右子节点。

4. 查找节点：递归算法根据索引（从1开始）定位节点。若索引为1返回根节点；否则，偶数索引递归向左找，奇数索引递归向右找。

5. 待完善：print()方法为空，需补充递归遍历打印逻辑（如前序、中序遍历）。

四、代码和注释

#include <iostream> // 包含输入输出流库
#include <vector> // 包含向量容器库
using namespace std; // 使用标准命名空间

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

// 链表实现的二叉树类
class BinaryTree {
private:
    int sum = 0; // 记录树中节点总数
    TreeNode* root; // 根节点指针

public:
    // 构造函数：初始化根节点
    BinaryTree() {
        root = new TreeNode; // 动态分配根节点内存
    }

    // 添加数据到二叉树（按特定规则构建完全二叉树）
    void add(int data) {
        if (sum == 0) { // 若树为空（sum=0表示无节点）
            root->data = data; // 将数据存入根节点
            sum++; // 节点总数+1
        } else { // 树非空时，按索引规则添加节点
            int tmp = sum + 1; // 计算新节点的目标索引（从1开始）
            TreeNode* tmpnode = find(tmp / 2 - 1); // 查找父节点（索引为tmp/2-1）
            TreeNode* newnode = new TreeNode; // 创建新节点
            newnode->data = data; // 存入数据
            if (tmp % 2 == 0) { // 若tmp为偶数，新节点为左子节点
                tmpnode->left = newnode;
            } else { // 否则为右子节点
                tmpnode->right = newnode;
            }
            sum++; // 节点总数+1
        }
    }

    // 根据索引（从1开始）查找节点（递归实现）
    TreeNode* find(int idx) {
        if (idx + 1 == 1) { // 若索引为1（根节点），直接返回根节点
            return root;
        }
        if (idx % 2 == 0) { // 若索引为偶数，递归查找左子节点
            return find(idx / 2 - 1)->left;
        } else { // 若索引为奇数，递归查找右子节点
            return find(idx / 2 - 1)->right;
        }
    }

    // 打印二叉树（未实现，需补充递归遍历逻辑）
    void print() {
        // TODO: 补充递归打印节点值的代码
    }
};

五、总结

链表二叉树是理解数据结构的重要实践案例。通过手搓代码，新手可直观感受指针连接、递归算法的应用。本实现虽简易，但已涵盖核心逻辑，适合作为学习起点。建议读者尝试补充print()方法，探索不同遍历方式，进一步掌握二叉树操作。未来可扩展至平衡树、搜索树等高级结构。