数据结构（c++版）：树的实现保姆级教程

Jeff-Nolan

2273人浏览 · 2025-10-15 19:53:39

Jeff-Nolan · 2025-10-15 19:53:39 发布

树是计算机科学中最重要的数据结构之一，它模拟了现实世界中的层级关系。下面我将详细解释树结构中各个类的具体实现，包括类函数的具体实现细节。

1. 链表节点类：`ListNode`

template<typename T>
struct ListNode
{
    T data;         // 节点存储的数据
    ListNode* next; // 指向下一个节点的指针
    
    // 构造函数
    ListNode(T d) :data(d), next(NULL) {};
};

实现解析：

这是一个简单的链表节点结构
data成员存储节点数据，类型由模板参数T决定
next指针指向链表中的下一个节点
构造函数使用初始化列表来设置data和next的值

比喻理解：
想象链表节点就像火车车厢：

data是车厢里装载的货物
next是连接下一节车厢的挂钩
构造函数就是制造新车厢的过程，指定装载什么货物(d)，并把挂钩(next)初始化为空

2. 树节点类：`treeNode`

template<typename T>
struct treeNode
{
    T data;  // 节点存储的数据
    ListNode<treeNode<T>*>* Childenhead; // 子节点链表的头指针
    
    // 构造函数
    treeNode() { Childenhead = NULL; }
    
    // 添加子节点函数
    void AddChild(treeNode<T>* node)
    {
        // 创建新的链表节点，存储要添加的子节点指针
        ListNode<treeNode<T>*>* childnode = new ListNode<treeNode<T>*>(node);
        
        if (Childenhead == NULL) // 如果还没有子节点
        {
            Childenhead = childnode;
        }
        else 
        {
            // 使用头插法将新节点插入链表
            childnode->next = Childenhead;
            Childenhead = childnode;
        }
    }
};

实现解析：

data存储该树节点的数据
Childenhead是指向子节点链表的指针，链表中的每个节点都存储着一个指向子树的指针
AddChild函数实现：
1. 创建一个新的链表节点来存储要添加的子节点
2. 如果当前没有子节点，直接将其设为头节点
3. 否则使用头插法将新节点插入链表

比喻理解：
把树节点想象成一个人：

data是这个人的名字
Childenhead是他手中拿着的孩子名单（链表）
AddChild就像给这个人添加一个孩子：
1. 先制作一张新的孩子名片（链表节点）
2. 如果他没有孩子名单，就直接拿着这张名片
3. 如果已经有名单，就把新名片放在名单最前面

3. 树类：`Tree`

构造函数和析构函数

template<typename T>
Tree<T>::Tree()
{
    nodes = new treeNode<T>[100001]; // 默认创建100001个节点的空间
}

template<typename T>
Tree<T>::Tree(int maxNode)
{
    nodes = new treeNode<T>[maxNode]; // 创建指定数量的节点空间
}

template<typename T>
Tree<T>::~Tree()
{
    delete[] nodes; // 释放节点数组内存
}

实现解析：

提供了两个构造函数：默认构造和指定最大节点数的构造
析构函数负责释放动态分配的节点数组内存

比喻理解：

构造函数就像准备一个空白的家族族谱本，可以指定要记录多少代人
析构函数就像族谱用完后，把它安全地销毁

获取节点函数

template<typename T>
treeNode<T>* Tree<T>::GetTreeNode(int id)
{
    return &nodes[id]; // 返回节点数组中指定id的节点的地址
}

实现解析：

通过节点ID（数组索引）直接访问对应的树节点
返回的是节点的指针，而不是节点本身

比喻理解：
就像根据编号快速找到族谱中的某一页

设置根节点函数

template<typename T>
void Tree<T>::SetRoot(int rootId)
{
    root = GetTreeNode(rootId); // 获取指定ID的节点并设为根
}

实现解析：

调用GetTreeNode获取指定节点
将该节点设为树的根节点

比喻理解：
就像指定族谱中的某个人为家族的始祖

添加子节点函数

template<typename T>
void Tree<T>::AddChild(int parentId, int sonId)
{
    // 获取父节点和子节点
    treeNode<T>* parentNode = GetTreeNode(parentId);
    treeNode<T>* sonNode = GetTreeNode(sonId);
    
    // 调用父节点的AddChild方法添加子节点
    parentNode->AddChild(sonNode);
}

实现解析：

根据ID获取父节点和子节点
调用父节点的AddChild方法建立父子关系

比喻理解：
就像在族谱中记录"某人是某人的孩子"这样的关系

赋值函数

