algorithm - profundidad - Convierta un árbol binario a una lista vinculada, primero el ancho, el almacenamiento constante/destructivo

recorrido por anchura arbol binario c++

Question

Esto no es tarea, y no necesito responderla, pero ahora me he obsesionado :)

El problema es:

• Diseñe un algoritmo para aplanar destructivamente un árbol binario a una lista vinculada, primero en amplitud. Bien, bastante fácil. Solo crea una cola y haz lo que tengas que hacer.
• Ese fue el calentamiento. Ahora, impleméntelo con un almacenamiento constante (la recursión, si puede encontrar una respuesta usándola, es un almacenamiento logarítmico, no constante).

Encontré una solución a este problema en Internet hace aproximadamente un año, pero ahora la he olvidado y quiero saber :)

El truco, por lo que recuerdo, involucraba el uso del árbol para implementar la cola, aprovechando la naturaleza destructiva del algoritmo. Cuando está enlazando la lista, también está empujando un elemento en la cola.

Cada vez que trato de resolver esto, pierdo nodos (como cada vez que vinculo el siguiente nodo / agrego a la cola), requiero almacenamiento adicional, o no puedo entender el método complicado que necesito para volver a un Nodo que tiene el puntero que necesito.

Incluso el enlace a ese artículo / publicación original me sería útil :) Google no me está dando ninguna alegría.

Editar:

Jérémie señaló que hay una respuesta bastante simple (y conocida) si tiene un puntero principal. Si bien ahora creo que está en lo cierto acerca de la solución original que contiene un indicador principal, realmente quería resolver el problema sin ella :)

Los requisitos refinados utilizan esta definición para el nodo:

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

Answer 1

La idea:

Puedes construir la lista enlazada a lo largo de los hijos izquierdos del árbol. Al mismo tiempo, los hijos correctos de esa lista se utilizan para mantener una cola de los siguientes subárboles para insertar en la cola.

El algoritmo en pseudo código:

( Editar: reescrito para mayor claridad )

• Un nodo tiene tres componentes: un valor, una referencia a su hijo izquierdo y una referencia a su hijo derecho. Las referencias pueden ser nulas.
• La función para transformar un árbol binario de dichos nodos en una sola lista vinculada
  • toma una referencia al nodo raíz como parámetro root ,
  • Bucles, con tail partir del hijo izquierdo de la root :
    • intercambiar el hijo izquierdo de tail con el hijo derecho de root ,
    • inserción de la cola en bucle ( O (n) ), con inicio de bubble-to partir de la root y de bubble-from el elemento izquierdo de bubble-to ,
      • intercambiar el hijo correcto de bubble-to con el hijo derecho de ''bubble-from'',
      • avanzar de bubble-to y de bubble-from a sus hijos izquierdos,
      • hasta que la bubble-from alcance la tail ,
    • avance la tail hacia su hijo izquierdo,
    • Mientras que la tail no es nula.
  • Finalmente, vuelve la head . La única lista enlazada ahora corre a lo largo de los niños de la izquierda.

Ilustración

El árbol de inicio (creo que debería ser un árbol completo; si faltan nodos, deberían hacerlo desde el final. Podría intentar dar sentido a otros casos, pero hay varias posibilidades diferentes para eso, e implica una mucho de violín)

 1
/ /
2 3
/ / / /
4 5 6 7
/ / / / / / / /
8 9 A B C D E F

Tenga en cuenta que estos no son necesariamente los valores de los nodos, solo están numerados para fines de visualización.

El árbol después de 1 iteración (observe la lista que se forma de 1 a 3 y la cola de los subárboles enraizados en 4 y 5 ):

 head
v
1
/ /
tail 2 4
v / / / /
3 5 8 9
/ / / /
6 7 A B
/ / / /
C D E F

después de 3 iteraciones (la lista ahora es de 1 a 5 , y la cola contiene los subárboles enraizados de 6 a 9 ):

 head
v
1
/ /
2 6
/ / / /
3 7 C D
/ / / /
4 8 E F
/ /
tail > 5 9
/ /
A B

y después de 8 iteraciones (casi terminadas):

 head
