【数据结构】孩子兄弟与二叉链表的本质统一

孩子兄弟表示法和二叉链表表示法在数据结构定义和物理存储上完全一样它们是同一事物的两种不同名称只是强调了不同的视角和应用场景。核心等价性它们都使用以下相同的节点结构以C语言为例typedef struct Node { ElemType data; // 数据域 struct Node *firstChild; // 指向第一个孩子 struct Node *nextSibling; // 指向下一个兄弟 } Node, *Tree;这个结构就是标准的二叉链表——每个节点包含两个指针域。两者的区别仅在于概念解释和用途视角/名称强调的重点主要应用场景孩子兄弟表示法树的逻辑关系用“第一个孩子”和“下一个兄弟”这两个指针来表示一棵普通树的结构。存储和操作普通树多叉树。二叉链表表示法二叉树的物理存储用“左指针”和“右指针”这两个指针来存储一棵二叉树。存储和操作二叉树。为什么说它们“一样”这源于一个经典的转换法则任何一棵普通树都可以唯一地转换为一棵二叉树转换方法就是著名的“左孩子右兄弟”法则左指针firstChild指向节点的第一个孩子。右指针nextSibling指向节点的下一个兄弟。这个转换过程是双向的、唯一的。当你用“第一个孩子”和“下一个兄弟”的视角去解释这棵二叉链表存储的二叉树时你看到的就是原来的那棵普通树。这就是孩子兄弟表示法。当你直接用“左孩子”和“右兄弟”的视角去看待这棵二叉链表时它本身就是一棵二叉树。这就是二叉链表表示法。举例说明对于下面这棵普通树A / | \ B C D / \ \ E F G应用“左孩子右兄弟”法则转换后得到的二叉树用二叉链表存储如下A / B / \ E C \ \ F D / G从孩子兄弟视角看解释二叉链表节点A的firstChild指向B第一个孩子nextSibling为NULL根无兄弟。节点B的firstChild指向E第一个孩子nextSibling指向C下一个兄弟。从二叉树视角看直接操作二叉链表节点A的left指针指向B左孩子right指针为NULL。节点B的left指针指向E左孩子right指针指向C右孩子。存储的物理结构内存中的二进制位完全相同只是我们赋予这两个指针的名称和语义不同。关键结论物理存储一致在内存中用于实现“孩子兄弟表示法”的节点结构与用于实现“二叉链表表示法”的节点结构其内存布局完全相同一个数据域两个指针域。逻辑映射唯一“左孩子右兄弟”法则建立了普通树与二叉树之间的一一对应关系。因此用二叉链表存储的这棵二叉树唯一地对应一棵用孩子兄弟法表示的普通树。操作算法相通在这两种表示法上进行的许多算法如先序遍历在代码实现上几乎一致只是遍历时的递归调用所代表的“语义”不同一个是遍历孩子/兄弟一个是遍历左/右子树。简单来说你可以把孩子兄弟表示法理解为使用二叉链表这种物理结构来存储一棵普通树的具体方法。当你说“二叉链表表示法”时你强调的是这个底层存储容器当你说“孩子兄弟表示法”时你强调的是用这个容器来装普通树时所遵循的装填规则左孩子右兄弟。