template<typename T>
void Tree<T>::AssignData(int id, T data)
{
    GetTreeNode(id)->data = data; // 给指定节点赋值
}

实现解析：

获取指定节点并设置其data成员的值

比喻理解：
就像给族谱中的某个人填写详细信息（如姓名、生日等）

打印函数（深度优先遍历）

template<typename T>
void Tree<T>::Print(treeNode<T>* node)
{
    if (node == NULL) // 如果未指定节点，默认从根开始
    {
        node = root;
    }
    
    cout << node->data; // 先打印当前节点数据
    
    // 遍历所有子节点
    ListNode<treeNode<T>*>* tmp = node->Childenhead;
    while (tmp) 
    {
        Print(tmp->data); // 递归打印子节点
        tmp = tmp->next;
    }
}

实现解析：

如果没有指定节点，默认从根节点开始
先打印当前节点的数据
遍历当前节点的所有子节点，递归调用Print函数

比喻理解：
就像家族聚会时的介绍顺序：

先介绍当前这个人
然后依次介绍他/她的每个孩子
对每个孩子重复同样的介绍过程

这种遍历方式称为"深度优先遍历"，因为它会沿着一条分支一直深入到底，然后再回溯到其他分支。

4. 主函数示例

int main()
{
    Tree<char>T(9); // 创建最多9个节点的树
    
    // 设置根节点并赋值
    T.SetRoot(0);
    T.AssignData(0, 'a');
    
    // 给其他节点赋值
    T.AssignData(1, 'b');
    T.AssignData(2, 'c');
    // ... 省略其他赋值
    
    // 建立父子关系
    T.AddChild(0,2); // a的孩子是c
    T.AddChild(0,1); // a的孩子是b
    T.AddChild(1,3); // b的孩子是d
    // ... 省略其他关系
    
    T.Print(); // 打印整棵树
    return 0;
}

构建的树结构：

        a
      /   \
     b     c
    /    /   \
   d    e     f
  / \
 g   h
    /
   i

打印输出：a c e f b d h i g

5. 关键点总结

节点存储：
- 使用数组存储所有树节点，通过索引(ID)访问
- 每个树节点包含数据和子节点链表
子节点管理：
- 使用链表来存储一个节点的所有子节点
- 采用头插法添加新子节点
遍历算法：
- 实现的是深度优先遍历(DFS)
- 先访问根节点，然后递归访问每个子节点
模板设计：
- 使用模板使树可以存储任意类型的数据
- 提高了代码的复用性和灵活性
内存管理：
- 构造函数动态分配节点数组
- 析构函数负责释放内存

这种树结构实现虽然简单，但包含了树的核心概念和操作，是理解更复杂树结构（如二叉树、B树等）的良好基础。

print函数递归详解：

深度解析树打印函数中的递归操作

递归是处理树结构最自然、最优雅的方式之一。让我们重点解析Print函数中的递归操作，理解它是如何遍历整棵树的。

打印函数代码回顾

template<typename T>
void Tree<T>::Print(treeNode<T>* node)
{
    if (node == NULL) // 如果未指定节点，默认从根开始
    {
        node = root;
    }
    
    cout << node->data; // 先打印当前节点数据
    
    // 遍历所有子节点
    ListNode<treeNode<T>*>* tmp = node->Childenhead;
    while (tmp) 
    {
        Print(tmp->data); // 递归打印子节点
        tmp = tmp->next;
    }
}

递归执行过程详解

让我们用示例树来逐步分析递归过程：

        a
      /   \
     b     c
    /    /   \
   d    e     f
  / \
 g   h
    /
   i

第一步：从根节点开始

调用Print()不传参数，默认从根节点'a'开始
打印'a'
开始遍历'a'的子节点链表（包含'b'和'c'）

第二步：处理第一个子节点'b'

递归调用Print(b)
打印'b'
开始遍历'b'的子节点链表（只包含'd'）
- 递归调用Print(d)
  - 打印'd'
  - 开始遍历'd'的子节点链表（包含'g'和'h')
    - 递归调用Print(g)
      - 打印'g'
      - 'g'没有子节点，返回
    - 递归调用Print(h)
      - 打印'h'
      - 开始遍历'h'的子节点链表（包含'i')
        
        递归调用Print(i)
        
        打印'i'
        
        'i'没有子节点，返回
- 'd'的子节点遍历完成，返回
'b'的子节点遍历完成，返回

第三步：处理第二个子节点'c'

回到'a'的子节点遍历，处理下一个节点'c'
递归调用Print(c)
打印'c'
开始遍历'c'的子节点链表（包含'e'和'f')
- 递归调用Print(e)
  - 打印'e'
  - 'e'没有子节点，返回
