头插法实现的树结构：链表式多叉树实现指南

一、简介和特点

头插法实现的树是一种使用链表存储子节点的多叉树结构。本文实现的树类通过链表头插法高效管理子节点关系，适合需要频繁插入子节点的场景。

‌主要特点‌：

动态子节点管理：使用链表存储子节点
高效插入：头插法实现O(1)时间复杂度的子节点插入
泛型支持：模板类设计支持多种数据类型
预分配节点：预先分配节点数组提高性能
递归遍历：深度优先遍历打印树结构

二、与其他实现的优点

相比传统树实现，这种头插法链表式实现有以下优势：

‌插入高效‌：头插法保证子节点插入为O(1)时间
‌内存连续‌：预分配节点数组减少内存碎片
‌灵活扩展‌：链表结构支持动态增减子节点
‌泛型设计‌：模板类支持多种数据类型
‌索引访问‌：通过ID直接访问任意节点

三、实现步骤解析

‌1.链表节点定义‌：创建通用链表节点结构
‌2.树节点定义‌：
- 包含数据域和子节点链表头指针
- 实现头插法添加子节点
3‌.树类设计‌：
- 预分配节点数组
- 提供根节点设置方法
- 实现父子关系建立
- 支持节点数据赋值
4‌.遍历打印‌：递归深度优先遍历打印树结构

四、完整代码和注释

#include<iostream>
using namespACe std;

// 链表节点模板结构
template<typename T>
struct listnode
{
    T data;            // 节点数据
    listnode* next;    // 指向下一个节点的指针
    listnode(T x) :data(x), next(nullptr){}  // 构造函数初始化
};

// 树节点模板结构
template<typename T>
struct treenode
{
    T data=0;  // 节点存储的数据
    // 子节点链表头指针，指向该节点的所有子节点
    listnode<treenode<T>*>* childrenhead=nullptr;

    // 添加子节点方法
    void addchild(treenode<T>* newchild)
    {
        // 创建新的链表节点包装子节点
        listnode<treenode<T>*>* childnode = new listnode<treenode<T>*>(newchild);

        if (childrenhead == nullptr)  // 如果没有子节点
        {
            childrenhead = childnode;  // 直接设置为头节点
        }
        else
        {
            // 头插法：新节点指向原头节点，然后更新头节点
            childnode->next = childrenhead;
            childrenhead = childnode;
        }
    }
};

// 树模板类
template<typename T>
class tree
{
    treenode<T>* root;  // 根节点指针
    treenode<T>* nodes; // 预分配的节点数组

public:
    // 默认构造函数，预分配10000个节点
    tree():root(new treenode<T>),nodes(new treenode<T>[10000]) {}

    // 指定最大节点数的构造函数
    tree(int maxnodes):root(nullptr),nodes(new treenode<T>[maxnodes]){}

    // 析构函数
    ~tree()
    {
        nodes = nullptr;
        root = nullptr;
        delete[] nodes;
        delete root;
    }

    // 通过ID获取树节点
    treenode<T>* gettreenode(int id)
    {
        return &nodes[id];
    }

    // 设置根节点
    void setroot(int rootid)
    {
        root = gettreenode(rootid);
    }

    // 添加子节点关系
    void addchild(int parentid, int sonid)
    {
        treenode<T>* parent = gettreenode(parentid);
        treenode<T>* son = gettreenode(sonid);
        parent->addchild(son);  // 调用头插法添加子节点
    }

    // 给节点赋值
    void assigndata(int nodeid, int data)
    {
        treenode<T>* node = gettreenode(nodeid);
        node->data = data;
    }

    // 递归打印树结构(深度优先)
    void print(treenode<T>* node)
    {
        if (node == nullptr)  // 默认从根节点开始
        {
            node = root;
        }
        cout << node->data<<" ";  // 打印当前节点数据

        // 遍历所有子节点递归打印
        listnode<treenode<T>*>* tmp = node->childrenhead;
        while (tmp)
        {
            print(tmp->data);
            tmp = tmp->next;
        }
    }
};