比较树节点

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 个节点在树中的平面位置。最简单的方法是遍历树并为每个节点分配一个索引（如上图最右侧的列所示），然后比较这些索引。但是，有两个缺点：

对于大型树，如果我们只需要比较包含数百万个节点的树中的 2 个节点，则计算索引可能会非常耗时且不切实际。
修改树（节点inserted/removed）后，需要重新计算索引。

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

Answer 1

一种方法可能是使用 "materialized path" 并比较这些路径（即路径可能是 "1.1.1.2" 等）。根据您是否知道每个级别有多少个节点，您可以使用固定大小的零件，例如"001.001.001.002" 然后一个简单的字符串比较就可以解决问题。

这样，当 inserting/deleting 一个节点时，您只需更新新节点和受影响的子树的物化路径。更改节点顺序时，您将对顺序已更改的所有 nodes/subtrees 执行相同的操作。

另一种方法是使用 "nested sets"，请在此处查看有关两者的简短教程：https://communities.bmc.com/docs/DOC-9902

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

比较树节点

Comparing tree nodes

.net

c#

java

collections

tree