树的左儿童右同级表示

Left-Child Right-Sibling Representation是n元树的另一种表示形式，其中一个节点不维护指向每个子节点的指针，而是仅持有两个指针，第一个指针指向其第一个孩子，另一个指向它的下一个兄弟姐妹。这种新的转换不仅消除了对节点具有的子代数目的先验知识的需要，而且还将指针的数目限制为最多两个，从而使编码变得非常简单。

在每个节点上，从左到右链接或连接同一父级的子级。

父母应仅与第一个孩子联系。

例子

左儿童右兄弟树表示

10
|
2 -> 3 -> 4 -> 5
| |
6 7 -> 8 -> 9

好处

• 通过将每个节点所需的最大指针数限制为两个，此表示节省了内存。

• 编码更简单。

缺点

• 诸如搜索/插入/删除之类的基本操作会花费较长的时间，因为要选择确切的位置，我们必须遍历要搜索/插入/删除的节点的所有同级节点（根据最坏的情况）。