时间戳

首页 > 解决方案 > 用数组存储 k-ary 树

arrays - 用数组存储 k-ary 树

问题描述

仅当您在移动到下一个节点之前用 k-children 从左到右填充每个节点时，将 k-ary 树存储为数组是否有效？

前任：

        1
      / | \
    2   3   4
  / | \
 5  6  7

可以存储为如下所示的数组：

[X,1,2,3,4,5,6,7]
 0 1 2 3 4 5 6 7

通过索引/k 可以找到任何父级。

但是，对于相同的数据但存储为：

        1
      / | \
    2   3   4
  / |   |
 5  6   7

以 7 作为 3 索引的孩子不再有效。

此外，一般来说，兄弟姐妹在当前节点的 +- k 索引内，但我如何确保我不会意外访问父/叔节点？

标签： arraysdata-structurestree

解决方案

假设根节点在数组中的索引 0 处，则索引处的节点的子节点位于i索引(i*n) + 1through处(i*n) + n。节点的父节点位于 index (i-1)/n。如果您想将根放在索引 1 处，有类似的等式，但没有充分的理由让索引 0 空置。

如果要访问当前节点的所有兄弟节点，首先找到父节点，然后访问该节点的所有子节点。这样您就不会意外访问“叔叔”节点。

通常，像这样存储在数组中的树是完全二叉树：除了最后一层之外的所有层都是满的，如果最后一层没有完全满，那么它会从左到右被填满。

您不必填写所有位置，但如果您不需要，那么您需要在该节点的位置有某种标志来告诉您它是空的。

但是像在第二个示例中那样存储树，其中索引 3 的第一个子节点通常放置索引 2 的最后一个子节点会破坏这些计算。您必须在父节点中存储一组子索引，并在每个子节点中存储父索引。

推荐阅读