v
1
/ /
2 B
/ /
3 C
/ /
4 D
/ /
5 E
/ /
6 F
/
7
/
8
/
9
/
tail > A

Código Real (Lisp)

Esta es la clase de nodo:

(defclass node ()
((left :accessor left)
(right :accessor right)
(value :accessor value)))

Un ayudante útil:

(defmacro swap (a b)
`(psetf ,a ,b
,b ,a))

La función de conversión ( edición: reescrita para mayor claridad ):

(defun flatten-complete-tree (root)
(loop for tail = (and root (left root)) then (left tail)
while tail
do (swap (left tail) (right root))
(loop for bubble-to = root then (left bubble-to)
for bubble-from = (left bubble-to)
until (eq bubble-from tail)
do (swap (right bubble-to) (right bubble-from))))
root)

Operación irreversible para árboles dentados:

He reescrito lo anterior para permitir árboles irregulares irregulares. Sin embargo, no puedes reconstruir el árbol original a partir de esto.

(defun flatten-tree (root)

;; El bucle interno aquí mantiene la head en la raíz del subárbol hasta ahora sin aplanar,
;; es decir, el nodo de la primera rama,
;; mientras que al mismo tiempo, planchar todo desde la raíz a niveles no ramificados hacia la izquierda.
;; Termina nil cuando el árbol está completamente aplanado.

 (loop for head = (loop for x = (or head root) then (left x)
do (when (and x (null (left x)))
(swap (left x) (right x)))
until (or (null x) (right x))
finally (return x))
for tail = (and head (left head)) then (left tail)
while head
do (swap (left tail) (right head))

;; Este bucle interno es la inserción de la cola O (n)

 (loop for bubble-to = head then (left bubble-to)
for bubble-from = (left bubble-to)
until (eq bubble-from tail)
do (swap (right bubble-to) (right bubble-from))))

;; Finalmente, devuelve la raíz original.

 root)

Answer 2

¿Qué hay de esta solución?

temp=root;
struct node*getleftmost(struct node* somenode)
{
while(somenode->left)
somenode=somenode->left;
return somenode;
}
while(temp)
{
if(temp->right){
(getletfmost(temp))->left=temp->right;
temp->right=NULL;}
temp=temp->left;
}

Answer 3

Aquí está mi nombramiento para el problema;

struct TreeNode
{
TreeNode(int in) : data(in)
{
left = nullptr;
right = nullptr;
}
int data;
TreeNode* left;
TreeNode* right;
};
//Converts left pointer to prev , right pointer to next
// A tree which is like 5
// 11 12
//will be converted to double linked list like 5 -> 12 -> 11
void finalize(TreeNode* current, TreeNode* parent)
{
if (parent == nullptr)
{
current->left = nullptr;
return;
}
if (parent->left == current)
{
if (parent->right == nullptr)
{
parent->right = current;
current->left = parent;
}
current->left = parent->right;
}
else
{
current->left = parent;
parent->right = current;
current->right = parent->left;
}
}
void traverser(TreeNode* current, TreeNode* parent)
{
if (current->left != nullptr)
traverser(current->left, current);
if (current->right != nullptr)
traverser(current->right, current);
finalize(current, parent);
}
void start(TreeNode* head)
{
if (head == nullptr || (head->left == nullptr && head->right == nullptr))
return;
traverser(head, nullptr);
}
int main()
{
TreeNode* n1 = new TreeNode(5);
TreeNode* n2 = new TreeNode(11);
TreeNode* n3 = new TreeNode(12);
n1->left = n2;
n1->right = n3;
start(n1);
}

Answer 4

Bueno, no puedo entender en este momento cómo esto ayuda en esta situación, pero podría darle una pista. Existe una técnica llamada "inversión de puntero" que se usa para atravesar iterativamente un árbol sin la necesidad de usar una pila / cola para almacenar punteros; se usó principalmente para recolectores de basura con poca capacidad de memoria. La idea detrás de esto es que cuando se atraviesa al elemento secundario de un nodo, se vincula ese puntero con el elemento secundario de nuevo al elemento principal para que sepa dónde volver cuando termine con ese nodo. De esa manera, la información de rastreo que generalmente mantendrías en una pila / cola ahora está incrustada en el propio árbol.

He encontrado la siguiente slideshow con un ejemplo (desafortunadamente no hay algo mejor en Google). El ejemplo aquí muestra cómo atravesar un árbol binario sin almacenamiento adicional.

Answer 5

En primer lugar, asumiré que sus nodos tienen un campo "padre" que apunta a su padre. O bien es eso, o necesita una pila para poder volver a subir al árbol (y, por lo tanto, no puede cumplir con el requisito de memoria auxiliar O (1)).

Existe una iteración en orden bien conocida que es iterativa y en espacio O (1). Supongamos, por ejemplo, que desea imprimir elementos en orden. Básicamente, cuando atraviesa un árbol binario, tiene que decidir en cualquier momento, en cualquier nodo dado, si desea moverse hacia ARRIBA (hacia el padre), hacia la IZQUIERDA (hacia el lado izquierdo) o hacia la DERECHA. La idea de este algoritmo es basar esta decisión en el lugar de donde vienes:

1. Si vienes del padre, entonces claramente estás visitando el nodo por primera vez, por lo que te quedas a la IZQUIERDA;
2. si sale del elemento secundario izquierdo, entonces ha visitado todos los nodos que son más pequeños que el nodo actual, por lo que puede imprimir (recuerde que queremos imprimir los nodos en orden aquí) el nodo actual, y luego ir a la DERECHA;
3. finalmente, si viene del hijo correcto, eso significa que ha visitado todo el subárbol arraigado en este nodo en particular, por lo que puede hacer una copia de seguridad de UP al padre.

OK: entonces este es el algoritmo que tomas para una base. Ahora, claramente, si está modificando destructivamente esto en una lista enlazada, solo debe modificar un nodo una vez que ya no vaya a visitarlo. Eso es cuando estás subiendo por la derecha. En ese momento, ¿tiene que decidir cuál será el sucesor de ese nodo ...?

Bueno, debe realizar un seguimiento, en todo momento, de dos punteros: uno al nodo más pequeño que haya visitado y el otro al nodo más grande que haya visitado en el subárbol con raíces actuales. Utiliza el más pequeño como el sucesor para los nodos que visita por última vez cuando viene del niño correcto, y usa el más grande como el sucesor para los nodos que visita por última vez desde otra parte, ¡porque no tienen un hijo adecuado!

EDITAR 1 : Olvidé decir que considero implícitamente que el campo "padre" en el árbol binario se convierte en el campo "siguiente" en la lista vinculada, que es lo que modifico en el último paso.

EDICIÓN 3 : La siguiente parte de mi respuesta ha resultado no responder completamente la pregunta original (pero lo que antecede sigue siendo pertinente).

EDIT 2 : Siguiendo el comprensible deseo de Svante, explícito mi sugerencia de usar rotaciones a la izquierda en algún código:

#include <stdlib.h>
#include <stdio.h>
typedef struct node *node;
struct node
{
int value;
node left;
node right;
};
node new_node(int value, node left, node right)
{
node n = (node) malloc(sizeof(struct node));
n->value = value; n->left = left; n->right = right;
return n;
}
int rotate_right(node tree)
{
if(tree != NULL && tree->left != NULL)
{
node
a = tree->left->left,
b = tree->left->right,
c = tree->right;
int tmp = tree->value;
tree->value = tree->left->value;
tree->left->value = tmp;
tree->left->left = b;
tree->left->right = c;
tree->right = tree->left;
tree->left = a;
return 1;
}
return 0;
}

La función de rotación no es elegante, pero como es fácil confundirse, intenté seguir exactamente el mismo nombre que se usa en el artículo de Wikipedia sobre rotaciones . Los nodos A, B, C se nombran como tales en mi código; los nodos P y Q no lo son, y como elegí no usar punteros de punteros, recurrí al truco de cambiar los valores de P y Q --- en lugar de cambiar de lugar. Con "rotation_right" a nuestra disposición, el algoritmo de conversión es bastante simple:

void convert_to_list(node tree)
{
if(tree != NULL) {
while(rotate_right(tree) != 0);
convert_to_list(tree->right);
}
}

El árbol resultante es una lista enlazada ordenada, donde el siguiente puntero de la lista es lo que solía ser el puntero correcto en el árbol. Finalmente, aquí hay un programa de prueba:

int main()
{
node t =
new_node(4,
new_node(2, NULL, new_node(3, NULL, NULL)),
new_node(8, new_node(5, NULL, NULL), NULL));
convert_to_list(t);
for(; t != NULL; t = t->right)
printf("%d, ", t->value);
return 0;
}

Answer 6

Esta es mi respuesta que funciona. Ahora me doy cuenta de que este es el mismo enfoque que la solución de Svante (!), Aunque construyo el árbol a la derecha.

Para el registro, aquí está el código C #:

// Flatten a tree into place in BFS order using O(1) space and O(n) time.
// Here is an example of the transformation (the top-row indicates the
// flattened parts of the tree.
//
// a
// |---.
// b c
// |-. |-.
// d e f g
//
// becomes
//
// a-b-c
// | | |-.
// d e f g
//
// becomes
//
// a-b-c-d-e-f-g
//
public static void FlattenBFS(Tree<T> t)
{
var a = t; // We "append" newly flattened vertices after ''a''.
var done = (t == null);
while (!done)
{
done = true;
var z = a; // This is the last vertex in the flattened part of the tree.
var i = t;
while (true)
{
if (i.L != null)
{
var iL = i.L;
var iLL = iL.L;
var iLR = iL.R;
var aR = a.R;
i.L = iLL;
a.R = iL;
iL.L = iLR;
iL.R = aR;
a = iL;
done &= (iLL == null) & (iLR == null);
}
if (i == z)
{
break; // We''ve flattened this level of the tree.
}
i = i.R;
}
a = (a.R ?? a); // The a.R item should also be considered flattened.
}
}

Answer 7

Hay una implementación java simple con el primer método descrito.

http://www.dsalgo.com/BinaryTreeToLinkedList.php

Answer 8

No creo que necesitemos punteros para los padres. Supongamos de forma inductiva que los niveles 0 a k-1 más un nodo centinela se han convertido en una lista de enlaces individuales en los punteros secundarios izquierdos cuyos elementos secundarios derechos apuntan a los nodos del nivel k. Iterar a través de la lista, agarrando cada "niño derecho" (nodo k de nivel) por turnos e insertarlo al final de la lista, sobrescribiendo el puntero derecho desde el que salió con su hijo izquierdo que pronto se sobrescribirá. Cuando llegamos al final inicial de la lista, hemos extendido la hipótesis inductiva a k + 1.

EDITAR: código

#include <cstdio>
struct TreeNode {
int value;
TreeNode *left;
TreeNode *right;
};
// for simplicity, complete binary trees with 2^k - 1 nodes only
void Flatten(TreeNode *root) {
TreeNode sentinel;
sentinel.right = root;
TreeNode *tail = &sentinel;
while (true) {
TreeNode *p = &sentinel;
TreeNode *old_tail = tail;
while (true) {
if ((tail->left = p->right) == NULL) {
return;
}
tail = p->right;
p->right = p->right->left;
if (p == old_tail) {
break;
}
p = p->left;
}
}
}
int main() {
const int n = 31;
static TreeNode node[1 + n];
for (int i = 1; i <= n; ++i) {
node[i].value = i;
if (i % 2 == 0) {
node[i / 2].left = &node[i];
} else {
node[i / 2].right = &node[i];
}
}
Flatten(&node[1]);
for (TreeNode *p = &node[1]; p != NULL; p = p->left) {
printf("%3d", p->value);
}
printf("/n");
}

Answer 9

Solo para el registro, la versión recursiva es hermosa (esto está en C #):

[Editado: como señala st0le, mi primera versión contiene ''new''s! Perdóname, he pasado los últimos veinte años codificando en lenguajes declarativos. Aquí está la versión corregida.]

[Editar: ratas dobles. Esto no es amplitud primero.]

public static Tree<T> Flatten(Tree<T> t, Tree<T> u = null)
{
if (t == null) return u;
t.R = Flatten(t.L, Flatten(t.R, u));
t.L = null;
return t;
}