查找完全二叉树的不相关分区
Find unrelated partitions of a complete binary tree
我有一个高度为'h'的完整二叉树。
我如何找到 'h' 个与此无关的分区？
注意：
不相关的分区意味着 child 不能与其直接的 parent.
一起出现
每个分区中的节点数有限制。
分区中最大节点数与分区中最小节点数之差可以为0或1。
此外，root 被排除在分区之外。
设计这个问题的人可能有一个更优雅的解决方案，但以下是可行的。
假设我们有 h 个编号为 1 到 h 的分区，并且分区 n 的节点的值为 n。根节点的值为 0，不参与分区。即使 n 是偶数，我们也称分区，如果 n 是奇数，则称分区为奇数。让我们也对完整的二叉树的级别进行编号，忽略根并从具有 2 个节点的级别 1 开始。 n级有2n个节点，完整树有2h+1-1个节点，但只有P=2h+1-2个节点属于分区（因为排除了根）。每个分区由 p=⌊P/h⌋ 或 p=⌈P/h⌉ 节点组成，使得 ∑ᵢpᵢ=P.
若树的高度h为偶数，将所有偶数分区放入左子树的偶数层和右子树的奇数层，将所有奇数分区放入奇数层左子树和右子树的偶数层。
如果h为奇数，则像偶数情况一样将所有分区分配到分区h-1，但将分区h均匀分配到左右子树的最后一层.
这是 h 最多 7 的结果（为此目的，我以紧凑的方式向终端写了一个很小的 Python library to print binary trees）：
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 的树都已通过程序确认符合规范。
算法的某些部分需要证明，例如，在奇数高度的情况下始终可以为分割分区选择偶数大小，但是这个和其他证明留作练习留给reader;-)
我有一个高度为'h'的完整二叉树。
我如何找到 'h' 个与此无关的分区？
注意： 不相关的分区意味着 child 不能与其直接的 parent.
一起出现每个分区中的节点数有限制。 分区中最大节点数与分区中最小节点数之差可以为0或1。
此外，root 被排除在分区之外。
设计这个问题的人可能有一个更优雅的解决方案，但以下是可行的。
假设我们有 h 个编号为 1 到 h 的分区，并且分区 n 的节点的值为 n。根节点的值为 0，不参与分区。即使 n 是偶数，我们也称分区，如果 n 是奇数，则称分区为奇数。让我们也对完整的二叉树的级别进行编号，忽略根并从具有 2 个节点的级别 1 开始。 n级有2n个节点，完整树有2h+1-1个节点，但只有P=2h+1-2个节点属于分区（因为排除了根）。每个分区由 p=⌊P/h⌋ 或 p=⌈P/h⌉ 节点组成，使得 ∑ᵢpᵢ=P.
若树的高度h为偶数，将所有偶数分区放入左子树的偶数层和右子树的奇数层，将所有奇数分区放入奇数层左子树和右子树的偶数层。
如果h为奇数，则像偶数情况一样将所有分区分配到分区h-1，但将分区h均匀分配到左右子树的最后一层.
这是 h 最多 7 的结果（为此目的，我以紧凑的方式向终端写了一个很小的 Python library to print binary trees）：
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 的树都已通过程序确认符合规范。
算法的某些部分需要证明，例如，在奇数高度的情况下始终可以为分割分区选择偶数大小，但是这个和其他证明留作练习留给reader;-)