python中BFS到DFS八叉树的转换

Question

我正在使用由第三方软件构建的八叉树。这个软件报告了如何以宽度优先的方式遍历树，但是我想以深度优先的方式遍历树。你知道吗

对于我的应用程序（为天体物理学应用程序构建粒子数据网格），我倾向于按照八叉树的“精炼”列表来考虑八叉树，即对于不精炼的单元，我们将有：

False

而对于一个细化成Oct的单细胞，我们将有：

True
False
False
False
False
False
False
False
False

我的目标是将这样一个以广度优先的方式生成的refined列表转换为深度优先的方式（在python中），但不知从何开始。你知道吗

例如，此代码：

def construct_octree(refined=[True]):

    # Loop over subcells
    for subcell in range(8):

        # Insert criterion for whether cell should be sub-divided. Here we
        # just use a random number to demonstrate.
        divide = random.random() < 0.5

        # Append boolean to overall list
        refined.append(divide)

        # If the cell is sub-divided, recursively divide it further
        if divide:
            construct_octree(refined)

    return refined

oct = construct_octree()

将为深度优先遍历创建refined列表。你知道吗

Answer 1

所以你在和hyperion合作？如前所述，树木并不是天生的深度优先或宽度优先。然而，hyperion处理它们的方式实际上是为深度优先遍历设置的。考虑列表格式的八叉树：

refine3 = [True,       # 1
             False,    # 2
             False,    # 3
             True,     # 4
               False,  # 10
               False,  # 11
               False,  # ..
               False,  # ..
               False,  # 14
               False,  # 15
               False,  # 16
               False,  # 17
             False,    # 5
             False,    # 6
             False,    # 7
             True,     # 8
               False,  # 18
               False,  # 19
               False,  # 20
               False,  # ..
               False,  # ..
               False,  # ..
               False,  # ..
               False,  # 25
             False,    # 9
             ]

深度优先遍历是1，2，3，4，10，11，12。。。或图表上的绿线：

为此，您只需：

for node in refine3:
    print(node)

宽度优先（橙色线）也可以做到，但会更复杂。你知道吗