Árbol de construcción con recorrido de preventa dado

Question

Se da un tipo especial de árbol donde todas las hojas están marcadas con L y otras están marcadas con N. Cada nodo puede tener 0 o como máximo 2 nodos. El recorrido de preorden del árbol está dado.

Proporcione un algoritmo para construir el árbol desde este recorrido.

Answer 1

Este es el algoritmo de recorrido preorden:

Preorder(T) 
    if (T is not null) 
    print T.label 
    Preorder(T.left) 
    Preorder(T.right) 

Vamos a tratar de encontrar un algoritmo para una entrada de NNLLNL.

Obviamente, la etiqueta de la raíz se imprime primero. Entonces sabes que la raíz tiene la etiqueta N. Ahora el algoritmo recurre en el subárbol izquierdo. Esto también es N según la entrada. Recurse en el subárbol izquierdo de eso, que es L. Ahora tienes que dar marcha atrás, porque has llegado a una hoja. La siguiente posición en la entrada también es L, por lo que el nodo actual tiene un hijo derecho etiquetado con L. Retrocede una vez. Retroceda nuevamente, porque ha agregado todos los elementos secundarios del nodo actual (máximo 2 hijos). Ahora estás en la raíz otra vez. Tienes que ir a la derecha, porque ya te fuiste a la izquierda. De acuerdo con la entrada, esto es N. Entonces, el hijo correcto de la raíz es N. El hijo izquierdo de eso será L. Este es su árbol:

 N 
    / \ 
    N  N 
/\ /
    L L L 

Tenga en cuenta que la solución no es necesariamente única, pero esto le dará una posible solución.

Pseudocódigo:

k = 0 
input = ... get preorder traversal vector from user ... 
Reconstruct(T) 
    if input[k] == N 
    T = new node with label N 
    k = k + 1 
    Reconstruct(T.left) 
    Reconstruct(T.right) 
    else 
    T = new node with label L 
    T.left = T.right = null 
    k = k + 1 

Call con un nodo nulo.

Pregunta de seguimiento: dado tanto el preorden como el inorder transversal de un árbol binario que contiene distintas etiquetas de nodo, ¿cómo se puede reconstruir de forma única el árbol?