data-structures - practico - tesis sobre netflix

Cuando dos árboles son iguales?

Question

Si el recorrido en orden de dos árboles binarios (no árboles de búsqueda binarios) es el mismo, ¿garantiza que los dos árboles sean iguales?

si la respuesta es no, ¿qué pasa con el cruce en orden y preordenar?

Answer 1

Definitivamente no. Los dos árboles

  b
 / /
a   d
   / /
  c   e

y

    d
   / /
  b   e
 / /
a   c

ambos tienen un recorrido inorden de abcde . Son, de hecho, rotaciones, una operación que preserva la travesía inorden .

Answer 2

Estoy pensando "no".

Es posible que dos árboles se equilibren de forma diferente, pero tienen el mismo "orden" de valores de nodo. Por ejemplo, si, del conjunto

1,2,3,4,5,6,7

Usted construye un árbol:

         4
      2    6
   1   3  5   7

el recorrido en orden producirá 1,2,3,4,5,6,7.

sin embargo, si elige un nodo raíz diferente (si la lista no está ordenada correctamente de antemano)

           5
         4   6
       2       7   
     1   3

Estos dos árboles darán el mismo resultado transversal en orden, pero son (claramente) no idénticos.

o incluso

      7
     6
    5
   4
  3
 2
1

etcétera.

Esto también está relacionado con un problema con los árboles BSP (partición de espacio binario), que normalmente se usan en la detección de colisiones de desarrollo de juegos y en la determinación de la visibilidad.

El BSP almacena triángulos en un árbol. Cada nodo contiene un triángulo o faceta. El nodo izquierdo contiene todos los hijos que están "detrás" de la faceta, mientras que el secundario derecho contiene todo lo que está en "frente". Recurse como se esperaba

Si eliges la faceta más a la izquierda de la escena como tu raíz, el hijo derecho tendrá otras facetas. Si toma una mala decisión para el niño correcto, sucederá lo mismo. Es perfectamente posible que uno construya un compilador BSP que, mediante un análisis idiota, cree un "árbol" que en realidad es una lista (como en mi último ejemplo anterior). El problema es dividir el conjunto de datos para que cada nodo divida la lista restante de la forma más equitativa posible. Esta es una de las razones por las que los BSP generalmente se generan en tiempo de compilación, ya que construir uno para una geometría muy compleja puede llevar horas para encontrar la / una solución óptima.

Answer 3

NO , y se ve con este simple ejemplo

   3            2          
  2           1   3
 1           0
0  

Ambos tienen los mismos atravesamientos inorden [0,1,2,3]

Pero si los recorridos inorden y preorden son iguales, entonces los árboles son iguales.