¿Se puede cruzar un árbol no binario en orden?

Question

Estamos tratando aquí con un algoritmo de acceso más similar. Parte del algoritmo implica buscar en orden sobre un árbol.

El hecho 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 atravesar los nodos de izquierda a derecha (y procesar el nodo padre sólo una vez? ")

Alguna idea?

actualización

Este árbol tendrá en cada nodo de una 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. Por lo tanto, su "tipo de árbol ab", sin todo el desbordamiento: mecánica de subdesbordamiento. Así que supongo el más similar en el cruce de la orden sería similar a un btree inorder transversal?

Gracias de antemano.

Answer 1

Sí, pero debe definir cuál es el pedido. 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.

Answer 2

No existe un análogo simple de la secuencia en orden para árboles que no sean binarios (de hecho, el 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 primera búsqueda puede servir para su propósito, entonces puede usar eso.