- 递归调用Print(f)
  - 打印'f'
  - 'f'没有子节点，返回
'c'的子节点遍历完成，返回

最终打印顺序

按照上述过程，打印顺序为：a b d g h i c e f

递归调用栈可视化

让我们用调用栈的方式来理解递归过程：

1. Print(a)
   - 打印 a
   - 遍历a的子节点[b, c]
   
   2. Print(b)
      - 打印 b
      - 遍历b的子节点[d]
      
      3. Print(d)
         - 打印 d
         - 遍历d的子节点[g, h]
         
         4. Print(g)
            - 打印 g
            - 无子节点，返回
         
         5. Print(h)
            - 打印 h
            - 遍历h的子节点[i]
            
            6. Print(i)
               - 打印 i
               - 无子节点，返回
   
   7. Print(c)
      - 打印 c
      - 遍历c的子节点[e, f]
      
      8. Print(e)
         - 打印 e
         - 无子节点，返回
      
      9. Print(f)
         - 打印 f
         - 无子节点，返回

递归的核心思想

这个递归过程体现了深度优先搜索(DFS)的核心思想：

先处理当前节点：首先访问并打印当前节点的数据
然后处理所有子节点：对每个子节点递归调用Print函数
递归终止条件：当节点没有子节点时，递归自然终止

递归的比喻理解

想象你在探索一个迷宫：

你站在当前房间（节点），先记录下这个房间的特征（打印数据）
然后你检查这个房间的所有门（子节点）
对每扇门：
- 你走进去（递归调用）
- 在新房间里重复同样的过程
- 探索完这个分支后，你退回原来的房间
当你遇到没有门的房间（叶子节点）时，就停止前进

递归的优缺点

优点：

代码简洁：用很少的代码表达了复杂的遍历逻辑
符合树的结构：树本身就是递归定义的，递归处理很自然
易于理解：一旦掌握递归思维，代码逻辑非常直观

缺点：

栈空间消耗：每次递归调用都会消耗栈空间，对于非常深的树可能导致栈溢出
效率问题：递归调用有一定开销，对于性能要求极高的场景可能不合适

非递归实现对比

为了更好理解递归，我们看看如何用栈来实现非递归的深度优先遍历：

void Tree<T>::PrintIterative()
{
    if (root == NULL) return;
    
    stack<treeNode<T>*> s;
    s.push(root);
    
    while (!s.empty())
    {
        treeNode<T>* current = s.top();
        s.pop();
        
        cout << current->data;
        
        // 将子节点逆序压入栈中，保证顺序正确
        ListNode<treeNode<T>*>* child = current->Childenhead;
        stack<treeNode<T>*> temp;
        while (child)
        {
            temp.push(child->data);
            child = child->next;
        }
        
        while (!temp.empty())
        {
            s.push(temp.top());
            temp.pop();
        }
    }
}

这个非递归版本使用显式的栈来模拟递归过程，避免了递归调用的开销，但代码相对复杂。

递归的适用场景

在这种树遍历场景中，递归特别适合因为：

问题可分解：处理树的问题可以分解为"处理当前节点+处理子树"的相同问题
深度可控：通常树的深度不会太大，栈溢出风险小
代码清晰：递归代码更易于编写和维护

总结

Print函数中的递归操作展示了处理树结构的经典模式：

先处理当前节点
然后递归处理所有子节点
自然处理边界条件

这种递归思维不仅适用于树的遍历，也是解决许多分治问题的关键。理解这种递归模式，将为你学习更复杂的算法和数据结构打下坚实基础。

源码及其运行：

#include<iostream>
#include<string>
#include<cstring>
using namespace std;

