如何将二叉树转换为二叉搜索树就绪，即我们不能使用任何额外的空间 [英] 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).

我假设树节点看起来像/ p>

I'm assuming that the tree nodes look like

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 + n> log（n）），它是O（n log（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.

我确定这个algorthm是由我之前的其他人考虑的，有一个很酷的名字，我只是不知道，或者从根本上说在某种程度上我没有看到有缺陷。

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屋！