Construya un árbol binario tal que el recorrido posterior a la orden debería dar el resultado ordenado

Question

Sé que el recorrido en orden (VISITA IZQUIERDA, VISITAR RAÍZ, VISITAR A LA DERECHA) en un árbol de búsqueda binario me da un resultado ordenado. Pero necesito hacer un recorrido posterior al pedido (VISITAR A LA IZQUIERDA, VISITAR A LA DERECHA, VISITAR RAÍZ) en un árbol binario y el resultado debería darme valores ordenados.

Para lograr eso, ¿cómo debería construir mi árbol binario?

Answer 1

Dado que la raíz se visitó por última vez, debe contener el artículo más grande. Como el subárbol izquierdo se visita antes que el subárbol derecho, todos los elementos en el subárbol izquierdo deben ser más pequeños que cualquier otro en el subárbol derecho.

Por lo tanto, para construir un árbol como este puede proceder de la siguiente manera: Si inserta un elemento que es mayor que la raíz, ese elemento se convierte en la raíz nueva. Si inserta un elemento que es más pequeño que la raíz pero mayor que la raíz del subárbol izquierdo, insértelo en el subárbol derecho. De lo contrario, insértelo en el subárbol izquierdo.

Answer 2

es necesario asegurarse de lo siguiente en cada nodo del árbol:

• valor en el nodo debe ser mayor que todos los valores en el subárbol izquierda-derecha-y sub-árbol.
• Los valores en el subárbol izquierdo deben ser menores que los valores en el subárbol derecho .

Answer 3

Esta subrutina es para la inserción en el árbol de donde estructura de árbol es

struct tree 

{ 

int data; 
tree * left; 
tree *right; 

tree(int n) // constructor 

{ 
     data = n; 
     left = right = NULL; 
    } 
}; 

El algoritmo es:
1. Si el árbol está vacía inserto nuevo nodo.
2. Si los datos del nuevo nodo son mayores que los datos del nodo raíz, cree el nuevo nodo
raíz del árbol.
3. else inserte un nuevo nodo en el subárbol izquierdo del árbol.

tree * insert(tree *root,int n) 

{ 

if(root == NULL) 
{ 

    root = new tree(n); 

    return root; 
} 
else 
{ 

    if(n > root -> data) 
    { 
     tree * t = new tree(n); 

     t -> left = root; 

     return t; 
    } 

    else 


    { 

     root -> left = insert(root -> left,n); 

     return root; 
    } 
    } 
} 

Answer 4

El currently accepted answer da un buen algoritmo en línea. Una solución algo más simple --- que no está en línea y por lo tanto, posiblemente, hacer trampa --- es almacenar una lista enlazada ordenada en los punteros principales.

En otras palabras: ordenar los datos; coloque el elemento más grande en la raíz, haga que uno de sus subárboles esté vacío y construya recursivamente un árbol clasificado por orden posterior de los elementos n-1 restantes en el otro subárbol.

El árbol tendrá una altura n, la hoja única es la cabeza de la lista y la raíz es el elemento de cola. Si caminas a través del árbol desde la hoja hasta la raíz, los elementos formarán una secuencia creciente, y esta ruta se corresponderá exactamente con un recorrido del postorder.

Answer 5

Supresión

• si la hoja, a continuación, eliminar regularmente
• si tiene sólo un hijo conectar hijo a padre
• otra cosa, eliminar la raíz, reemplazarlo con su hijo a la derecha, a continuación, conectar sub izquierda -árbol al vértice más a la izquierda en el subárbol derecho.

por ejemplo:

7               6 
/\              /\ 
    3 6    =========DELETING 7 ============>   4 5 
/\/\             / 
1 2 4 5             3 
                  /\ 
                  1 2