如何就地将二叉树转换为二叉搜索树，即我们不能使用任何额外的空间 [英] How to convert a binary tree to binary search tree in-place, i.e., we cannot use any extra space

问题描述

如何将二叉树就地转换为二叉搜索树，即我们不能使用任何额外的空间.

How to convert a binary tree to binary search tree in-place, i.e., we cannot use any extra space.

推荐答案

你没有太多的事情要做，但如果需求是我认为的那样，你已经创建了一个二叉树并坐在内存中，但未排序(无论如何，您希望它的排序方式).

You don't give much to go on, but if the requirement is what I think it is, you have a binary tree already created and sitting in memory, but not sorted (the way you want it to be sorted, anyway).

我假设树节点看起来像

struct tree_node {
    struct tree_node * left;
    struct tree_node * right;
    data_t data;
};

我还假设您可以阅读 C

I'm also assuming that you can read C

虽然我们可以坐下来想知道为什么会创建这棵树而没有按照对我们没有任何好处的排序顺序创建，所以我会忽略它并只处理排序.

While we could just sit around wondering why this tree was ever created without having been created in sorted order that doesn't do us any good, so I'll ignore it and just deal with sorting it.

不使用额外空间的要求很奇怪.暂时会有额外的空间，如果只是在堆栈上.我将假设这意味着调用 malloc 或类似的东西，并且结果树使用的内存不会比原始未排序的树多.

The requirement that no extra space be used is odd. Temporarily there will be extra space, if only on the stack. I'm going to assume that it means that calling malloc or something like that and also that the resulting tree has to use no more memory than the original unsorted tree.

第一个也是最简单的解决方案是对未排序的树进行前序遍历，从该树中删除每个节点，然后在新树中进行排序插入.这是 O(n+nlog(n))，也就是 O(nlog(n)).

The first and easiest solution is to do a preorder traversal of the unsorted tree removing each node from that tree and doing a sorted insertion into a new tree. This is O(n+nlog(n)), which is O(nlog(n)).

如果这不是他们想要的，你将不得不使用旋转和其他东西......那太可怕了！

If this isn't what they want and you're going to have to use rotations and stuff..... that's horrible!

我认为您可以通过执行堆排序的奇数版本来做到这一点，但我遇到了问题.我想到的另一件事是在树上进行奇怪的冒泡排序，这会非常慢.

I thought that you could do this by doing an odd version of a heap sort, but I ran into problems. Another thing that did come to mind, which would be horribly slow, would to do an odd version of bubble sort on the tree.

为此，每个节点都被反复比较，并可能与它的每个直接子节点(因此也与其父节点)反复交换，直到您遍历树并且找不到任何需要交换.执行此版本的振动器排序(从左到右和从右到左的冒泡排序)效果最好，并且在初始传递之后，您不需要向下遍历相对于其父级看起来没有乱序的子树.

For this each node is compared and possibly swapped with each of it's direct children (and therefore also with its parent) repeatedly until you traverse the tree and don't find any needed swaps. Doing a shaker sort (bubble sort that goes left to right and the right to left) version of this would work best, and after the initial pass you would not need to traverse down subtrees that did not look out of order with respect to it's parent.

我敢肯定，这个算法要么是在我之前由其他人想到的，并且有一个我不知道的很酷的名字，要么在我没有看到的某些方面存在根本性的缺陷.

I'm sure that either this algorthm was thought up by someone else before me and has a cool name that I just don't know, or that it is fundamentally flawed in some way that I'm not seeing.

为第二个建议进行运行时计算非常复杂.起初我认为它只是 O(n^2)，就像冒泡和振动器排序一样，但我不能满足自己，子树遍历避免可能不会赢得足够的胜利，使它比 O(n^2).本质上，冒泡排序和振动排序也得到了这种优化，但只有在早期发生总排序的末端，你才能削减限制.使用此树版本，您也有机会避免在集合中间出现块.好吧，就像我说的，它可能存在致命的缺陷.

Coming up with the run-time calculations for the second suggestion is a pretty complicated. At first I thought that it would simply be O(n^2), like bubble and shaker sorts, but I can't satisfy myself that the subtree traversal avoidance might not win enough to make it a little bit better than O(n^2). Essentially bubble and shaker sorts get this optimization too, but only at the ends where total sortedness occurs early and you can chop down the limits. With this tree version you get oppurtunities to possibly avoid chunks in the middle of the set as well. Well, like I said, it's probably fatally flawed.

这篇关于如何就地将二叉树转换为二叉搜索树，即我们不能使用任何额外的空间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！