使用不同的键对二叉搜索树进行排序？

Question

我在 Java 中有一个二叉搜索树，每个节点都有一个对象，这些对象是根据它们的名称添加的 属性。遍历时根据名称的字母顺序列出对象，这很好。虽然，我需要一种方法来根据对象的年龄 属性 以降序排列对象。所以基本上我需要暂时重新排序树以按顺序打印内容。

到目前为止我想出的是遍历树并将每个节点添加到一个临时数组，完成后对数组进行合并排序。这行得通，但它似乎相对低效并且增加了复杂性，这是我必须创建的第一棵二叉树，所以我的方法可能是不必要的。

我想我的问题是，是否有更有效的方法来处理或思考这个问题以重新排序树？由于树将是完全随机的（就年龄而言）我想不出另一种方法。任何帮助将不胜感激。

Answer 1

您似乎可以创建另一棵根据年龄排序的树，每当您向第一棵树添加一个项目时，您也可以将相同的项目添加到第二棵树。这为您提供了 O(logN) 用于插入新树和 O(N) 用于遍历树并打印出项目与 O(NlogN) 这是合并排序的运行时间。