树的孩子表示法，双亲表示法，孩子双亲表示法

### 树结构的不同表示方法

#### 孩子表示法

孩子表示法通过链表来保存节点的孩子列表。每个节点包含两部分：数据域和指向其第一个孩子的指针。对于每一个孩子，同样记录下它的下一个兄弟的位置。

优点在于容易找到某个节点的所有直系后代；缺点则是难以快速定位到父节点位置，并且当树较为稀疏时会浪费较多空间用于存储空闲链接[^1]。

typedef struct CTNode {
    int child;           /* 当前孩子在数组中的位置 */
    struct CTNode *next; /* 指向下一 sibling 的指针 */
} CTNode;

typedef struct TreeNode {
    ElemType data;
    CTNode *firstchild; /* 指向该结点的第一个儿子的头指针 */
} TreeNode, CsTree;

#### 双亲表示法

双亲表示法则是在顺序存储的基础上增加了一个指示器用来指出当前节点的父亲所在的位置。这种方式使得查找某节点的祖先变得非常简单快捷，但是要访问一个节点的孩子则相对复杂一些[^2]。

#define MAX_TREE_SIZE 100 // 定义最大可能的节点数

typedef struct PTNode {
    TElemType data;
    int parent;          // 记录此节点父亲所在的下标
} PTNode;

typedef struct {
    PTNode nodes[MAX_TREE_SIZE];
    int n;               // 结点数目
} PTree;

#### 孩子兄弟表示法

这种方法利用两个指针分别代表最左侧的孩子（即长子）以及右侧相邻的一个弟弟（右邻）。它能够很好地模拟自然界的家族关系，在遍历整棵树的时候效率较高。不过这种表达形式可能会让某些操作变得更加困难，比如计算特定层次上的所有成员数量等。

typedef struct CSNode {
    TElemType data;
    struct CSNode *firstchild, *nextsibling;
} CSNode, CSTree;

每种表示都有各自的特点：

- **孩子表示法**适合于频繁查询某一节点下的全部子女情况的应用场景；
- **双亲表示法**适用于经常需要追溯至根路径或是处理有关辈分问题的情形；
- **孩子兄弟表示法**可以简化二叉树和其他多分支树形结构间的相互转化过程，同时也便于执行先序、中序或后序遍历算法。