有没有一种有效的方法可以对具有 parent/child 关系的对象数组进行排序？

Question

我正在尝试找出一种对数组进行排序的有效方法，其中每个对象都可以指向同一数组中 "parent" 对象的索引。
每个对象可以没有父对象（索引为-1）或只有一个父对象，所以它只是一个多对一的关系。
您可以将任意数量的对象链接在一起，创建深层层次结构。
然而，它们都在一个连续的数组中，并以任意顺序添加。

这是对象的示例：

struct Object
{
    void* data;

    int ParentIndex; //Will either be '-1' or will be an index in 'objects' where the parent of this object is.
};

std::vector<Object> objects;

似乎要对多对一关系执行此操作的唯一方法是对每个父项使用深度递归。
然而，这具有非常糟糕的性能。
是否存在可以处理此类问题的算法？

Answer 1

您必须考虑一些问题：

理论上，它可能包含一个递归链。 2 个或更多对象互为父对象。
排序时，当您移动父对象时，它必须更新其所有子对象。

因此，我认为唯一有效的方法是将其转换为具有指针而不是索引的图（多子树）。

struct Object2
{
    void* data;
    Object2* FirstChild; // Will point to first child (if there is), or null.
    Object2* NextSibling;// Will point to next sibling (if there is), or null.
};

实际上，您可以使用任何 XML 库对其进行排序：

只需将任何子元素附加到父元素即可。
完成后，您从 XML 中读取元素并使用新索引重新排序。

有没有一种有效的方法可以对具有 parent/child 关系的对象数组进行排序？

Is there an efficient way to sort an array of objects with parent/child relationships?

c++

sorting

algorithm

parent-child