¿Cómo construir un árbol no binario con o sin recursividad?

que tienen datos jerárquica que dice así:¿Cómo construir un árbol no binario con o sin recursividad?

+----------------------+-------+ 
| name     | depth | 
+----------------------+-------+ 
| ELECTRONICS   |  0 | 
| TELEVISIONS   |  1 | 
| TUBE     |  2 | 
| LCD     |  2 | 
| PLASMA    |  2 | 
| PORTABLE ELECTRONICS |  1 | 
| MP3 PLAYERS   |  2 | 
| FLASH    |  3 | 
| CD PLAYERS   |  2 | 
| 2 WAY RADIOS   |  2 | 
+----------------------+-------+

TUBO, LCD y de plasma son hijos de los televisores. FLASH es el hijo de los reproductores de MP3. REPRODUCTORES DE MP3, REPRODUCTORES DE CD Y RADIOS DE 2 VÍAS son los hijos de la ELECTRÓNICA PORTÁTIL. Usted obtiene el taladro.

Ahora, tengo un nodo de estructura que contiene su Id y sus hijos, y así sucesivamente, para construir un árbol. De esta manera:

struct Node 
{ 
    int id; 
    list<Node*> children; 
}

Cada elemento se identifica mediante un ID, que es el número de fila (ELECTRONICS = 0, televisores = 1, y así sucesivamente), por lo que es fácil de averiguar quién son los hijos de una nodo.

Este es el árbol que intento construir. Este árbol no es binario, como puedes ver. Entonces, aplicar la recursividad no parece una idea fácil. Corrígeme si estoy equivocado.

Entonces, ¿cómo puedo hacer esto? ¡Ayuda!

Fuente

2012-01-30 Michael Eilers Smith

Recursión lo hace más fácil donde tiene más de 1 ruta para explorar. Por lo tanto, 2 o más ramas hacen que la recursión sea una elección fácil. El enfoque alternativo (iteración) requiere que realice un seguimiento manual de sus progresos (es decir, haga el trabajo que la pila está haciendo en la versión recursiva). Pero para esta situación, la recursión no es necesaria. –

En su lugar, debe usar punteros a Nodos, de lo contrario, estará duplicando datos en su árbol en cada nivel.

También le sugiero que use una enumeración en lugar de la identificación int, hace que el código sea un poco más claro.

no hay problema usando la recursividad con un árbol no binario, solo necesita llamar a left/right (o similar) en su función recursiva llamar a cada uno en el list<Node*>.

Fuente

2012-01-30 06:36:33

Eso tiene sentido. ¡Gracias! –

Probablemente sea mejor usar un hash en lugar de una lista, ya que el tiempo de acceso será constante, mientras que en una lista será O (n) (por definición). –

No hay limitación de que el árbol debe ser binario para construirlo recursivamente. Podría ser ambos creados con método recursivo y no recursivo.

Para mí, construiría el árbol de arriba hacia abajo, es decir, crearía el nodo primario antes de los elementos secundarios. Me gustaría ordenar los datos de entrada de alguna manera para que el consumo sea lineal. Para agregar un nuevo nodo, solo ingrese la profundidad como parámetro y disminuya (mientras desciende de la raíz) hasta que llegue a 0, ahí es donde debería estar el nodo. Por supuesto, se requiere información de la ruta padre para el nodo.

Fuente

2012-01-30 06:33:19 LeleDumbo

No veo cómo funcionaría esto. ¿Me podría dar un fragmento de código? –

Algo como esto:

int main() 
{ 
    Node flash(FLASH_ID); 
    Node mp3(MP3_ID); 

    mp3.children.push_back(flash); 
    // repeat 
}

Fuente

2012-01-30 06:47:16

Usted puede utilizar más de un puntero de enlace. decir

struct node 
{ 
int id; 
node *first_child; 
node *second child; 
node *third_child; 
}

En le caso de que el máximo es de 3. Puede apuntar los nodos con los diferentes niños y acceder a ellos. En caso de que haya menos de 3 hijos, puede hacerlo NULL.

Fuente

2013-12-05 11:00:11 user3069721

¿Cómo construir un árbol no binario con o sin recursividad?

Respuesta

Cuestiones relacionadas