返回一个二叉树中的项目的排序子集

我有很多节点以通常的方式存储在二叉树中，以便它们根据存储在每个节点中的某些值进行排序;也就是说，可以通过树从左到右递归并按照排序顺序获得总集。返回一个二叉树中的项目的排序子集

但是，我有一个很大的单独的数组指针，指向树中的一个节点子集，并且此数组中的顺序是随机的。

我希望能够快速排序这个数组。有什么方法可以回溯到二叉树结构以使其更快？如有必要，我可以将成员添加到任何节点。

谢谢！

来源

2013-02-26 Robotbugs

通过在节点中添加一个标志，您可以获得运行时为O(t+a)（t是树的大小，a是数组的大小）。这是通过首先设置数组中的标志，然后遍历树并选取标记的值来完成的。

这只有在您的树仅比阵列大log a倍时才有利。如果t >> quicksort肯定是首选的方法，因为它的运行时间为O(a * log a)。

来源

2013-02-26 23:32:36

谢谢，我在想，我将不得不退后快速排序。 – Robotbugs 2013-02-27 00:27:35

实际上，如果我最初在-1树中存储索引号，它可能比O（t * a）更快。然后，我可以让数组中的一个通过，并将数组偏移量写入树结构的索引编号成员中，然后遍历该树并将大于等于0的索引列表写入辅助数组（设置它们在使用后回到-1），最后我可以使用索引列表对数组进行排列。如果O（t）是>> O（a），那么它会到达O（t）。 – Robotbugs 2013-02-27 00:32:40

但是在我的情况下t >> a，所以quicksort看起来是最好的选择。 – Robotbugs 2013-02-27 00:33:56

返回一个二叉树中的项目的排序子集

回答

相关问题