手搓尾插法树类代码详解：从实现到优化的全流程指南

一、简介和特点

尾插法树是一种基于链表实现树结构的手动编码方式，通过将节点的孩子节点以尾插方式插入链表，实现树形数据的存储与操作。本文代码示例采用C++模板类，允许泛型数据类型，核心特点包括：

1. 使用listnode作为子节点链表单元，treenode存储数据及子节点链表头指针；

2. tree类管理节点数组，支持动态分配内存，提供根节点设置、添加子节点、数据赋值及打印功能；

3. 尾插法插入子节点时，从链表末尾添加，避免头插法导致的遍历顺序颠倒，逻辑更直观。

二、优点

1. 逻辑清晰：尾插法按节点自然顺序添加，符合“父-子”层级关系，减少遍历时的反向调整；

2. 内存管理可控：通过节点数组预分配（如tree(int maxnodes)），避免频繁动态分配内存碎片；

3. 灵活性：模板类支持任意数据类型，适用于不同场景（如整数树、字符串树等）；

4. 简洁性：相比递归构建或复杂指针操作，代码结构更易理解，适合新手学习树结构基础。

三、实现步骤

1. 定义节点结构

    listnode：链表节点，存储指向treenode的指针，通过next指向下一个节点；

    treenode：树节点，包含数据data和子节点链表头指针childrenhead。

2. 构建树类tree

    初始化节点数组：nodes为treenode指针数组，通过构造函数传入最大节点数（默认10000）；

    根节点设置：通过setroot(int rootid)将指定索引的节点设为根；

    子节点添加：addchild(int parentid, int sonid)通过父/子ID定位节点，调用addchild(treenode* node)尾插子节点到父节点链表。

3. 数据操作与遍历

    assigndata(int id, T data)：为指定ID节点赋值；

    print()：递归打印根节点及其所有子节点，通过链表遍历子树。

四、代码及注释

#include <iostream>
using namespace std;

// 链表节点模板，存储指向T类型节点的指针
template <typename T>
struct listnode {
    T* data;         // 指向树节点的地址
    listnode* next = nullptr;  // 指向下一个节点

    // 构造：传入节点指针初始化data
    listnode(T* d) {
        data = d;
    }
    // 空构造（可能用于初始化头节点）
    listnode() {}
};

// 树节点模板，存储数据和子节点链表头指针
template <typename T>
struct treenode {
    T data;                      // 节点数据
    listnode<treenode<T>*>* childrenhead = nullptr;  // 子节点链表头

    // 添加子节点：尾插法
    void addchild(treenode<T>* node) {
        // 创建新子节点链表节点，指向传入的node
        listnode<treenode<T>*>* newchild = new listnode<treenode<T>*>(node);
        if (childrenhead == nullptr) {  // 若链表为空，直接作为头节点
            childrenhead = newchild;
        } else {                       // 否则从末尾插入
            listnode<treenode<T>*>* tmp = childrenhead;
            while (tmp->next) {        // 遍历到末尾
                tmp = tmp->next;
            }
            tmp->next = newchild;      // 尾插新节点
        }
    }
};

// 树类模板，管理节点数组和树操作
template <typename T>
class tree {
    treenode<T>* nodes;             // 节点数组指针
    treenode<T>* root = nullptr;     // 根节点

public:
    // 构造：默认分配10000个节点
    tree() {
        nodes = new treenode<T>[10000];
    }
    // 构造：传入最大节点数
    tree(int maxnodes) {
        nodes = new treenode<T>[maxnodes];
    }
    // 析构：释放节点数组
    ~tree() {
        delete[] nodes;
    }

    // 设置根节点（通过ID索引）
    void setroot(int rootid) {
        root = &nodes[rootid];
    }

    // 添加子节点（通过父/子ID）
    void addchild(int parentid, int sonid) {
        treenode<T>* parent = &nodes[parentid];
        treenode<T>* son = &nodes[sonid];
        parent->addchild(son);
    }

    // 为节点赋值
    void assigndata(int id, T data) {
        treenode<T>* node = &nodes[id];
        node->data = data;
    }

    // 递归打印节点及其子节点
    void print(treenode<T>* node) {
        cout << node->data;          // 打印当前数据
        listnode<treenode<T>*>* tmp = node->childrenhead;
        while (tmp) {               // 遍历子节点链表
            print(tmp->data);        // 递归打印子节点
            tmp = tmp->next;
        }
    }

    // 打印整棵树（从根开始）
    void print() {
        print(root);
    }
};

五、总结

本文通过尾插法树类的代码示例，展示了手动实现树结构的基础逻辑：利用链表维护子节点顺序，通过节点数组简化内存管理。该实现适合学习树结构原理，尤其适合新手理解“尾插”操作如何避免头插法的遍历问题。在实际应用中，可根据需求扩展（如添加删除节点、搜索等功能），但需注意内存释放细节（如节点删除时链表清理）。通过注释与步骤解析，读者可快速掌握从零构建树类的方法，为更复杂的算法设计打下基础。