left-child right-sibling representation of tree - 左孩子右兄弟表示树

小咪咪 2023-01-03 11:30 115阅读 0赞

# **left-child right-sibling representation of tree - 左孩子右兄弟表示树** #

child-sibling representation, left-child, right-sibling binary tree, doubly chained tree or filial-heir chain.

binary tree：二叉树
    left-child right-sibling，LCRS：左孩子右兄弟
    sibling ['sɪblɪŋ]：n. 兄，弟，姐，妹
    filial ['fɪliəl]：adj. 子女 (对父母) 的
    heir [eə(r)]：n. 继承人，后嗣，传人
    multi-way tree - k-ary tree

## 1. LC-RS binary tree ##

In a binary tree that represents a multi-way tree  T T T, each node corresponds to a node in  T T T and has two pointers: one to the node’s first child, and one to its next sibling in  T T T. The children of a node thus form a singly-linked list.  
在表示多路树  T T T 的二叉树中，每个节点对应于  T T T 中的一个节点，并且具有两个指针：一个指向节点的第一个子节点，另一个指向在  T T T 中的下一个子节点。因此，节点的子级形成一个单链表。

The process of converting from a k-ary tree to an LC-RS binary tree is sometimes called the `Knuth transform`. To form a binary tree from an arbitrary k-ary tree by this method, the root of the original tree is made the root of the binary tree. Then, starting with the root, each node’s leftmost child in the original tree is made its left child in the binary tree, and its nearest sibling to the right in the original tree is made its right child in the binary tree.  
从 `k-ary` 树转换为 `LC-RS` 二叉树的过程有时称为 `Knuth transform`。为了通过这种方法从任意的 `k-ary` 树形成二叉树，将原始树的根设为二叉树的根。

Processing a k-ary tree to LC-RS binary tree, every node is linked and aligned with the left child, and the next nearest is a sibling.  
将 `k-ary` 树处理为 `LC-RS` 二叉树，每个节点都与左子节点链接并对齐，下一个最近的节点是同级节点。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center]

a ternary tree

1
                     /|\
                    / | \
                   /  |  \
                  2   3   4
                 / \      |
                5   6     7
                         / \
                        8   9

We can re-write it by putting the left child node to one level below its parents and by putting the sibling next to the child at the same level – it will be linear (same line).  
我们可以通过以下方式重新编写它：将左侧的子节点放置在其父节点以下一级，并在同一级别将子节点旁边的同级节点放置为线性 (同一行)。

1
                     /
                    /
                   /
                  2---3---4
                 /       /
                5---6   7
                       /
                      8---9

The LCRS representation is more space-efficient than a traditional multiway tree, but comes at the cost that looking up a node’s children by index becomes slower. Therefore, the LCRS representation is preferable if  
LCRS 表示比传统的多路树更节省空间，但代价是按索引查找节点的子代变慢。因此，如果满足以下条件，则最好使用 LCRS 表示形式

1.  Memory efficiency is a concern. (内存效率。)
2.  Random access of a node’s children is not required. (不需要节点的子级的随机访问。)

Case (1) applies when large multi-way trees are necessary, especially when the trees contains a large set of data. For example, if storing a phylogenetic tree, the LCRS representation might be suitable.  
情况 (1) 适用于需要大型多路树的情况，尤其是当树包含大量数据时。 例如，如果存储系统树，则 LCRS 表示可能是合适的。

Case (2) arises in specialized data structures in which the tree structure is being used in very specific ways. For example, many types of heap data structures that use multi-way trees can be space optimized by using the LCRS representation.  
情况 (2) 出现在特殊的数据结构中，其中以非常特定的方式使用树结构。例如，可以使用 LCRS 表示对使用多路树的许多类型的堆数据结构进行空间优化。

## 2. trie ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 1]

A trie implemented as a doubly chained tree: vertical arrows are child pointers, dashed horizontal arrows are next-sibling pointers.  
一个实现为双链树的 trie：垂直箭头是子指针，虚线水平箭头是下一个兄弟指针。

## References ##

[https://www.geeksforgeeks.org/left-child-right-sibling-representation-tree/][https_www.geeksforgeeks.org_left-child-right-sibling-representation-tree]  
[https://www.geeksforgeeks.org/creating-tree-left-child-right-sibling-representation/][https_www.geeksforgeeks.org_creating-tree-left-child-right-sibling-representation]  
[https://en.wikipedia.org/wiki/Left-child\_right-sibling\_binary\_tree][https_en.wikipedia.org_wiki_Left-child_right-sibling_binary_tree]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221119/ad590004434d4d0e84afdeba565a8390.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221119/290433ea380e4e1ca8d057b0d88a39a4.png
[https_www.geeksforgeeks.org_left-child-right-sibling-representation-tree]: https://www.geeksforgeeks.org/left-child-right-sibling-representation-tree/
[https_www.geeksforgeeks.org_creating-tree-left-child-right-sibling-representation]: https://www.geeksforgeeks.org/creating-tree-left-child-right-sibling-representation/
[https_en.wikipedia.org_wiki_Left-child_right-sibling_binary_tree]: https://en.wikipedia.org/wiki/Left-child_right-sibling_binary_tree