我一直在努力與下面的問題：我有一個DFS輸出串列：0.2500000074505806，0.6500000059604645，0.15000000223517418，0.45000000298023224，0.45000000298023224，0.8499999940395355，0.15000000223517418]，但想不先創建一棵樹，然后應用BFS這種轉變為BFS順序。作為參考，這是一個深度為 2 的完全二元圖。
在此先感謝您的幫助。
uj5u.com熱心網友回復：
對于一般圖，DFS 不包含足夠的資訊來獲取 BFS 輸出。但是，如果您確定該圖是 7 個節點上的完整二叉樹，并且您從根運行 DFS 并且輸出為 x1,x2,x3,...,x7，那么 BFS 輸出將為 x1,x2,x5,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 佇列中的每個子串列執行以下操作：列印左孩子，然后將大約一半的元素作為子串列添加到佇列中，然后列印右child，然后將大約一半的元素作為子串列添加到佇列中。
uj5u.com熱心網友回復：
當樹被保證是一個完美的二叉樹時，即樹的葉子都在底層，那么你可以使用一種實用的方法，將級別順序遍歷的級別填充為單獨的串列，然后回傳這些值的串聯：
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]
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/466088.html
下一篇：想要獲取值匹配的其他串列的值