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.
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.Escoja un nodo y escriba sus hijos antes de ejecutar nada. Los arreglos de arriba son lo único que hace falta.
hijoIzq, y la 40, que avanza por hermanoDer. La 37 corre una vez por
llamado; la 40, una vez por hijo.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.
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.
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.
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.