c - 是否有一个好的算法来对未排序的、平衡的、二叉树进行排序(这比仅仅构建一棵新树更好)？

Question

这听起来像是一道家庭作业题，但老实说，它不是。

我有一个键/值对列表，我正在将其读入二叉树。我为此实现了一个 AVL 树，非常简单——键、值作为有效负载、左 child 、右 child 、平衡因子和树本身的父节点。这里没有问题。

现在，我想根据不同的标准对树重新排序 - 假设不同的比较函数，或者我想使用(部分)值来对树进行排序。当然，我可以按几乎任何顺序遍历我的原始树，并将每个节点添加到一个新的 AVL 树中——毕竟，要构建的代码就在那里。或者我可以将树转储到数组中，qsort() 数组，并使用众多算法中的一种从排序的数组中有效地生成树。

但是，由于太复杂的原因无法在这里解释，我宁愿不分配第二个结构，相反，我想对树本身进行排序。标准的排序算法在这里似乎没有多大意义，因为它们通常依赖于诸如“选择第 n 个元素”、“前进一个元素”、“后退一个元素”之类的操作，这些操作在数组中是廉价的，而是在二叉树中成本很高。

谷歌搜索没有太大帮助 - 有无数网页解释二叉树、B 树、AVL 树、红黑树以及如何使用它们对数据进行排序。我不需要这些页面，我知道基础知识。但是，如果某处有一篇文章解释了“如何对未排序的树进行排序，从而使结果排序且平衡”，那数以万计的页面就可以很好地隐藏它。

因此，如果有任何好的算法可以在保持平衡的同时对未排序的树进行重新排序，我想听听它 - 如果该算法需要的时间少于“只构建一个新的”尝试之一, 更好。

(不，我没有代码可以显示，因为我正在搜索算法；我拥有的 AVL 树构建代码不会对问题有所帮助，一旦我找到合适的算法，我就非常确定我将能够实现它 - 我只需要一个起点)。

Answer 1

一种方法是将树的节点一个一个地移动到已排序的新树中。是的，我知道这在技术上是另一棵树，但你永远不会增加分配的节点数量，也永远不会复制任何内存，只是切换指针。因此，除了一个额外的根节点之外，您并不是在“分配第二个结构”。

我在疯狂地猜测你在这里做什么，但也许你正在改变你的排序键。如果是这样，则可能有两个(或更多)具有相同节点集的树的树指针，因此一个节点可以同时在 2 个(或更多)树中，两次排序，并且排序不同。这也可能有用。