将m元树转换成n元树

Question

• 给定一棵树的根。树可以是任何深度和宽度，
  • 即每个节点可以有任意数量的子节点。
  • 此方法应该以这样一种方式转换树，即每个节点（可能只有一个除外）都有N个或0个子节点（并且一个节点可能有多个介于0和N之间的子节点）。
  • 算法可以以任何方式转换给定的树，但只有一个条件：如果节点A是源树中节点B的优势节点B可能不是结果树中节点A的优势节点（尽管它们可能成为兄弟姐妹）。

  
  interface CompactTreeBuilder<T> {
      /**
       *
       * E.g.
       *
       * source:        compact(A, 2)     compact(A, 1)             compact(A, 100)
       *
       * A               A                 A                         A
       *  |               |                 |_B                       |_B
       *  |_B             |_B                  |_C                    |
       *     |            |  |                    |_D                 |_C
       *     |            |  |_D                     |_E              |
       *     |            |  |                          |_F           |_D
       *     |_C          |  |_E                           |_G        |
       *     | |_D        |    |_H                            |_H     |_E
       *     |    |_F     |                                           |
       *     |            |_C                                         |_F
       *     |_E            |                                         |
       *       |_G          |_F                                       |_G
       *       |            |                                         |
       *       |_H          |_G                                       |_H
       *
       *
       *  in an example for compact(A,2) above node E is an exception node:
       *  it has 1 child while any other node has either 2 or 0 children
       */
      Node<T> compact(Node<T> root, int N);
      }
   
      class Node<T> {
      private final T data;
   
      private final List<Node<T>> children;
   
      public Node(T data, List<Node<T>> children) {
          this.data = data;
          this.children = children;
      }
   
      public T getData() {
          return data;
      }
   
      public List<Node<T>> getChildren() {
          return children;
      }
  }
  
  

Answer 1

一个简单的算法是：

以广度优先的顺序遍历输入树。将每个被访问的节点添加到新树中，也是以广度优先的顺序，确保将子节点添加到还没有N个子节点的节点中，并且当没有少于N个子节点的内部节点时，仅将第一个子节点添加到下一个叶子中(以广度优先的顺序)。

这将确保：

• 目标树中永远不会有两个节点的子节点少于N个
• 节点只能成为后来添加的节点的父节点。由于我们以广度优先顺序遍历输入树，这保证了节点永远不会成为其任何原始祖先的祖先