Cómo crear un árbol D-ario balanceado en Python utilizando el paquete `networkx` en Python.
Estoy intentando generar un árbol balanceado D-ario en python utilizando el paquete networkx
.
import networkx as nx
g = nx.Graph()
D = int(input("Ingrese el número de hijos de un nodo: "))
L = int(input("Ingrese el número de niveles: "))
# variable para almacenar el número total de nodos en el árbol.
tot_node = 0
for i in range(0, L + 1):
tot_node = tot_node + D ** i
for N in range(1, tot_node):
for j in range(N, N + D):
g.add_edge(N, j)
nx.draw(g)
Para esto, obtengo el siguiente árbol para D=2
y L=3
.
ver descripción de la imagen aquí
¿Alguien puede señalar el error en este código? Quiero construir un árbol balanceado para cualquier D
general (el número de ramas de un nodo).
davy.ai
El código proporcionado en realidad genera un árbol D-ario completo, no un árbol D-ario balanceado. En un árbol D-ario completo, todos los niveles están completamente llenos, excepto posiblemente el último nivel, que se llena de izquierda a derecha. Sin embargo, un árbol D-ario balanceado es un árbol en el cual para cada nodo, la diferencia en el número de descendientes entre cada rama no es mayor que uno.
Para generar un árbol D-ario balanceado, puedes modificar el código de la siguiente manera:
En este código modificado, usamos una lista llamada
levels
para hacer un seguimiento de los nodos en cada nivel del árbol. El nodo raíz está en el nivel 0 y es simplemente el nodo 1. Luego iteramos sobre los niveles del árbol, creando nodos y aristas a medida que avanzamos. Para cada nivel, mantenemos una lista de los nodos en ese nivel llamadalevel
. También actualizamos el número total de nodos en el árbol,node_count
. Creamos un nodonode_count
para cada hijo de cada nodo en el niveli-1
, y agregamos una arista desde el nodo padre al nodo hijo. Utilizamos la división entera//
para calcular el nodo padre en función del índice del nodo hijo, que varía de 1 a D^i inclusive. Finalmente, agregamos la listalevel
alevels
para que podamos calcular el número de nodos en el árbol con la expresiónsum(len(level) for level in levels)
.