Cómo convertir un árbol binario de árbol binario de búsqueda en el lugar, es decir, no podemos utilizar cualquier espacio extra

Question

Cómo convertir un árbol binario de árbol binario de búsqueda en el lugar, es decir, no podemos utilizar cualquier espacio adicional.

Answer 1

no dan mucho para seguir adelante, pero si el requisito es lo que yo creo que es, usted tiene un árbol binario ya creado y sentado en la memoria, pero no ordenados (la forma en que desea que se ordenan, de todos modos ).

Estoy asumiendo que los nodos del árbol se parecen

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

También estoy asumiendo que usted puede leer C

Mientras que podíamos simplemente sentarse alrededor preguntándose por qué este árbol fuera creado sin haber sido creado con el fin ordenada que no nos hace ningún bien, así que voy a ignorarlo y simplemente trato con la clasificación de la misma.

El requisito de que no se utilizará ningún espacio adicional es impar. Temporalmente no habrá espacio adicional, aunque sólo sea en la pila. Voy a asumir que significa que llamar a malloc o algo así, y también que el árbol resultante tiene que usar más memoria que el árbol original no ordenado.

La primera y más sencilla solución es hacer un recorrido preorden del árbol sin ordenar la eliminación de cada nodo de ese árbol y haciendo una inserción ordenada en un nuevo árbol. Esto es O (n + n log (n)), que es O (n log (n)).

Si esto no es lo que quieren y usted va a tener que rotaciones de uso y esas cosas ..... eso es horrible!

pensé que podía hacer esto haciendo una versión impar de una pila de clasificación, pero me encontré con problemas. Otra cosa que no vienen a la mente, lo que sería terriblemente lento, sería hacer una versión impar de ordenamiento de burbuja en el árbol.

Para este cada nodo se compara y posiblemente intercambia con cada uno de los niños es directa (y por tanto también con su padre) varias veces hasta que se recorre el árbol y no encuentra ningún permutas necesario. Haciendo un agitador tipo (ordenamiento de burbuja que va de izquierda a derecha y de derecha a izquierda) de esta funcionaría mejor, y después de la pasada inicial no tendría que recorrer hacia abajo subárboles que no parecían fuera de orden con respecto a ella de los padres .

estoy seguro de que sea este algorthm fue ideado por otra persona antes que yo y tiene un nombre fresco que yo no sé, o que está fundamentalmente equivocada de alguna manera que no estoy viendo.

El subir con los cálculos de tiempo de ejecución para la segunda sugerencia es bastante complicado. A primera vista me que simplemente sería O (n ^ 2), al igual que la burbuja y agitador tipo, pero yo no me puede satisfacer que el subárbol recorrido evitación podrían no ganar lo suficiente para que sea un poco mejor que O (n ^ 2). En esencia, la burbuja y agitador tipo reciben esta optimización también, pero sólo en los extremos, donde sortedness total ocurre temprano y se pueden talar los límites. Con esta versión se obtiene del árbol oppurtunities, para evitar posiblemente trozos en el medio del conjunto así. Bueno, como he dicho, es probable que fatalmente defectuoso.

Answer 2

Convertir Binary Tree a un lista- doblemente enlazada puede ser inplace hecho en O (n)
A continuación, ordenar que el uso de combinar especie, nlogn
Convertir la parte posterior lista a un árbol - O (n)

nlogn solución simple.

Answer 3

Hacer la orden posterior de recorrido y desde que crear un árbol de búsqueda binaria.

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';
    }
}

Answer 4

Do siguiente algoritmo para llegar a la solución.

1) encontrar el sucesor en orden sin utilizar ningún espacio.

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 en el recorrido orden sin necesidad de utilizar el espacio.

a) Encuentre el primer nodo de recorrido en orden. Debe dejado la mayor parte del niño del árbol si tiene, o hacia la izquierda del primer hijo derecho si tiene, o el propio hijo derecho. b) El uso anterior algoritmo para encontrar a cabo inoder sucesor del primer nodo. c) Repetir el paso 2 para todos el sucesor devuelto.

El uso por encima del 2 algoritmo y hacer el recorrido en el orden en el árbol binario sin utilizar espacio adicional. Formar el árbol de búsqueda binaria cuando se hace el recorrido. Sin embargo, la complejidad es O(N2) peor de los casos.

Answer 5

Bueno, si se trata de una pregunta de la entrevista, la primera cosa que me gustaría dejar escapar (con el pensamiento real cero) es la siguiente: Iterar todo el binaria recursiva y y encontrar el elemento más pequeño. Sacarlo del árbol binario. Ahora, repita el proceso en el que usted repite todo el árbol y encontrar el elemento más pequeño, y añadirlo como padre del último elemento se encontró (con el elemento anterior convertirse en hijo izquierdo del nodo nuevo). Repita tantas veces como sea necesario hasta que el árbol original está vacía. Al final, lo que queda es la peor posible árbol binario ordenado - una lista enlazada. El puntero apunta al nodo raíz, que es el elemento más grande.

Este es un algoritmo horrible, todo alrededor - O (n ^ 2) el tiempo de funcionamiento con la peor salida de árbol binario es posible, pero es un punto de partida decente antes de llegar a algo mejor y tiene la ventaja de que seas capaz de escribir el código para ello en aproximadamente 20 líneas en una pizarra.

Answer 6

Un árbol binario por lo general es un árbol de búsqueda binaria, en cuyo caso no se requiere ninguna conversión.

Tal vez usted necesita para aclarar la estructura de lo que está convirtiendo a. Es desequilibrada árbol de código fuente? ¿No está ordenada por la clave que desea buscar en? ¿Cómo se llega a la estructura de directorios?

Answer 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;
}

Answer 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);
}

Answer 9

Do finde recorrido del árbol binario y almacenar el resultado. ordenar los resultados con el fin acending formar el árbol de búsqueda binaria tomando elemento medio de la lista clasificada como root (esto se puede hacer mediante la búsqueda binaria). por lo que tenemos equilibrados árbol binario de búsqueda.

Answer 10

pila de clasificación del árbol .. complejidad nlogn ..