首页 文章

用于在遍历编号的完整树中查找节点的第i个子节点的公式的直观推导

提问于
浏览 次
1

在我的answer到this问题中，我使用了两个通过临时方式得出的公式，我对这些公式为什么起作用的简单解释感到茫然 . 这是完整的问题：

考虑一个高度为H的perfect或完整的K-ary树，其中每个节点在广度优先遍历中用它们的等级标记，并且在其中每个节点以深度优先顺序标记 . 以下是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, where step = (K^(H - D) - 1) / (K - 1)

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

在查看任何手绘示例时，BF命令公式对我来说很有意义，但我不能说出它为什么有效 . 在DF订购的案例中，我能想到的最好的是：

对于高度为H的DFS编号的K-ary树中的深度为D的节点N，其第一个子节点仅为N 1，因为它是在深度优先遍历中要访问的下一个节点 . 在访问以第一个孩子（N 1）为根的整个子树之后，将直接访问N的第二个孩子，该子树本身是高度为H - （D 1）的完整K-ary树 . 任何完整的K-ary树的大小由这里解释的有限几何级数的总和给出 . 所述子树的大小是第一和第二子节点之间的距离，并且实际上，所有兄弟节点之间的距离相同，因为它们的每个子树具有相同的大小 . 如果我们称这个距离为步骤，那么：第一个孩子是N 1第二个孩子是N 1步骤第3个孩子是N 1个步骤......依此类推 .

谁能为这些公式的工作方式或原因提供更好的解释？

algorithm math tree

1 回答

  • 1

    对于BFS：

    如果节点 N 位于深度 D 并且 N 之前有 a 个节点，深度为 D （之后为 b 个节点）：

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

    在第一个孩子之前会标记多少个节点？深度为 D 的剩余节点和深度为 D+1 的 a * K "child"节点将在之前出现 . 因此，如果 C 是 N 的第一个孩子的标签：

    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-ary树的子树本身就是一个完美的K-ary树，您可以计算其节点数 .

    回复于

相关问题