math - 嵌套树元素编号

Question

我想问的是我有嵌套树的数学/逻辑情况，它看起来类似于

我需要每个项目订单的索引号，例如：

Tube - 1
LCD -2
Plasma - 3
MP3 Player - 1
CD Player - 2
2 Way Radios -3

（1,2,3 ...值不一定是这些）

这将是按此值订购项目所必需的。下订单后，我需要获得所有第一件物品，而不是所有第二件物品......等等

设置每个项目的订单号很容易，但我正在寻找的是根据每个项目及其父项目的左右值计算的值

Answer 1

要订购它们，您可以使用 DFS（深度优先搜索算法）。下面是一个可能的伪代码，

DFS(node)
{

index=1

for all child v of node
     assign v the value of index
     DFS (v)
     increment index by 1
end for

}

assign the root the index 1
DFS (root)

Answer 2

您可以将索引计算为左兄弟的索引加一，或者如果没有左兄弟，则计算为一。如果您无法控制计算索引的顺序，则可能必须遍历所有左兄弟，对它们进行计数，以计算索引。

没有直接的方法。看到这一点的一种方法是想象一个节点被插入到具有相当低索引的树中。仅通过查看父级和直接兄弟级指针，其直接兄弟节点以外的节点将无法知道此插入。但他们的指数仍然必须改变。这意味着这些指针不足以直接计算索引。