我有一個高度為“h”的完整二叉樹。
我如何為此找到“h”個不相關的磁區？
注意：不相關的磁區意味著沒有子級可以與它的直接父級一起存在。
每個磁區中的節點數都有限制。一個磁區中的最大節點數與磁區中的最小節點數之差可以是0，也可以是1。
此外，root 也不包括在磁區中。
uj5u.com熱心網友回復：
設計這個問題的人可能有一個更優雅的解決方案，但以下有效。
假設我們有h編號1為 的磁區h，并且磁區的節點n具有值n。根節點有值0，不參與磁區。即使n是偶數，我們也將其稱為磁區，如果n是奇數，則稱為奇數。讓我們也對完整二叉樹的級別進行編號，忽略根并從12 個節點的級別開始。層n有2 n 個節點，完整的樹有2 h 1 -1 個節點，但只有P=2 h 1 -2 個節點屬于磁區（因為排除了根）。每個磁區由 p=?P/h? 或 p=?P/h? 節點組成，這樣 ∑?p?=P。
如果h樹的高度為偶數，則將所有偶數磁區放入左子樹的偶數層和右子樹的奇數層，將所有奇數磁區放入左子樹的奇數層和右子樹的偶數層子樹。
如果h是奇數，則h-1像偶數情況一樣將所有磁區分配到磁區，但將磁區h均勻地分配到左子樹和右子樹的最后一級。
這是h最多 7 個的結果（為此，我撰寫了一個小型Python 庫，以緊湊的方式將二叉樹列印到終端）：
0
1 1
0
1 2
2 2 1 1
0
1 2
2 2 1 1
1 1 3 3 2 2 3 3
0
1 2
2 2 1 1
1 1 1 1 2 2 2 2
2 4 4 4 4 4 4 4 1 3 3 3 3 3 3 3
0
1 2
2 2 1 1
1 1 1 1 2 2 2 2
2 2 2 2 2 2 4 4 1 1 1 1 1 1 3 3
3 3 3 3 3 3 3 3 3 3 5 5 5 5 5 5 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5
0
1 2
2 2 1 1
1 1 1 1 2 2 2 2
2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1
1 1 1 1 1 1 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 4 4 4 4 4 4 4 4 4 4
4 4 4 4 4 4 4 4 4 4 4 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 3 3 3 3 3 3 3 3 3 3 3 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
0
1 2
2 2 1 1
1 1 1 1 2 2 2 2
2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
2 2 2 2 2 2 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 1 1 1 1 1 1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 3 3 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 4 4 4 4 4 4 4 4 4 4 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7
這是生成它的代碼：
from basicbintree import Node
for h in range(1, 7 1):
root = Node(0)
P = 2 ** (h 1) - 2 # nodes in partitions
p = P // h # partition size (may be p or p 1)
if h & 1: # odd height
t = (p 1) // 2 # subtree tail nodes from split partition
n = (h - 1) // 2 # odd or even partitions in subtrees except tail
else: # even height
t = 0 # no subtree tail nodes from split partition
n = h // 2 # odd or even partitions in subtrees
s = P // 2 - t # subtree nodes excluding tail
r = s - n * p # partitions of size p 1 in subtrees
x = [p 1] * r [p] * (n - r) # nodes indexed by subtree partition - 1
odd = [1 2 * i for i, c in enumerate(x) for _ in range(c)] [h] * t
even = [2 2 * i for i, c in enumerate(x) for _ in range(c)] [h] * t
for g in range(1, h 1):
start = 2 ** (g - 1) - 1
stop = 2 ** g - 1
if g & 1: # odd level
root.set_level(odd[start:stop] even[start:stop])
else: # even level
root.set_level(even[start:stop] odd[start:stop])
print('```none')
root.print_tree()
print('```')
所有生產到高度 27 的樹木都已通程序式確認符合規格。
Some parts of the algorithm would need a proof, like, e.g., that it's always possible to choose an even size for the split partition in the odd height case, but this and other proofs are left as an exercise to the reader ;-)
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/325486.html