algorithm - 遍历编号完全树中寻找节点第i个子节点公式的直观推导

Question

在我的answer至 this问题，我使用了两个通过临时方法得出的公式，但我无法简单解释为什么这些公式有效。这是完整的问题:

考虑一个 perfect或高度为 H 的完整 K 元树，其中每个节点在广度优先遍历中都按其等级标记，而其对偶树中每个节点都按深度标记-第一个订单。这是一个 K=2，H=2 的例子:

    _ 0 _                 _ 0 _
   /     \               /     \
  1       2             1       4
 / \     / \           / \     / \
3   4   5   6         2   3   5   6

对于 BF 有序树，深度 D 处的节点 N 的第 i 个子节点由下式给出:

K*N + 1 + i

对于 DF 有序树，深度 D 处的节点 N 的第 i 个子节点由下式给出:

N + 1 + i*step，其中 step = (K^(H - D) - 1)/(K - 1)

这些公式的直观解释是什么？

在查看任何手绘示例时，BF 有序公式对我来说都很有意义，但我无法说出它为什么有效。在 DF 有序的情况下，我能想到的最好的是:

For a node N at depth D in a DFS-numbered K-ary tree of height H, its first child is simply N+1 because it is the next node to be visited in a depth-first traversal. The second child of N will be visited directly after visiting the entire sub-tree rooted at the first child (N+1), which is itself a complete K-ary tree of height H - (D + 1). The size of any complete, K-ary tree is given by the sum of a finite geometric series as explained here. The size of said sub-tree is the distance between the first and second children, and, in fact, it is the same distance between all siblings since each of their sub-trees are the same size. If we call this distance step, then:

1st child is N + 1 2nd child is N + 1 + step 3rd child is N + 1 + step + step ...and so on.

谁能更好地解释这些公式的工作原理或原因？

Answer 1

对于 BFS:

如果节点 N 在深度 D 并且在 N 深度 之前有 a 个节点D(和 b 之后的节点):

N = K^0 + K^1 + ... + K^(D-1) + a

有多少个节点会在第一个 child 之前被标记？在深度 D 处还有 b 个剩余节点和在深度 D+1 处有 a * K 个“子”节点会来之前。所以如果 C 是 N 的第一个 child 的标签:

C = N + b + a * K + 1
C = K^0 + K^1 + ... + K^(D-1) + a + b + a * K + 1
C = K^0 + K^1 + ... + K^(D-1) + K^D + a * K

在 D 深度确实有 K^D 个节点，所以 a + b + 1 = K^D，因此:

C = 1 + (K^0 + ... + K^(D-2) + K^(D-1) + a )* K
C = 1 + N*k

对于 DFS:

要计算步骤的大小，您必须计算剩余子树的大小，就像完美 K 叉树的子树本身就是完美 K 叉树一样，您可以计算它的数量节点数。