c++ - 将多路树转换为左子/右兄弟格式？

Question

我正在尝试编写 C++ 代码，给定一个多路树，将该树转换为以left-child/right-sibling format表示的二叉树。例如，给定这棵树：

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

我想输出这棵树：

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

我不确定如何解决这个问题。我应该如何考虑这样做？

标签： c++data-structurestreebinary-tree

Answer 1

有一个很好的递归洞察力可以用来解决这个问题。我将让您详细了解如何在代码中实际实现这一点，因为我不知道您是如何表示树的，但这是核心思想。

首先，将空树转换为 LC/RS 格式非常容易：它以空树的形式返回。

另一方面，假设您有一棵非空树。首先将其每个子项转换为 LC/RS 格式（递归）。例如，给定这棵树：

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

您将从递归地将每个孩子转换为 LC/RS 开始，返回这三棵树：

   B        C         D
  /                  /
 E                  H
  \
   F
  / \
 I   G
  \
   J

这些树目前是自由浮动的，并且没有相互连接。但是既然你知道他们是兄弟姐妹，你就会想让 C 成为 B 的右孩子，让 D 成为 C 的右孩子。这本质上是一个链表遍历。以下是完成后的样子：

         B
       /   \
      E     C
       \     \
        F     D
       / \   /
      I   G H
       \
        J

完成后，剩下要做的就是让 B 成为 A 的左孩子，如下所示：

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

回顾一下，逻辑是这样的：

• 如果要转换的树为空，则返回一棵空树。
• 否则：
  • 递归地将根节点的每个子节点转换为 LC/RS 格式。
  • 遍历这些树，分配右子链接以将树链接在一起。
  • 分配 A 的左子指针指向结果树（如果它没有子节点，则为 null）。

我将把 C++ 的详细信息留给您填写。如果您尝试解决此问题但遇到了麻烦，请随时发布后续问题，详细说明您迄今为止编写的代码使用失败的特定测试用例或遇到的特定编译器错误。祝你好运！