有没有办法从DFS输出到BFS输出？

Question

我一直在努力解决以下问题：我有一个DFS输出列表： [0.2500000074505806， 0.65000059604645， 0.15000000223517418， 0.450000298023224， 0.450000298023224， 0.849999940395355， 0.1500002223517418] 并希望将其转换为BFS订购，而无需先创建树，然后再应用BFS。作为参考，这是一个完整的二进制图，带有深度2。

感谢提前的帮助。

Answer 1

对于一般图，DFS不包含足够的信息来获得BFS输出。但是，如果您确定该图是7个节点上的完整二进制树，并且您可以从根而来dfs，输出为x1，x2，x3，…，x7，那么bfs输出将为x1，x2，x5，x3，x3 ，x4，x6，x7。

更一般而言，如果您在n个节点上具有完整的二进制树的DFS输出，则可以通过以下算法生成BFS输出的置换：

k = 3   # number of levels in complete binary tree
n = 2**k   #so node labels are 1,2,...,n-1
L = list(range(1, n))

def toBFS(L):
    #input: a sequence of node labels, obtained by DFS on a complete binary tree
    #output: the sequence of node labels if BFS was performed
    #Q = a queue of all sublists to be processed
    #each sublist q has length 2^k-2
    #process each sublist by printing 1st, and n/2th element
    #and partitioning into two subsublists, both added to queue
    print(L[0])
    Q = []
    Q.append(L[1:len(L)])
    while len(Q) > 0:
        q = Q.pop(0)    #removes first element of Q
        if len(q) <= 2:
            for x in q:
                print(x)
        else:
            print(q[0])
            n = len(q)
            print(q[n//2])
            Q.append(q[1:n//2])
            Q.append(q[n//2+1:n])
        
toBFS(L)

输出：输出：

1
2
5
3
4
6
7

该算法将DFS序列作为输入，并打印出根节点，即根节点，，并将其打印出根节点，即然后对FIFO队列中的每个sublist进行以下操作：打印左子女，然后将约一半的元素作为sublist添加到队列中，然后打印正确的孩子，然后将大约一半的元素添加为sublist 。

Answer 2

当树被保证为完美的二进制树树全部都在底层，然后您可以使用务实的方法在其中填充级别顺序遍历的级别作为单独的列表，然后返回这些值的串联：

def preorder_to_levelorder(seq):
    height = int(len(seq) ** 0.5)
    levels = [[] for _ in range(height+1)]
    it = iter(seq)
    
    def recur(depth):
        if depth > height:
            return
        try:
            val = next(it)
        except:
            return
        levels[depth].append(val)
        recur(depth + 1)
        recur(depth + 1)

    recur(0)
    return [val for level in levels for val in level]

示例完美树：

        4
      /   \
     2     6
    / \   / \
   1   3 5   7

示例为该树运行：

preorder = [4, 2, 1, 3, 6, 5, 7]
print(preorder_to_levelorder(preorder))  # [4, 2, 6, 1, 3, 5, 7]