树的存储表示法是数据结构中处理树形结构的基础，针对不同的操作需求，设计了多种存储方式以提高效率。以下是三种主要的树的存储表示法及其特点：
双亲表示法
- 每个节点包含两部分：数据域和一个指向其双亲节点在数组中索引的指针（通常用整型表示）。
- 根节点的双亲索引设为 -1，表示无双亲。
- 存储结构为顺序结构（数组），适合查找父节点，时间复杂度为 O(1)；但查找子节点需遍历整个数组，效率较低。
- 示例代码结构（C语言风格）：
typedefstruct{ElementType data;intparent;// 双亲节点的下标}PTNode;
孩子表示法
- 每个节点的数据与一个单链表关联，链表中存储该节点的所有孩子节点的索引或指针。
- 所有节点组成一个数组，每个数组元素指向其孩子的链表头。
- 查找子节点高效，但查找双亲需要遍历所有链表。
- 改进形式为“双亲孩子表示法”：在孩子链表的基础上，每个节点额外记录双亲索引，兼顾双向查找。
孩子兄弟表示法（二叉链表表示法）
- 每个节点包含三个部分：数据域、指向“第一个孩子”的指针、指向“下一个兄弟”的指针。
- 结构上等价于二叉树（左子树为第一个孩子，右子树为下一个兄弟），因此可以将任意树或森林转换为二叉树进行处理。
- 特别适用于实现树与二叉树之间的相互转换，便于复用二叉树的遍历、插入、删除等算法。
- 示例结构定义：
typedefstructCSNode{ElementType data;structCSNode*firstChild;structCSNode*nextSibling;}CSNode,*CSTree;
这三种表示法各有优劣，选择依据具体应用场景：
- 若频繁查询父节点 → 选用双亲表示法；
- 若频繁访问子节点 → 选用孩子表示法；
- 若需统一处理森林或利用二叉树算法 → 选用孩子兄弟表示法。
在双亲表示法中，由于每个节点都存储了其双亲节点在数组中的索引，因此可以通过迭代或递归地向上追溯父节点，直到根节点（其双亲索引为 -1），从而获取该节点的所有祖先节点。
实现思路：
从目标节点开始，利用其parent索引找到双亲，再根据双亲的parent找到上一级祖先，依次类推，直至到达根节点。将路径上的所有节点数据记录下来，即为该节点的祖先序列（不包括自身）。
示例代码（C语言风格）
#include<stdio.h>#defineMAX_TREE_SIZE100typedefcharElementType;typedefstruct{ElementType data;intparent;// 双亲节点的下标}PTNode;// 假设树的节点存储在一个数组中PTNode nodes[MAX_TREE_SIZE];intnodeCount;// 节点总数// 查找并打印某节点的所有祖先节点（非递归方式）voidFindAncestors(intindex){if(index==-1||index>=nodeCount)return;printf("Ancestors of %c: ",nodes[index].data);while(nodes[index].parent!=-1){index=nodes[index].parent;printf("%c ",nodes[index].data);}printf("\n");}示例说明：
假设有一棵树如下：
A / \ B C /|\ D E F用双亲表示法存储的数组可能为：
| 下标 | 数据 | 双亲索引 |
|---|---|---|
| 0 | A | -1 |
| 1 | B | 0 |
| 2 | C | 0 |
| 3 | D | 1 |
| 4 | E | 1 |
| 5 | F | 1 |
若查找节点 D（下标3）的祖先：
- 下标3 → parent = 1 → 节点B
- 下标1 → parent = 0 → 节点A
- 下标0 → parent = -1 → 结束
输出祖先：B, A（顺序为从父到根）
注：若需按“从根到父”的顺序输出，可使用栈暂存结果后再弹出。
时间复杂度分析：
- 最坏情况为树退化成链表（如单支树），时间复杂度为 O(h)，其中 h 是树的高度。
- 空间复杂度为 O(1)（不考虑输出存储）。
总结：
双亲表示法非常适合查找祖先路径，实现简单高效，是实现并查集、目录结构回溯等算法的基础。
k7p9r)
