Подтвердить что ты не робот

Как преобразовать двоичное дерево в двоичное дерево поиска на месте, т.е. Мы не можем использовать дополнительное пространство

Как преобразовать двоичное дерево в двоичное дерево поиска на месте, т.е. мы не можем использовать лишнее пространство.

4b9b3361

ОТВЕТЫ

Ответ 1

Вы не уделяете много внимания, но если это то, что я думаю, у вас есть бинарное дерево, уже созданное и сидящее в памяти, но не отсортированное (так, как вы хотите, чтобы оно сортировалось, в любом случае).

Я предполагаю, что узлы дерева выглядят как

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

Я также предполагаю, что вы можете читать C

Пока мы могли просто сидеть, задаваясь вопросом, почему это дерево когда-либо создавалось без создания в отсортированном порядке, что не делает нам ничего хорошего, поэтому я проигнорирую его и просто займусь его сортировкой.

Требование, чтобы дополнительное пространство не использовалось, является нечетным. Временно будет дополнительное пространство, если только на стеке. Я предполагаю, что это означает, что вызов malloc или что-то в этом роде, а также то, что полученное дерево должно использовать больше памяти, чем оригинальное несортированное дерево.

Первое и самое простое решение состоит в том, чтобы выполнить обход предварительного сортировки несортированного дерева, удаляя каждый node из этого дерева и делая сортированную вставку в новое дерево. Это O (n + nlog (n)), то есть O (nlog (n)).

Если это не то, чего они хотят, и вам придется использовать поворот и прочее..... это ужасно!

Я думал, что вы можете сделать это, выполнив нечетную версию кучи, но я столкнулся с проблемами. Еще одна вещь, которая пришла на ум, которая была бы ужасно медленной, сделала бы нечетную версию сортировки пузырьков на дереве.

Для этого каждый node сравнивается и, возможно, поменяется местами каждый из его прямых детей (и, следовательно, также со своим родителем), пока вы не пересечете дерево и не найдете никаких необходимы свопы. Выполнение сортировки шейкера (сортировка пузырьков, которая идет слева направо и справа налево) будет работать лучше всего, и после начального прохода вам не нужно будет перемещать поддеревья, которые не выглядят неуправляемыми по отношению к этому родительскому.

Я уверен, что либо этот algorthm был придуман кем-то еще передо мной, и имеет классное имя, которое я просто не знаю, или что он в корне ошибочен в некотором роде, которого я не вижу.

Выполнение расчетов во время выполнения второго предложения довольно сложно. Сначала я подумал, что это будет просто O (n ^ 2), как пузырь и сортировка шейкера, но я не могу удовлетворить себя тем, что избежание обхода поддерева может не выиграть достаточно, чтобы сделать его немного лучше, чем O (n ^ 2). По существу, пузырьки и шейкер сортируют эту оптимизацию, но только в тех случаях, когда общая сортировка происходит на ранней стадии, и вы можете отменить ограничения. С этой версией дерева вы получаете возможности, чтобы, возможно, избежать кусков в середине набора. Ну, как я уже сказал, он, вероятно, смертельно испорчен.

Ответ 2

Преобразование двоичного дерева в двусвязный список - может выполняться inplace in O (n)
Затем отсортируйте его, используя сортировку слияния, nlogn
Преобразовать список обратно в дерево - O (n)

Простое решение nlogn.

Ответ 3

Проведите обход 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

Сделайте следующий алгоритм для решения.

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) Проведите обход без использования пробела.

a) Найдите первый node обходного пути. Он должен оставить большинство дочерних элементов дерева, если оно есть, или осталось от первого правильного ребенка, если оно есть, или самого ребенка. b) Используйте вышеприведенный алгоритм для определения преемника inoder первого node. c) Повторите шаг 2 для всего возвращаемого преемника.

Используйте алгоритм выше 2 и выполняйте обход на двоичном дереве без использования дополнительного пространства. Создайте двоичное дерево поиска при обходе. Но сложность - это худший случай O(N2).

Ответ 5

Двоичное дерево обычно представляет собой двоичное дерево поиска, и в этом случае преобразование не требуется.

Возможно, вам нужно прояснить структуру того, из чего вы конвертируете. Является ли ваше исходное дерево неуравновешенным? Не упорядочен ли он ключом, который вы хотите найти? Как вы пришли к исходному дереву?

Ответ 6

Хорошо, если это вопрос с интервью, первое, что я выговорил (с нулевой фактической мыслью), это: повторить все рекурсивно и найти наименьший элемент. Выньте это из двоичного дерева. Теперь повторите процесс, в котором вы перебираете все дерево и находите наименьший элемент, и добавляете его как родительский элемент последнего найденного элемента (при этом предыдущий элемент становится новым дочерним элементом node). Повторяйте столько раз, сколько необходимо, пока исходное дерево не станет пустым. В конце вы остаетесь с наименее возможным отсортированным двоичным деревом - связанным списком. Ваш указатель указывает на корень node, который является самым большим элементом.

Это ужасный алгоритм all-around-O (n ^ 2) времени работы с наихудшим выходным двоичным деревом, но он является достойной отправной точкой, прежде чем придумать что-то лучшее и имеет то преимущество, что вы можете писать код для него примерно на 20 строк на доске.

Ответ 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

Проведите обход двоичного дерева и сохраните результат. сортировать результат в порядке обслуживания сформируйте дерево двоичного поиска, выбрав средний элемент отсортированного списка как root (это можно сделать с помощью двоичного поиска). поэтому мы получаем сбалансированное двоичное дерево поиска.

Ответ 10

куча сортировать дерево.. сложность nlogn.