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

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

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

10 个解决方案

#1

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).

您没有给出太多的内容，但是如果需求是我想的，那么您已经有了一个已经创建并驻留在内存中的二叉树，但是没有排序(无论如何，您希望它被排序)。

I'm assuming that the tree nodes look like

我假设树节点是这样的。

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

I'm also assuming that you can read C

我还假设你可以读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.

我们可以坐在这里思考为什么这棵树是在没有按照排序顺序创建的情况下被创建的，它对我们没有任何好处，所以我将忽略它，只处理排序。

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.

要求不使用额外空间的要求是奇数。暂时会有额外的空间，只要在堆栈上。我将假设它意味着调用malloc或者类似的东西，结果树必须使用的内存比原始未排序的树要多。

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)).

第一个也是最简单的解决方案是对未排序的树执行一个预序遍历，从树中删除每个节点，并将排序插入到新树中。这是O(n+nlog(n))，也就是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.

对于这个节点，每个节点都要进行比较，并可能与每个节点(因此也与其父节点)交换，直到遍历树，并没有找到任何需要的交换。做一个shaker排序(由左到右的冒泡排序)，这是最好的方法，在初始阶段之后，你就不需要遍历那些没有考虑到它的父级的子树了。

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.

我敢肯定，在我之前，这个算法是由别人想出的，它有一个很酷的名字，我不知道，或者它在某种程度上是有缺陷的，我没有看到。

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.

提出第二个建议的运行时计算是相当复杂的。起初我还以为这是O(n ^ 2),像泡沫和瓶类,但我无法满足自己的子树遍历回避可能不会赢得足够让它稍微比O(n ^ 2)。本质上，气泡和振动器也能得到这种优化，但只有在总的酸度出现得较早的时候，你才能把极限切掉。使用此树版本，您可以获得机会，以避免在设置中间的块。就像我说的，这可能有致命的缺陷。

#2

Convert Binary Tree to a doubly linked list- can be done inplace in O(n)
Then sort it using merge sort, nlogn
Convert the list back to a tree - O(n)

将二叉树转换为双链表——可以在O(n)中完成，然后使用归并排序，nlogn将列表转换为树- O(n)

Simple nlogn solution.

简单nlogn的解决方案。

#3

Do the PostOrder Traversal and from that create a Binary search tree.

执行PostOrder遍历和创建一个二叉搜索树。

struct Node * newroot = '\0';

struct Node* PostOrder(Struct Node* root)
{
      if(root != '\0')
      {
          PostOrder(root->left);
          PostOrder(root->right);
          insertBST(root, &newroot);
      }
}

insertBST(struct Node* node, struct Node** root)
{
   struct Node * temp, *temp1;
   if( root == '\0')
   {
      *root == node;
       node->left ==  '\0';
       node->right == '\0';
   }
   else
   {
       temp = *root;
       while( temp != '\0')
       {
           temp1= temp;
           if( temp->data > node->data)
               temp = temp->left;
           else
               temp = temp->right;
       }
       if(temp1->data > node->data)
       {
           temp1->left = node;
       }
       else
       {
           temp1->right = node;
       }
       node->left = node->right = '\0';
    }
}

#4

Do following algorithm to reach the solution.

执行以下算法以达到解决方案。

1) find the in order successor without using any space.

1)在不使用任何空间的情况下，找到合适的继任者。

Node InOrderSuccessor(Node node)
{ 
    if (node.right() != null) 
    { 
        node = node.right() 
        while (node.left() != null)  
            node = node.left() 
        return node 
    }
    else
    { 
        parent = node.getParent(); 
        while (parent != null && parent.right() == node)
       { 
            node = parent 
            parent = node.getParent() 
        } 
        return parent 
    } 
} 

2) Do in order traversal without using space.

2)在不使用空格的情况下进行遍历。

a) Find the first node of inorder traversal. It should left most child of the tree if it has, or left of first right child if it has, or right child itself. b) Use above algorithm for finding out inoder successor of first node. c) Repeat step 2 for all the returned successor.

a)找到序遍历的第一个节点。它应该让树的大部分子结点，如果它有，或者是右子结点，或者右子结点。b)使用上述算法找出第一个节点的inoder继承者。c)为所有已返回的继任者重复第二步。

Use above 2 algorithm and do the in order traversal on binary tree without using extra space. Form the binary search tree when doing traversal. But complexity is O(N2) worst case.

使用上述两种算法，并在不使用额外空间的情况下对二叉树进行遍历。在遍历过程中形成二叉搜索树。但是复杂度是O(N2)最糟糕的情况。

#5

Well, if this is an interview question, the first thing I'd blurt out (with zero actual thought) is this: iterate the entire binary recursively and and find the smallest element. Take it out of the binary tree. Now, repeat the process where you iterate the entire tree and find the smallest element, and add it as a parent of the last element found (with the previous element becoming the new node's left child). Repeat as many times as necessary until the original tree is empty. At the end, you are left with the worst possible sorted binary tree -- a linked list. Your pointer is pointing to the root node, which is the largest element.

