java - 比较树节点

Question

假设我们有一个简单的节点树:

Node 1                        0
 |-Node 1.1                   1
 |  |-Node 1.1.1              2
 |     |-Node 1.1.1.1         3
 |     |-Node 1.1.1.2         4
 |-Node 1.2                   5
    |-Node 1.2.1              6

... etc.

我需要能够通过树中任意 2 个节点的平坦位置来比较它们。最简单的方法是遍历树并为每个节点分配一个索引(如上面最右列所示)，然后比较索引。但是，有两个缺点:

1. 对于大型树，如果我们只需要比较包含数百万个节点的树中的 2 个节点，则计算索引可能会非常耗时且不切实际。
2. 一旦树被修改(插入/删除节点)，就需要重新计算索引。

因此，我的问题是:是否有更好的方法可以让我按位置比较树节点，而无需计算每个节点的索引？

Answer 1

一种方法可能是使用“具体化路径”并比较这些路径(即路径可能是“1.1.1.2”等)。根据您是否知道每个级别有多少个节点，您可以使用固定大小的零件，例如“001.001.001.002” 然后一个简单的字符串比较就可以了。

这样，当插入/删除节点时，您只需更新新节点和受影响的子树的物化路径。更改节点顺序时，您将对顺序已更改的所有节点/子树执行相同的操作。

另一种方法是使用“嵌套集”，请查看此处有关两者的简短教程:https://communities.bmc.com/docs/DOC-9902

基本上，您的问题似乎与如何将树映射到数据库表有关，即将树结构转换为平面列表并返回。