遍历编号完整树中节点的第i个子代的公式的直观推导 [英] Intuitive derivation of formulas for finding the i-th child of a node in a traversal-numbered complete tree

问题描述

在我的 answer 中，这个问题，我使用了两个通过临时手段得出的公式，而对于这些公式为何起作用的简单解释，我不知所措。这是完整的问题：

请考虑完美或完整的 K 高度为 H 的树，其中每个节点都按其在广度优先遍历中的等级标记，并且其对偶位置为每个节点都按深度优先顺序标记。这是一个K = 2，H = 2的示例：

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

对于BF排序树，深度 N 的第 i 个子节点 D 的计算公式为：

K * N +1 + i

对于DF排序树，深度为 D N 的第 i 个子节点em>由下式给出：

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

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

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

对于节点 N 在深度为 D 的Dem编号为 K 的高度为 H 的一棵树中，它的第一个子代为 N + 1 ，因为它是深度优先遍历中要访问的下一个节点。在访问根于第一个子节点（ N + 1 ）的整个子树后，将直接访问 N 的第二个子节点，该子树本身就是完整的 K -高度为 H-（D + 1）的树。如此处所述，完整的 K 一元树的大小由有限的几何级数之和给出。一个>。所述子树的大小是第一和第二子树之间的距离，并且实际上，由于所有子兄弟的子树的大小相同，因此这是所有同级之间的距离。如果我们将此距离称为步距，则：

第一个孩子是 N + 1
第二个孩子是 N + 1 +步骤
第三个孩子是 N + 1 + step +步骤
...等等。

谁能提供更好的解释或为什么这些公式有效？

解决方案

对于BFS：

如果节点 N 的深度为 D ，并且在<$ c $之前有 a 个节点c> N 深度为 D （以及之后的 b 个节点）：

  N = K ^ 0 + K ^ 1 + ... + K ^（D-1）+ a 
  

第一个子节点之前将标记多少个节点？在深度 D 和 a * K b 个剩余节点>深度 D + 1 之前的子节点。因此，如果 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元树的子树本身就是完美K元树一样，您可以计算其节点数。 / p>

In my answer to this question, I used two formulas that I arrived at by ad-hoc means, and I am at a loss for a simple explanation for why these formulas work. Here is the problem in full:

Consider a perfect or complete K-ary tree of height H where every node is labeled by their rank in a breadth-first traversal, and the its dual where every node is labeled in depth-first order. Here is an example with K=2, H=2:

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

For the BF-ordered tree, the i-th child of a node N at depth D is given by:

K*N + 1 + i

For the DF-ordered tree, the i-th child of a node N at depth D is given by:

N + 1 + i*step, where step = (K^(H - D) - 1) / (K - 1)

What is an intuitive explanation for these formulas?

The BF-ordered formula makes sense to me when looking at any hand-drawn example, but I can't put into words why it works. In the DF-ordered case, the best I can come up with is this:

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.

Can anyone provide a better explanation for how or why these formulas work?

解决方案

For the BFS:

If node N is at depth D and there is a nodes before N at depth D (and b nodes after):

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

How many nodes will be labeled before its first child? There is b remaining nodes at depth D and a * K "child" nodes at depth D+1 that will come before. So if C is the label of the first child of 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

Indeed there is K^D nodes at depth D so a + b + 1 = K^D, therefor:

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

For the DFS:

To compute the size of the step you have to compute the size of the remaining sub-tree, and like a sub-tree of a perfect K-ary tree is itself a perfect K-ary tree, you can compute its number of nodes.

这篇关于遍历编号完整树中节点的第i个子代的公式的直观推导的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！