algorithm - 根据其位置计算层次结构中元素的唯一整数标识符

Question

我们有这样的层次结构:

- 1 ( identifier = 100 )
  - 1 (101)
  - 2 (102)
  - 3 (103)
    - 1 (1031)
    - 2 (1032)
    - 3 (1033)
  - 4 (104)
    - 1 (1041)
    - 2 (1042)
    - 3 (1043)
  -901 (1001)
- 2 (200)
  - 1 (201)
  - 2 (202)
- 10 (1000)
  - 1 (1001)

必需的特征:

• 每个节点的标识符应该是唯一的。
• 标识符应根据元素的级别递增
• 标识符应为整数类型。
• 每个元素的计数器在每个新级别/父元素重置

正如您在元素 1.901 和 10.1 的示例中看到的，当前的实现不起作用。我们尝试了下一个解决方案:

• 将每个级别乘以数字。
• 仅将第一个级别乘以一个数字并将每个 child 相加

如果标识符是一个字符串，它会变得更容易，在这种情况下我们可以使用下一种方式:“level1.level2.level3 ...”，所以对于 1 -> 1 它将是“1.1”等等在。但这是最不需要的步骤。

那么，您能否建议可以在此处使用的任何算法来生成所需的标识符？

更新 修复了示例。附言我知道这是错误的。

Answer 1

您太迷恋小数了。

1. 选择一个值 X，它表示一个节点中子节点的最大数量，或者大于您认为方便处理的任何数字。
2. 不再拘泥于十进制数字，将所有标识符表示为以 X 为基数的整数。
3. 将标识符编码为基数 X 中的整数，其中第一个数字表示节点树的顶层，第二个数字表示第二层，依此类推。

因此，如果幸运的话，X 的合理值是 16，您可以使用整数的十六进制表示。如果 36 是一个合适的值，请使用任何字母数字字符作为数字。

编辑

正如 Rafael 所指出的，如果无法定义一个节点可以拥有的子节点数量的上限，那么这种方法就会失效。根据我的经验，这在实践中不太可能成为一个严重的问题。

如果 X 的值很大，比如说 863 那么我建议明显的实现是设置 X = 1000 并且使用 3 个十进制数字组来表示以 1000 为基数的每个数字。这样，标识符 12.245.1 将表示为 12245001。

现在我们进入了 alestanis 的回答已经涵盖的领域