如果这是一个面试问题，我首先要脱口而出的是:递归地遍历整个二进制，然后找到最小的元素。把它从二叉树中取出来。现在，重复这个过程，您遍历整个树并找到最小的元素，并将其添加为最后一个元素的父元素(前面的元素变成了新节点的左子)。重复多次，直到原始树为空。最后，剩下的是最糟糕的排序二叉树——一个链表。指针指向根节点，根节点是最大的元素。

This is a horrible algorithm all-around - O(n^2) running time with the worst possible binary tree output, but it's a decent starting point before coming up with something better and has the advantage of you being able to write the code for it in about 20 lines on a whiteboard.

这是一个可怕的算法全面- O(n ^ 2)运行时间与最糟糕的二叉树输出,但这是一个不错的起点之前想出更好的东西的好处是你能够把它在20行代码写在白板上。

#6

A binary tree usually is a binary search tree, in which case no conversion is required.

二叉树通常是二叉搜索树，在这种情况下不需要转换。

Perhaps you need to clarify the structure of what you are converting from. Is your source tree unbalanced? Is it not ordered by the key you want to search on? How did you arrive at the source tree?

也许您需要澄清您正在转换的内容的结构。你的源树不平衡吗?它不是按你想要搜索的键来排序的吗?你是如何到达源树的?

#7

#include <stdio.h>
#include <stdlib.h>

typedef int data_t;

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

        /* a bonsai-tree for testing */
struct tree_node nodes[10] =
{{ nodes+1, nodes+2, 1}
,{ nodes+3, nodes+4, 2}
,{ nodes+5, nodes+6, 3}
,{ nodes+7, nodes+8, 4}
,{ nodes+9, NULL, 5}
,{ NULL, NULL, 6}
,{ NULL, NULL, 7}
,{ NULL, NULL, 8}
,{ NULL, NULL, 9}
        };

struct tree_node * harvest(struct tree_node **hnd)
{
struct tree_node *ret;

while (ret = *hnd) {
        if (!ret->left && !ret->right) {
                *hnd = NULL;
                return ret;
                }
        if (!ret->left ) {
                *hnd = ret->right;
                ret->right = NULL;;
                return ret;
                }
        if (!ret->right) {
                *hnd = ret->left;
                ret->left = NULL;;
                return ret;
                }
        hnd = (rand() &1) ? &ret->left : &ret->right;
        }

return NULL;
}

void insert(struct tree_node **hnd, struct tree_node *this)
{
struct tree_node *ret;

while ((ret= *hnd)) {
        hnd = (this->data  < ret->data ) ? &ret->left : &ret->right;
        }
*hnd = this;
}

void show(struct tree_node *ptr, int indent)
{
if (!ptr) { printf("Null\n"); return; }

printf("Node(%d):\n", ptr->data);
printf("%*c=", indent, 'L');  show (ptr->left, indent+2);
printf("%*c=", indent, 'R');  show (ptr->right, indent+2);
}

int main(void)
{
struct tree_node *root, *this, *new=NULL;

for (root = &nodes[0]; this = harvest (&root);  ) {
        insert (&new, this);
        }

show (new, 0);
return 0;
}

#8

struct Node
{
    int value;
    Node* left;
    Node* right;
};

void swap(int& l, int& r)
{
    int t = l;
    l = r;
    r = t;
}

void ConvertToBST(Node* n, Node** max)
{
    if (!n) return;

    // leaf node
    if (!n->left && !n->right)
    {
        *max = n;
        return;
    }

    Node *lmax = NULL, *rmax = NULL;
    ConvertToBST(n->left, &lmax);
    ConvertToBST(n->right, &rmax);

    bool swapped = false;
    if (lmax && n->value < lmax->value)
    {
        swap(n->value, lmax->value);
        swapped = true;
    }

    if (rmax && n->value > rmax->value)
    {
        swap(n->value, n->right->value);
        swapped = true;
    }

    *max = n;
    if (rmax && rmax->value > n->value) *max = rmax;

    // If either the left subtree or the right subtree has changed, convert the tree to BST again
    if (swapped) ConvertToBST(n, max);
}

#9

Do inorder traversal of the binary tree and store the result. sort the result in acending order form the binary search tree by taking middle element of the sorted list as root( this can done using binary search). so we get balanced binary search tree.

对二进制树进行无序遍历并存储结果。通过将排序列表中的中间元素作为根(可以使用二分查找)将结果排序为二叉搜索树。我们得到了平衡的二叉搜索树。

#10

heap sort the tree.. nlogn complexity..

堆排序树. .nlogn复杂. .