← Volver a los ejercicios

Hijo izquierdo y hermano derecho: dos punteros por nodo

Un nodo con una cantidad cualquiera de hijos se guarda con dos campos: hijoIzq[x], el primero de sus hijos, y hermanoDer[x], el hermano que le sigue. Los hijos de un nodo quedan en una lista enlazada y el espacio es Θ(n) sin importar la aridad. Aquí se lee esa lista con el código a la vista, se construyen las dos tablas desde un dibujo, se separan los dos grados de un mismo nodo y se mira el árbol binario que los dos punteros dejan en memoria.

1. El árbol y sus tres arreglos

padre apunta hacia arriba y vale −1 en la raíz; hijoIzq apunta al primer hijo y vale −1 en las hojas; hermanoDer encadena a los hermanos de izquierda a derecha y vale −1 en el último. En ámbar, el nodo x del llamado; en azul, la casilla que se está leyendo.

2. Los hijos de un nodo, siguiendo la cadena

Escoja un nodo y escriba sus hijos antes de ejecutar nada. Los arreglos de arriba son lo único que hace falta.

Los hijos del nodo
Paso 0 de 0
Las dos líneas que leen memoria son la 37, que entra a la cadena por hijoIzq, y la 40, que avanza por hermanoDer. La 37 corre una vez por llamado; la 40, una vez por hijo.

3. Convertir un árbol a los dos punteros

De este árbol solo se da el dibujo. Llene las dos tablas con el nombre del nodo o con −1 donde no haya a quién apuntar.

4. El grado y la aridad

Para tres nodos del árbol de la primera tarjeta, cuántos hijos tiene y cuántas aristas toca. Los dos números son distintos en todos los nodos menos en uno.

Aridad del árbol

5. El árbol binario que quedó en memoria

Cada nodo guarda dos punteros, igual que en un árbol binario. Leyendo hijoIzq como hijo izquierdo y hermanoDer como hijo derecho, lo que hay en memoria es otro árbol, y las profundidades no son las mismas.

Profundidad en el árbol de aridad libre
Profundidad en el árbol binario
Altura del árbol binario

6. Para llevarse

Sin solución aquí. Escriba hermanos(x), que devuelve los hermanos de x sin contarlo, con un solo return y usando los tres arreglos; diga cuánto cuesta en el peor caso y qué nodo del árbol de aridad 6 lo provoca. Después escriba ultimoHijo(x) y diga por qué agregar un hijo al final cuesta el grado de x mientras agregarlo al principio cuesta Θ(1), y qué campo habría que añadir para que las dos cuesten lo mismo. De último, sobre el árbol binario de la quinta tarjeta: su recorrido en preorden coincide con uno de los recorridos del árbol de aridad libre; diga con cuál y por qué el posorden no coincide con ninguno.