Construir un árbol

¿Cómo puedo construir un árbol dado su recorrido en orden y preorden? Estoy buscando un algoritmo eficiente.Construir un árbol

Fuente

2010-02-02 Carlin

Bueno, recursivamente. Espero que no seas mi alumno. –

Necesitaría alguna aclaración. ¿Cuál es el formato de los datos de entrada? ¿El árbol está equilibrado? ¿Qué quiere decir con eficiente (Ordo (x), o simplemente "no terriblemente loco"). ¿Cuál es la estructura que quieres construir? Árbol como objetos vinculados, o árbol usando una matriz. – ron

http://forums.devshed.com/software-design-43/finding-binary-tree-from-inorder-and-preorder-traversals-151147.html – Heinzi

Una copia descarada y pegar de Sun's (Oracle now, I guess...) forum:

Pregunta:
¿Puede alguien ayudarme sobre cómo construir el árbol binario de finde y recorridos orden posterior, sólo quiero saber el algoritmo de modo que puedo aplicarlo

Respuesta:
Vamos p_1, p_2...p_n ser el recorrido de orden posterior y dejar que i_1, i_2...i_n sea el recorrido en orden. Desde el recorrido del postorder, sabemos que la raíz del árbol es p_n. Encuentra este elemento en el recorrido en orden, i_1 decir, i_2...i_k-1p_ni_k+1...i_n. Desde el recorrido en orden nos encontramos con todos los elementos en el subárbol izquierdo, es decir, i_1, i_2...i_k-1 y en el subárbol derecho, es decir i_k+1...i_n respectivamente.

Eliminar elemento p_n (y elemento i_k==p_n). Encontrar el elemento más a la derecha en p_jp_1, p_2...p_j...p_n-1 donde p_j es un elemento en i_1, i_2 ... i_k-1. Esta es la raíz del subárbol izquierdo del árbol original. de Split p_1, p_2...p_j y p_j+1 ... p_n-1 y i_1, i_2...i_k-1 y i_k+1...i_n. Ahora tiene dos subsecuencias que representan el postorder y el recorrido inorden de los dos subárboles del árbol original .

Autor: JosAH.

Implementé el algoritmo una vez siguiendo las instrucciones de Jos, ¡y funcionó a la perfección!

Fuente

2010-02-02 15:14:33

Lleva mucho tiempo encontrar el elemento de la derecha p_j en p_1 ~ p_n-1, mientras que también está en i_1 ~ i_k-1. Toma O (n^2) tiempo. En realidad, después de eliminar p_n, y encontrar su posición en i_1 ~ i_n. Ya conocemos la posición de p_j. Esto se debe a que ya conocemos el recuento de nodos en su subárbol izquierdo y derecho, que podría obtenerse contando los elementos después de p_n en i_1 ~ i_n. Con esto, podríamos encontrar fácilmente el lugar para dividir p_1 ~ p_n-1 – ibread

Dado que esto es tarea, no le daré una respuesta completa, pero con suerte, lo suficiente para que se mueva.

Imagine que ha realizado un recorrido de preorden de, digamos this árbol.

El recorrido le da 2-7-2-6-5-11-5 ... etc. Observe que el 5 es realmente el hijo correcto de la raíz.

Obviamente, no se puede decir que solo mirando los números, por lo que o se le informará sobre la estructura del árbol, o si necesita almacenar algunos datos adicionales (es decir, si el nodo es el izquierdo niño o niño correcto, por ejemplo).

Analizar el árbol es simplemente una función recursiva que toma el recorrido de preorden como entrada (piense en su alcance cuando esté pasando la entrada). Como mencioné anteriormente, su recorrido de preorden debe tener datos adicionales adjuntos.

Eficiencia:

cuenta el número de veces que se visitó cada nodo cuando se genera este árbol, sino también en cuenta la operación de leer la entrada. ¿Hay alguna forma de reorganizar la entrada más rápido de lo que puedes construir el árbol? ¿Qué estructura tendrías que usar si necesitas manipular los datos?

En orden: Necesitará la misma idea para pasarlo, así que no lo cubriré. Estoy seguro de que alguien más lo hará, si estás desesperado por ello.

Fuente

2010-02-02 15:22:34

Respuesta

Cuestiones relacionadas