作者：解学武

前面讲解了存储普通树的双亲表示法和孩子表示法，本节来讲解最后一种常用方法——孩子兄弟表示法。
在树结构中，同一层的节点互为兄弟节点。例如图 1 的普通树中，节点 A、B 和 C 互为兄弟节点，而节点  D、E 和 F 也互为兄弟节点。

所谓孩子兄弟表示法，指的是用将整棵树用二叉链表存储起来，具体实现方案是：从树的根节点开始，依次存储各个结点的孩子结点和兄弟结点。

在二叉链表中，各个结点包含三部分内容（如图 2 所示）：

1. 节点的值；
2. 指向孩子结点的指针；
3. 指向兄弟结点的指针；

用 C 语言代码表示结点结构为：

#define ElemType char
typedef struct CSNode{
    ElemType data;
    struct CSNode * firstchild,*nextsibling;
}CSNode,*CSTree;

以图 1 为例，使用孩子兄弟表示法进行存储的结果如图 3 所示：
由图 3 可以看到，节点 R 无兄弟节点，其孩子节点是 A；节点 A 的兄弟节点分别是 B 和 C，其孩子节点为 D，依次类推。

在以孩子兄弟表示法构建的二叉链表中，如果要查找结点 x 的所有孩子，则只要根据该结点的 firstchild 指针找到它的第一个孩子，然后沿着孩子结点的 nextsibling 指针不断地找它的兄弟结点，就可以找到结点 x 的所有孩子。

实现图 3 中的 C 语言实现代码也很简单，根据图中链表的结构即可轻松完成链表的创建和使用，因此不再给出具体代码。

观察图 1 和图 3。图 1 为原普通树，图 3 是由图 1 经过孩子兄弟表示法转化而来的一棵树，确切地说图 3 是一棵二叉树。因此可以得出这样一个结论，即通过孩子兄弟表示法，任意一棵普通树都可以相应转化为一棵二叉树，它们是一一对应的。

因此，孩子兄弟表示法可以作为将普通树转化为二叉树的最有效方法，通常又被称为"二叉树表示法"或"二叉链表表示法"。
声明：当前文章为本站“玩转C语言和数据结构”官方原创，由国家机构和地方版权局所签发的权威证书所保护。