什么是树的左孩子，右兄弟表示？ 为什么要使用它？(What is the left-child,

使用表示很多数据结构店多路树木二叉树称为“左孩子，右兄弟”表示。 这是什么意思？ 为什么要使用它？

Answer 1:

左孩子，右兄弟表示（LCRS）是编码的方式多路树使用（一个树结构，其中每个节点可以具有任意数量的子） 的二进制树 （树结构，其中每个节点可以最多有两个孩子）。

动机

为了激励这种表示是如何工作的，让我们开始考虑一个简单的多路树，像这样的位置：

                   A
                 //|\ \
               / / | \  \
              B C  D  E  F
              |   /|\   / \
              G  H I J K   L

（道歉低质量的ASCII艺术作品！）

在这个树状结构，我们可以从树中的任何其子女的任何节点向下导航。 例如，我们可以从A迁移到B，A至C，A至d等

如果我们想代表在这样一个树中的节点，我们通常会使用某种像这样一个在这里（用C ++编写）节点结构/节点类：

struct Node {
    DataType value;
    std::vector<Node*> children;
};

在LCRS表示，我们代表的方式树多路，其中每个节点最多需要两个指针。 要做到这一点，我们将稍微重塑树。 而不是在树中存储指向所有儿童的每一个节点，我们将通过使每个节点存储指针结构的方式略有不同树的孩子只有一个（在LCRS，最左边的孩子）。 然后，我们将每个节点存放指向其右兄弟，在树中同一父节点的子下一个节点。 在上面的树的情况下，我们可能代表通过以下方式树：

            A
           /
          /
         /
        B -> C -> D -> E -> F
       /         /         /
      G         H->I->J   K->L

注意，在这个新的结构，仍然可以从它的第k子父节点导航（零索引）。 这样做的过程如下：

• 下降到当前节点的左子。 （这是它的孩子列表中的第一个节点）。
• 按照那个孩子的右兄弟指针k次。 （这需要你到节点的第k个孩子）。
• 返回该节点。

例如，要查找根节点A的第三个（零索引的孩子），我们会沦落到最左边的孩子（B），然后遵循三个右连杆（访问B，C，d，最后E）。 然后，我们在节点E，持有节点A的第三个孩子到达

为表示树这种方式的主要原因是，即使任何节点都可以有任意数量的儿童，表示需要对每个节点最多两个指针：一个节点存储最左边的孩子，和一个指针来保存右兄弟。 因此，我们可以用一个更简单的节点结构存储多路树：

struct Node {
    DataType data;
    Node* leftChild;
    Node* rightSibling;
};

此节点结构具有恰好在二叉树（数据加上两个指针）的节点的相同的形状。 其结果是，该LCRS表示使得有可能使用表示每个节点仅仅两个指针的任意多路树。

分析

现在让我们看看多路树的两个不同的陈述和它的一些基本操作的时间和空间复杂度。

让我们先来看看为代表最初的“孩子们的动态数组”所需的总空间使用情况。 会有多少总内存使用量是一个正节点树？ 好吧，我们知道以下内容：

1. 每个节点上，而不管其数儿童的，对于（的sizeof（数据））存储的原始数据和动态阵列的空间开销有助于空间。 动态阵列（通常）具有存储的一个指针（其指向在所分配的阵列），用于元件的动态阵列中的总数一个机器字，和（任选地）一个机器字的阵列的所分配的容量。 这意味着，每个节点占用的sizeof（数据）+的sizeof（节点*）+ 2 *的sizeof（机器字）的空间。

2. 在所有树的动态数组，会有N - 1指针孩子，因为在树中的n个节点的N - 1人有父母。 *的sizeof（节点*）因素 - 在一个额外的（1 N）补充道。

因此，总的占用空间

N·（的sizeof（数据）+的sizeof（节点*）+ 2 *的sizeof（机器字））+（N - 1）*的sizeof（节点*）

= N *的sizeof（数据）+（2N - 1）*的sizeof（节点*）+ 2N *的sizeof（机字）

现在，让我们对比一下与LCRS树。 在LCRS每个节点树存储两个指针（2 *的sizeof（节点*））和一个数据元素（的sizeof（数据）），所以它的总空间是

N *的sizeof（数据）+ 2N *的sizeof（节点*）

在这里，我们看到了胜利：请注意，我们不是存储2n个*的sizeof（机器字）额外的内存来跟踪分配的数组的大小。 这意味着，LCRS表示采用比常规多路树内存相当少。

然而，在LCRS树结构的基本操作往往比正常的多路树及其相应的操作需要更长的时间。 具体而言，在标准形式（每个节点存储子指针数组）表示的多路树，所需要的时间从一个节点到它的第k子导航通过遵循单个指针所需的时间给出。 在另一方面，在LCRS表示，这样做所需的时间是由遵循K + 1点的指针（一个左子指针，则K右孩子指针）所需要的时间给出。 其结果是，如果树有一个大的分支因子，它可以慢得多做查找在LCRS树状结构比相应的多路树结构。

因此，我们可以认为，LCRS表示作为提供时间和空间的折衷数据结构存储空间和存取时间之间。 的LCR表示有内存开销比原来的多路树少，而多路树给每个孩子它的恒定时间的查找。

用例

因为所涉及的LCRS表示时间空间折衷中，LCRS表示通常不使用，除非两个标准中的一个成立：

1. 内存是极为稀缺的，或
2. 不需要节点的子节点的随机访问。

如果你需要存储在主内存中的惊人巨大的多路树案例（1）可能出现。 例如，如果你需要存储系统进化树包含受频繁更新许多不同的物种，那么LCRS表示可能是适当的。

情况（2）出现在其中的树结构以特定的方式被使用专门的数据结构。 例如，许多类型的堆的数据结构使用多路树木可以空间通过使用LCRS表示优化。 造成这种情况的主要原因是，在堆数据结构中，最常见的操作往往是

1. 删除树的根和处理它的每一个孩子，或
2. 通过使一棵树其他的孩子加入两棵树在一起。

操作（1）可以在LCRS表示非常有效地进行。 在一个LCRS表示中，树的根永远具有右子（因为它没有兄弟姐妹），因此移除所述根只是意味着剥离根节点和下降到它的左子树。 从那里，处理每个孩子可以通过简单地走在剩余树的右侧脊椎和处理依次在每个节点来完成。

操作（2）可以非常有效地进行为好。 从以上召回在LCRS表示，一棵树的根永远不会有一个正确的孩子。 因此，很容易两棵树联合起来在LCRS表示如下。 有两棵树像这样开头：

    R1             R2
   /               /
 (children 1)    (children 2)

我们可以用这种方式融合在一起的树木：

             R1
            /
           R2
          /  \
(children 2) (children 1)

这可以在O完成（1）时间，是很简单的。 该LCRS表示具有该属性的事实意味着许多类型的堆优先级队列的，如二项堆或秩配对堆通常表示为LCRS树。

希望这可以帮助！

文章来源: What is the left-child, right-sibling representation of a tree? Why would you use it?