C语言实现普通树：孩子兄弟表示法与遍历算法详解
在数据结构中，普通树（非二叉树）因存在“多子节点”特性，无法直接用二叉树的左右子树结构存储。本文将结合两段C语言代码，拆解普通树的孩子兄弟表示法（核心存储方式）、节点创建（健壮性设计）以及前序/后序遍历（核心操作），帮你吃透普通树的基础实现逻辑。
一、核心基础：普通树的“孩子兄弟表示法”
普通树的关键难点是“多子节点”的存储——若为每个节点定义固定数量的子节点指针（如 child1, child2...），会造成内存浪费或无法适配动态子节点数量。而孩子兄弟表示法完美解决了这个问题：将“多子节点”关系拆分为“第一个孩子 + 后续兄弟”，把普通树转化为“等价二叉树”，用两个指针即可覆盖所有节点关系。
代码中对应的节点结构定义如下，这是整个普通树实现的基石：
// 普通树节点结构（孩子兄弟表示法）
typedef struct TNode
{
int data; // 数据域：存储节点值
struct TNode *firstchild; // 指向“第一个子节点”：定位子节点的起点
struct TNode *nextsibling; // 指向“右兄弟节点”：串联同一父节点的其他子节点
} TNode, *Tree;
结构解读：
- 若节点有多个子节点，只需用
firstchild指向“第一个子节点”，再通过第一个子节点的nextsibling，依次串联第二个、第三个...子节点； - 示例树（两段代码共用）的结构用该表示法拆解后更清晰：
1（根） / \ 2 3（2的nextsibling指向3，二者都是1的子节点） / 4（2的firstchild指向4，4无兄弟）
二、基础操作：健壮的节点创建函数
创建节点是树操作的第一步，代码中 CreateTNode函数不仅完成内存分配，还加入了内存分配失败判断——这是工业级代码的必要设计，避免因 malloc返回 NULL导致的野指针问题。
关键代码与解读：
TNode *CreateTNode(int data)
{
// 1. 分配节点内存：sizeof(TNode)确保内存大小匹配
TNode *newNode = (TNode *)malloc(sizeof(TNode));
// 2. 健壮性判断：malloc失败返回NULL，需终止程序避免后续错误
if (newNode == NULL)
{
printf("内存分配失败！\n");
exit(1); // 退出程序，错误码1表示异常
}
// 3. 初始化节点：数据域赋值，指针域置空（避免野指针）
newNode->data = data;
newNode->firstchild = NULL; // 初始无第一个子节点
newNode->nextsibling = NULL; // 初始无右兄弟节点
return newNode;
}
注意点：
- 指针域必须初始化为
NULL：若未置空，firstchild和nextsibling会指向随机内存，后续遍历判断“是否有子节点/兄弟”时会出错； exit(1)的作用：内存分配失败属于严重错误（如堆内存耗尽），继续执行会导致不可控崩溃，直接终止程序更安全。
三、核心算法：前序与后序遍历的实现与差异
遍历是树的核心操作，两段代码分别实现了前序遍历和后序遍历，且基于同一棵示例树——便于对比两种遍历的逻辑差异。
1. 前序遍历：“根 → 子”的顺序
前序遍历的规则是：先访问当前根节点，再依次对每个子节点执行前序遍历（子节点按“第一个孩子→右兄弟”的顺序处理）。
对应代码与执行流程：
void PreOrder(Tree T)
{
if (T == NULL) return; // 递归终止条件：空节点直接返回（避免死循环）
// 1. 第一步：访问当前根节点（前序的核心：“根优先”）
printf("%d ", T->data);
// 2. 第二步：遍历当前节点的所有子节点（按“第一个孩子→右兄弟”顺序）
TNode *p = T->firstchild; // 先拿到第一个子节点
while (p != NULL)
{
PreOrder(p); // 递归：对当前子节点执行前序遍历（子树的根）
p = p->nextsibling; // 切换到下一个兄弟节点，继续遍历
}
}
示例树遍历结果：1 2 4 3执行逻辑拆解：
- 访问根节点1 → 找1的第一个子节点2；
- 访问节点2 → 找2的第一个子节点4；
- 访问节点4 → 4无子女，返回；
- 2无其他兄弟，返回 → 找1的下一个兄弟节点3；
- 访问节点3 → 3无子女，遍历结束。
2. 后序遍历：“子 → 根”的顺序
后序遍历的规则是：先依次对每个子节点执行后序遍历，最后访问当前根节点（与前序遍历的“根优先”相反，是“子优先”）。
对应代码与执行流程：
void PostOrder(Tree T)
{
if (T == NULL) return; // 递归终止条件：空节点直接返回
// 1. 第一步：先遍历当前节点的所有子节点（“子优先”，与前序顺序颠倒）
TNode *p = T->firstchild;
while (p != NULL)
{
PostOrder(p); // 递归：对当前子节点执行后序遍历（先处理子树）
p = p->nextsibling; // 切换到下一个兄弟节点
}
// 2. 第二步：所有子节点处理完后，再访问当前根节点
printf("%d ", T->data);
}
示例树遍历结果：4 2 3 1执行逻辑拆解：
- 处理根节点1的第一个子节点2 → 先处理2的第一个子节点4；
- 4无子女，访问4 → 返回2，2无其他兄弟，访问2；
- 返回1，处理1的下一个兄弟节点3 → 3无子女，访问3；
- 所有子节点处理完，访问根节点1，遍历结束。
3. 前序与后序遍历对比
| 对比维度 | 前序遍历 | 后序遍历 |
|---|---|---|
| 核心顺序 | 根节点 → 子节点 | 子节点 → 根节点 |
| 代码关键差异 | 先执行 printf(T->data) |
后执行 printf(T->data) |
| 示例树结果 | 1 2 4 3 | 4 2 3 1 |
| 适用场景 | 复制树、获取树的结构信息 | 计算子树权重、删除树节点 |
四、总结与扩展
本文通过两段代码，覆盖了普通树的三大核心知识点：
- 孩子兄弟表示法：用“firstchild + nextsibling”将多子树转化为二叉树结构，是普通树存储的标准方案；
- 节点创建健壮性：
malloc后必须判断NULL，指针域初始化为NULL，避免内存错误； - 遍历算法逻辑：前序“根优先”、后序“子优先”，差异仅在于“访问根节点”与“遍历子节点”的顺序。
扩展建议：
- 实际开发中，需补充树的销毁函数（递归释放所有节点，避免内存泄漏）；
- 可尝试实现层序遍历（按节点深度依次访问，需借助队列），进一步完善普通树的操作体系。
需要我帮你补充“树的销毁函数”代码，或详细讲解层序遍历的实现思路吗？
内容由 AI 生成
评论区