找到n-ary树的所有子树

Question

我试图找到n-ary树的所有子树.只有BFS或DFS不起作用.因为树不是二进制的.例如:

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

我想显示包括这一个在内的所有子树

        1
     /    \
    2      3
     \     |
      6    7

如何从原始子树中提取该子树？

Answer 1

您可以执行以下操作。

• 对于树中的每个顶点，您决定是切割以顶点为根的子树还是继续探索。您的选择数量约为 2^（节点数量）。请注意，它恰好是 2^（节点数）（它更少，但仍然是指数），因为在切割子树之后，您不会探索它。
• 对于每个顶点的每个选择配置，使用 打印树DFS。

您的示例是其中具有根4, 5,的子树8 被剪切的配置。

可以通过为每个节点设置标志来隐式完成切割。