Hola, hice un árbol binario simple y agregué un método transversal de pedido anticipado. Después de lanzar algunas ideas, me quedé atascado en encontrar una forma de devolver cada valor del método traverse_pre() en una matriz.
class BST: def __init__(self, val): self.value = val self.left = None self.right = None def add_child(self, val): if self.value: if val < self.value: if self.left == None: self.left = BST(val) else: self.left.add_child(val) else: if val > self.value: if self.right == None: self.right = BST(val) else: self.right.add_child(val) else: self.value = val def traverse_pre(self): if self.left: self.left.traverse_pre() print(self.value) if self.right: self.right.traverse_pre() Tree = BST(5) Tree.add_child(10) Tree.add_child(8) Tree.add_child(2) Tree.add_child(4) Tree.add_child(7) Tree.traverse_pre() ¿Cómo modificaría la función traverse_pre() para devolver una matriz que consta de los valores de los nodos? ¿Hay un buen ejemplo de este proceso para que yo entienda esto más? Estoy un poco atascado en cómo se pueden agregar valores a una matriz dentro de la recursividad.
Así es como lo haría: todas las ramas devuelven sus listas de subelementos.
En caso de que un nodo no tenga subelementos, solo devuelve su propio valor. De lo contrario, también contiene elementos de los niños.
Extend agrega todos los elementos de la lista de resultados del nodo secundario a la lista de resultados del nodo principal.
class BST: def __init__(self, val): self.value = val self.left = None self.right = None def add_child(self, val): if self.value: if val < self.value: if self.left == None: self.left = BST(val) else: self.left.add_child(val) else: if val > self.value: if self.right == None: self.right = BST(val) else: self.right.add_child(val) else: self.value = val def traverse_pre(self): results = [] if self.left: results.extend(self.left.traverse_pre()) results.append(self.value) if self.right: results.extend(self.right.traverse_pre()) return results Tree = BST(5) Tree.add_child(10) Tree.add_child(8) Tree.add_child(2) Tree.add_child(4) Tree.add_child(7) print(Tree.traverse_pre())Puede usar una matriz como una variable global y en la función traverse_pre() puede agregar el valor a esa matriz, en lugar de imprimirla.
arr = [] class BST: def __init__(self, val): self.value = val self.left = None self.right = None def add_child(self, val): if self.value: if val < self.value: if self.left == None: self.left = BST(val) else: self.left.add_child(val) else: if val > self.value: if self.right == None: self.right = BST(val) else: self.right.add_child(val) else: self.value = val def traverse_pre(self): if self.left: self.left.traverse_pre() arr.append(self.value) if self.right: self.right.traverse_pre() Tree = BST(5) Tree.add_child(10) Tree.add_child(8) Tree.add_child(2) Tree.add_child(4) Tree.add_child(7) Tree.traverse_pre() print(arr)Yo abordaría el problema así:
def traverse_pre(self): rslt = [self.value] if self.left: rslt.extend(self.left.traverse_pre()) if self.right: rslt.extend(self.right.traverse_pre())No recomendaría copiar todo el árbol a una lista intermedia usando .append o .extend . En su lugar, use el yield que hace que su árbol sea iterable y capaz de trabajar directamente con muchas funciones integradas de Python:
class BST: # ... def preorder(self): # value yield self.value # left if self.left: yield from self.left.preorder() # right if self.right: yield from self.right.preorder() Simplemente podemos reordenar las líneas para ofrecer diferentes recorridos como inorder :
class BST: # ... def inorder(self): # left if self.left: yield from self.left.inorder() # value yield self.value # right if self.right: yield from self.right.inorder() Y postorder -
class BST: # ... def postorder(self): # left if self.left: yield from self.left.postorder() # right if self.right: yield from self.right.postorder() # value yield self.value El uso de generadores proporciona inversión de control. En lugar de que la función transversal decida qué le sucede a cada nodo, la persona que llama se queda con la decisión de qué hacer. Si una lista es de hecho el objetivo deseado, simplemente use list -
list(mytree.preorder()) # => [ ... ] Dicho esto, hay margen de mejora con el resto de su código. No hay necesidad de mutar nodos y enredar el contexto self y los métodos recursivos dentro de su clase BST directamente. Un enfoque funcional con un contenedor de class delgada le facilitará el crecimiento de la funcionalidad de su árbol. Para obtener más información sobre esta técnica, consulte estas preguntas y respuestas relacionadas .
Si necesita facilitar árboles de tamaño significativo, es posible que se requiera una técnica transversal diferente. Simplemente pregunte en los comentarios y alguien puede ayudarlo a encontrar lo que está buscando.