template<typename T>
struct ListNode
{
	T data;
	ListNode* next;
	ListNode(T  d) :data(d), next(NULL) {};
};
template<typename T>
struct treeNode
{
	T data;
	ListNode<treeNode<T>*>* Childenhead;//链表头 listnode里面是一个指针类型关于树结点的指针类型，用来指向多个结点
	treeNode()
	{
		Childenhead = NULL;
	}
	void AddChild(treeNode<T>* node)//传入树结点类型的结点
	{
		ListNode<treeNode<T>*>* childnode = new ListNode<treeNode<T>*>(node);//创建一个ListNode类似的孩子结点
		if (Childenhead == NULL)//头插法把所有的子结点连接起来 孩子链表  就是listnode储存了所有节点并连接了起来 要遍历是通过listnode 访问单个可以用treenode
		{
			Childenhead = childnode;
		}
		else {
			childnode->next = Childenhead;
			Childenhead = childnode;
		}
	}
};
		template<typename T>
		class Tree
		{
		private:
			treeNode<T>* nodes;//子节点
			treeNode<T>* root;//根节点
		public:
			Tree();
			Tree(int maxNodes);
			~Tree();
			treeNode<T>* GetTreeNode(int id);
			void SetRoot(int rootId);
			void AddChild(int parentId, int sonId);
			void AssignData(int id, T data);
			void Print(treeNode<T>* node= NULL);
		};
		template<typename T>
		Tree<T>::Tree()
		{
			nodes = new treeNode<T>[100001];//申请子结点个数
		}
		template<typename T>
		Tree<T>::Tree(int maxNode)
		{
			nodes = new treeNode<T>[maxNode];
		}
		
		template<typename T>
		Tree<T>::~Tree()
		{
			delete[] nodes;
		}
		template<typename T>
		treeNode<T>* Tree<T>:: GetTreeNode(int id)
		{
			return &nodes[id];//不加&取到的是结点对象,加了&后拿到的是唯一标识为这个id的这个对象的地址
		}
		template<typename T>
		void Tree<T>::SetRoot(int rootId)
		{
			root = GetTreeNode(rootId);

		}
		template<typename T>
		void Tree<T>::AddChild(int parentId, int sonId)
		{
			treeNode<T>* parentNode = GetTreeNode(parentId);
			treeNode<T>* sonNode = GetTreeNode(sonId);
			parentNode->AddChild(sonNode);

		}
		
		template<typename T>
		void Tree<T>::AssignData(int id, T data)
		{
			GetTreeNode(id)->data = data;

		}
		template<typename T>
		void Tree<T>::Print(treeNode<T>* node)
		{
			if (node == NULL)
			{
				node=root;
			}
			cout << node->data;
			ListNode<treeNode<T>*>* tmp = node->Childenhead;//
			while (tmp)
			{
				Print(tmp->data);//对于当前结点node我访问他的所有孩子节点。
				tmp = tmp->next;
			}

		}
		int main()
		{
			Tree<char>T(9);
			T.SetRoot(0);
			T.AssignData(0, 'a');
			T.AssignData(1, 'b');
			T.AssignData(2, 'c');
			T.AssignData(3, 'd');
			T.AssignData(4, 'e');
			T.AssignData(5, 'f');
			T.AssignData(6, 'g');
			T.AssignData(7, 'h');
			T.AssignData(8, 'i');
			T.AddChild(0,2);
			T.AddChild(0,1);
			T.AddChild(1,3);
			T.AddChild(3,6);
			T.AddChild(3,7);
			T.AddChild(2,4);
			T.AddChild(2,5);
			T.AddChild(3,8);
			T.Print(0);
			return 0;
		}

AI Agent技术社区

Agent 垂直技术社区，欢迎活跃、内容共建。

更多推荐

SeedVR2终极指南：如何用单步扩散模型实现专业级视频修复

还在为老旧视频的模糊画质而烦恼吗？面对抖动严重的监控录像或褪色的家庭影像，你是否曾希望有一种简单高效的修复方案？SeedVR2正是为解决这些痛点而生的一站式视频修复工具。作为字节跳动推出的先进视频修复模型，它能够在单步推理中实现专业级的视频质量提升，彻底改变了传统视频修复的工作流程。## 核心价值：为什么选择SeedVR2进行视频修复？**传统视频修复的三大瓶颈**：1. **计算成本高

AI Agent技术社区

深度解析Amlogic S9xxx电视盒子Armbian系统：从闲置设备到Linux服务器的终极实战指南

你是否拥有一台闲置的Amlogic S9xxx系列电视盒子？想让它摆脱单一的视频播放功能，变身为功能强大的Linux服务器、开发平台或家庭媒体中心？本指南将为你详细解析如何通过Armbian系统实现这一转变，让你的电视盒子重获新生，成为高性能的Linux设备。Armbian系统基于Debian/Ubuntu构建，专为ARM芯片优化，提供了完整的Linux生态支持。## 🎯 核心价值与独特优势

AI Agent技术社区

CANN/runtime Event管理API

本章节描述 CANN Runtime 的 Event 管理接口，用于事件的创建、记录、同步、计时及 IPC 跨进程共享。- [`aclError aclrtCreateEvent(aclrtEvent *event)`](#aclrtCreateEvent)：创建Event，创建出来的Event可用于统计两个Event之间的耗时、多Stream之间的任务同步等场景。- [`aclError