一、简介和特点链表二叉树是一种利用链表（动态内存分配）实现的二叉树数据结构。它通过节点间的指针连接形成树状结构，每个节点包含数据及指向左右子节点的指针。相比数组实现的二叉树，链表版本更灵活，无需预先分配固定空间，适合节点动态增删的场景。本文代码实现了一个简易链表二叉树类，支持数据添加、节点查找等基础功能，适合新手理解二叉树的底层逻辑。 二、与其他相比的优点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()方法，探索不同遍历方式，进一步掌握二叉树操作。未来可扩展至平衡树、搜索树等**结构。
| 
发表于 2025-7-14 11:24:36