如何根据深度将树分割为分支

Question

我不确定这是否是一个难题，或者我对 DSA 太生疏了，但我找不到一种方法来编写一个函数来根据任意深度值将树拆分为多个分支.

我的意思是：我想编写一个函数

split_tree

，它至少接收参数：

tree

和

level

，后者是树中的深度级别。该函数应该探索树，直到达到确定的级别，然后返回该分支的副本，并修剪所有不相关的节点。重复此操作，直到同一级别的所有节点都完成。

考虑下图中的树。

level

确定哪些节点是分裂分支的基节点（或相关节点）。考虑 ROOT 节点为 0，如果

level=1

基节点为 B、C 和 D，如果

level=2

基节点将为 E、F、C、H 和 I。

因此，调用

split_tree(tree, level=1)

将返回三个不同的分支：

[ROOT, B, [E, F]]
[ROOT, C]
[ROOT, D, [H, I, [J, K]]]

调用

split_tree(tree, level=2)

时将返回五个不同的分支：

[ROOT, B, E]
[ROOT, B, F]
[ROOT, C]
[ROOT, D, H]
[ROOT, D, I, [J, K]]

请注意

• 如果分支未达到

  level

  的深度，它将返回尽可能深的分支。例如：[根，C]
• 如果基节点有子节点，则它们包含在分支中。例如：[ROOT, D, I, [J, K]]
• 基本节点的所有兄弟节点和其他不相关的分支都被修剪。

我特别感谢伪代码或Python中的任何帮助，但请随意使用任何东西。

Answer 1

这是 Python 中的实现：

class Node:
    def __init__(self, value, *children):
        self.value = value
        self.children = children

def children_to_nested_list(children):
    for child in children:
        yield child.value
        if child.children:
            yield list(children_to_nested_list(child.children))
 
def split_tree(tree, level):
    if not tree:
        return
    if not tree.children:
        yield [tree.value]
        return
    if level == 0:
        yield [tree.value, list(children_to_nested_list(tree.children))]
        return
    for child in tree.children:
        for path in split_tree(child, level - 1):
            yield [tree.value, *path]    

这是示例树上的运行：

tree = Node("ROOT",    
           Node("B",
               Node("E"),
               Node("F")
           ),
           Node("C"),
           Node("D",
               Node("H"),
               Node("I",
                   Node("J"),
                   Node("K")
               )
           )
       )

print("level 1:")
for branch in split_tree(tree, 1):
    print(branch)
print("level 2:")
for branch in split_tree(tree, 2):
    print(branch)

输出：

level 1:
['ROOT', 'B', ['E', 'F']]
['ROOT', 'C']
['ROOT', 'D', ['H', 'I', ['J', 'K']]]
level 2:
['ROOT', 'B', 'E']
['ROOT', 'B', 'F']
['ROOT', 'C']
['ROOT', 'D', 'H']
['ROOT', 'D', 'I', ['J', 'K']]