algorithm - ordenado - arboles binarios estructura de datos

Determine si un árbol binario es un subárbol de otro árbol binario usando cadenas de prepedido y ordenadas

Question

Quiero averiguar si el árbol binario T2 es un subárbol del árbol binario T1. Leí que uno podría construir representaciones de cadena para T2 y T1 utilizando recorridos previos y en orden, y si las cadenas T2 son subcadenas de cadenas T1, T2 es un subárbol de T1.

Estoy un poco confundido por este método y no estoy seguro de su corrección.

Del wiki: "Un subárbol de un árbol T es un árbol que consiste en un nodo en T y todos sus descendientes en T."

En el siguiente ejemplo:

T2:
  1
 / /
2   3

T1:
  1
 / /
2   3
     /
      4

Si construimos las cadenas para T2 y T1:

preordenar T2: "1,2,3"
preordenar T1: "1,2,3,4"
inorder T2: "2,1,3"
inorder T1: "2,1,3,4"

Las cadenas T2 son subcadenas de T1, por lo que utilizando el método de concordancia de subcadena descrito anteriormente, debemos concluir que T2 es un subárbol de T1.

Sin embargo, T2 por definición no debe ser un subárbol de T1 ya que no tiene todos los descendientes del nodo raíz de T1.

Aquí hay una discusión relacionada, que parece concluir que el método es correcto.

¿Me estoy perdiendo de algo?

Answer 1

Estoy leyendo el mismo libro y dudaba de su solución también. Se me ocurrió otro contraejemplo que no cae en la interpretación potencial que menciona el icepack del usuario (de un subárbol que no necesariamente necesita a todos los descendientes).

Considera los siguientes árboles

T2:
  B
 / /
A   C

T1:
    C
   / /
  B   C
 /
A

preordenar T2: ''BAC''
preordenar T1: ''CBAC''
inorder T2: ''ABC''
inorder T1: ''ABCC''

Nuevamente, las cadenas T2 son subcadenas de sus equivalentes T1 y, sin embargo, T2 no es de ninguna manera un subárbol de T1. Tal vez en el autor había descartado los duplicados y específicamente mencionó su definición de subárbol, podría ser correcto, pero omitir esa información no nos deja más remedio que considerarla como una solución incorrecta.

Answer 2

La definición de subárbol de un árbol debe ser la misma que la definición de subcadena de una cadena. Piénselo de esta manera: 1. la subcadena tiene comienza-con, contiene y termina-con. 2. Tree también debería tener la misma definición pero generalizada para adaptarse a la estructura de datos Tree. 3. La generalización es de 1 dimensional para string a 2 dimensional para tree.

Answer 3

Na ... Este enfoque no es correcto. Porque diferentes árboles pueden tener el mismo recorrido. Por ejemplo, aquí en el ejemplo dado, el árbol es

         26
        /   /
      10     3
    /    /     /
  4      6      3
   /
    30

y los subárboles candidatos son

10
/ /
4 6
/
30

y

30
/ /
4 10
/
6

tiene el mismo recorrido inorden como 4,30,10,6 pero el segundo no es un subárbol

Answer 4

Pregunta muy interesante. Usted parece estar en lo cierto. Supongo que el problema que mencionas surge debido a las diferentes definiciones de subárbol en matemáticas (teoría de grafos) y ciencias de la computación. En la teoría de grafos, T2 es un subárbol apropiado de T1.

Answer 5

Suponiendo que haya obtenido esto del libro "Cracking the Coding Interview", el autor también menciona que para distinguir entre nodos con los mismos valores, también se deben imprimir los valores nulos.

Esto también resolvería su problema con la definición de un subárbol (que es correcto como también se describe en el libro)

preordenar T2: "1, 2, null, null, 3, null, null" preorden T1: "1, 2, nulo, nulo, 3, nulo, 4, nulo, nulo" inorder T2: "nulo, 2, nulo, 1, nulo, 3, nulo "inorder T1:" nulo, 2, nulo, 1, nulo, 3, nulo, 4, nulo "

Como puede ver, T2 no es un subárbol de T1