algorithm - que - pangenero

¿Puede un árbol no binario ser cruzado en orden?

Question

Estamos lidiando con un algoritmo vecino más similar aquí. Parte del algoritmo implica buscar en orden sobre un árbol.

El caso es que hasta ahora, no podemos hacer que ese árbol sea binario.

¿Hay un análogo en el cruce de la orden para árboles no binarios? Particularmente, creo que hay, simplemente atravesando los nodos de izquierda a derecha (¿y procesando el nodo padre solo una vez? ")

¿Alguna idea?

actualizar

Este árbol tendrá en cada nodo un pequeño gráfico de n objetos. Cada nodo tendrá n hijos (1 por cada elemento en el gráfico), cada uno de los cuales será otro gráfico. Entonces, su "tipo de árbol ab", sin todo el desbordamiento: mecánica de flujo descendente. ¿Entonces supongo que el recorrido más similar en orden sería similar a un recorrido transversal de btree?

Gracias por adelantado.

Answer 1

No existe un análogo simple de la secuencia en orden para árboles que no sean binarios (en realidad, en orden es una forma de obtener elementos ordenados de un árbol de búsqueda binario).

Puede encontrar más detalles en "El arte de la programación de computadoras" de Knuth, vol. 1, página 336.

Si la búsqueda de amplitud puede servir para su propósito, entonces puede usar eso.

Answer 2

Sí, pero debe definir cuál es el orden. El pedido de publicación y Pre es idéntico, pero inorder toma una definición de cómo las ramas se comparan con los nodos.