¿Cómo implementar un árbol de búsqueda binario en Python?

Esto es lo que tengo hasta ahora pero no está funcionando:

class Node: rChild,lChild,data = None,None,None def __init__(self,key): self.rChild = None self.lChild = None self.data = key class Tree: root,size = None,0 def __init__(self): self.root = None self.size = 0 def insert(self,node,someNumber): if node is None: node = Node(someNumber) else: if node.data > someNumber: self.insert(node.rchild,someNumber) else: self.insert(node.rchild, someNumber) return def main(): t = Tree() t.root = Node(4) t.root.rchild = Node(5) print t.root.data #this works print t.root.rchild.data #this works too t = Tree() t.insert(t.root,4) t.insert(t.root,5) print t.root.data #this fails print t.root.rchild.data #this fails too if __name__ == '__main__': main() 

Aquí está un ejemplo rápido de un inserto binario:

 class Node: def __init__(self, val): self.l_child = None self.r_child = None self.data = val def binary_insert(root, node): if root is None: root = node else: if root.data > node.data: if root.l_child is None: root.l_child = node else: binary_insert(root.l_child, node) else: if root.r_child is None: root.r_child = node else: binary_insert(root.r_child, node) def in_order_print(root): if not root: return in_order_print(root.l_child) print root.data in_order_print(root.r_child) def pre_order_print(root): if not root: return print root.data pre_order_print(root.l_child) pre_order_print(root.r_child) 

 r = Node(3) binary_insert(r, Node(7)) binary_insert(r, Node(1)) binary_insert(r, Node(5)) 

  3 / \ 1 7 / 5 

 print "in order:" in_order_print(r) print "pre order" pre_order_print(r) in order: 1 3 5 7 pre order 3 1 7 5 
 class Node: rChild,lChild,data = None,None,None 

Esto es incorrecto: hace que sus variables sean variables de clase , es decir, cada instancia de Node usa los mismos valores (¡cambiar rChild de cualquier nodo lo cambia para todos los nodos!). Esto claramente no es lo que quieres; tratar

 class Node: def __init__(self, key): self.rChild = None self.lChild = None self.data = key 

ahora cada nodo tiene su propio conjunto de variables. Lo mismo se aplica a su definición de árbol,

 class Tree: root,size = None,0 # <- lose this line! def __init__(self): self.root = None self.size = 0 

Además, cada clase debe ser una clase de "nuevo estilo" derivada de la clase "objeto" y debe volver a encadenarse al objeto .__ init __ ():

 class Node(object): def __init__(self, data, rChild=None, lChild=None): super(Node,self).__init__() self.data = data self.rChild = rChild self.lChild = lChild class Tree(object): def __init__(self): super(Tree,self).__init__() self.root = None self.size = 0 

Además, main () está demasiado sangrado, como se muestra, es un método de Árbol que no se puede recuperar porque no acepta un argumento propio .

Además, está modificando los datos del objeto directamente ( t.root = Node(4) ) qué tipo de destruye la encapsulación (el punto principal de tener clases en primer lugar); deberias estar haciendo algo mas como

 def main(): t = Tree() t.add(4) # <- let the tree create a data Node and insert it t.add(5) 
 class BST: def __init__(self, val=None): self.left = None self.right = None self.val = val def __str__(self): return "[%s, %s, %s]" % (self.left, str(self.val), self.right) def isEmpty(self): return self.left == self.right == self.val == None def insert(self, val): if self.isEmpty(): self.val = val elif val < self.val: if self.left is None: self.left = BST(val) else: self.left.insert(val) else: if self.right is None: self.right = BST(val) else: self.right.insert(val) a = BST(1) a.insert(2) a.insert(3) a.insert(0) print a 

El método Op’s Tree.insert califica para el premio de “Nombre erróneo bruto de la semana”, no inserta nada. Crea un nodo que no se adjunta a ningún otro nodo (no es que haya nodos para adjuntarlo) y luego el nodo creado se destruye cuando el método vuelve.

Para la edificación de @Hugh Bothwell:

 >>> class Foo(object): ... bar = None ... >>> a = Foo() >>> b = Foo() >>> a.bar >>> a.bar = 42 >>> b.bar >>> b.bar = 666 >>> a.bar 42 >>> b.bar 666 >>> 
 class Node: rChild,lChild,parent,data = None,None,None,0 def __init__(self,key): self.rChild = None self.lChild = None self.parent = None self.data = key class Tree: root,size = None,0 def __init__(self): self.root = None self.size = 0 def insert(self,someNumber): self.size = self.size+1 if self.root is None: self.root = Node(someNumber) else: self.insertWithNode(self.root, someNumber) def insertWithNode(self,node,someNumber): if node.lChild is None and node.rChild is None:#external node if someNumber > node.data: newNode = Node(someNumber) node.rChild = newNode newNode.parent = node else: newNode = Node(someNumber) node.lChild = newNode newNode.parent = node else: #not external if someNumber > node.data: if node.rChild is not None: self.insertWithNode(node.rChild, someNumber) else: #if empty node newNode = Node(someNumber) node.rChild = newNode newNode.parent = node else: if node.lChild is not None: self.insertWithNode(node.lChild, someNumber) else: newNode = Node(someNumber) node.lChild = newNode newNode.parent = node def printTree(self,someNode): if someNode is None: pass else: self.printTree(someNode.lChild) print someNode.data self.printTree(someNode.rChild) def main(): t = Tree() t.insert(5) t.insert(3) t.insert(7) t.insert(4) t.insert(2) t.insert(1) t.insert(6) t.printTree(t.root) if __name__ == '__main__': main() 

Mi solución.

Encuentro las soluciones un poco torpes en la parte de insert . Podrías devolver la referencia root y simplificarla un poco:

 def binary_insert(root, node): if root is None: return node if root.data > node.data: root.l_child = binary_insert(root.l_child, node) else: root.r_child = binary_insert(root.r_child, node) return root 

Solo algo para ayudarte a empezar.

Una (simple idea de) búsqueda de árbol binario sería muy probablemente implementada en python de acuerdo con las líneas:

 def search(node, key): if node is None: return None # key not found if key< node.key: return search(node.left, key) elif key> node.key: return search(node.right, key) else: return node.value # found key 

Ahora solo necesita implementar el andamiaje (creación de árbol e inserciones de valor) y listo.

Otro Python BST con clave de clasificación (valor predeterminado en valor)

 LEFT = 0 RIGHT = 1 VALUE = 2 SORT_KEY = -1 class BinarySearchTree(object): def __init__(self, sort_key=None): self._root = [] self._sort_key = sort_key self._len = 0 def insert(self, val): if self._sort_key is None: sort_key = val // if no sort key, sort key is value else: sort_key = self._sort_key(val) node = self._root while node: if sort_key < node[_SORT_KEY]: node = node[LEFT] else: node = node[RIGHT] if sort_key is val: node[:] = [[], [], val] else: node[:] = [[], [], val, sort_key] self._len += 1 def minimum(self): return self._extreme_node(LEFT)[VALUE] def maximum(self): return self._extreme_node(RIGHT)[VALUE] def find(self, sort_key): return self._find(sort_key)[VALUE] def _extreme_node(self, side): if not self._root: raise IndexError('Empty') node = self._root while node[side]: node = node[side] return node def _find(self, sort_key): node = self._root while node: node_key = node[SORT_KEY] if sort_key < node_key: node = node[LEFT] elif sort_key > node_key: node = node[RIGHT] else: return node raise KeyError("%r not found" % sort_key) 

Aquí hay una implementación recursiva compacta, orientada a objetos:

  class BTreeNode(object): def __init__(self, data): self.data = data self.rChild = None self.lChild = None def __str__(self): return (self.lChild.__str__() + '<-' if self.lChild != None else '') + self.data.__str__() + ('->' + self.rChild.__str__() if self.rChild != None else '') def insert(self, btreeNode): if self.data > btreeNode.data: #insert left if self.lChild == None: self.lChild = btreeNode else: self.lChild.insert(btreeNode) else: #insert right if self.rChild == None: self.rChild = btreeNode else: self.rChild.insert(btreeNode) def main(): btreeRoot = BTreeNode(5) print 'inserted %s:' %5, btreeRoot btreeRoot.insert(BTreeNode(7)) print 'inserted %s:' %7, btreeRoot btreeRoot.insert(BTreeNode(3)) print 'inserted %s:' %3, btreeRoot btreeRoot.insert(BTreeNode(1)) print 'inserted %s:' %1, btreeRoot btreeRoot.insert(BTreeNode(2)) print 'inserted %s:' %2, btreeRoot btreeRoot.insert(BTreeNode(4)) print 'inserted %s:' %4, btreeRoot btreeRoot.insert(BTreeNode(6)) print 'inserted %s:' %6, btreeRoot 

La salida del main () anterior es:

 inserted 5: 5 inserted 7: 5->7 inserted 3: 3<-5->7 inserted 1: 1<-3<-5->7 inserted 2: 1->2<-3<-5->7 inserted 4: 1->2<-3->4<-5->7 inserted 6: 1->2<-3->4<-5->6<-7 

es fácil de implementar un BST utilizando dos clases, 1. Nodo y 2. La clase Árbol de árbol será solo para la interfaz del usuario, y los métodos reales se implementarán en la clase Nodo.

 class Node(): def __init__(self,val): self.value = val self.left = None self.right = None def _insert(self,data): if data == self.value: return False elif data < self.value: if self.left: return self.left._insert(data) else: self.left = Node(data) return True else: if self.right: return self.right._insert(data) else: self.right = Node(data) return True def _inorder(self): if self: if self.left: self.left._inorder() print(self.value) if self.right: self.right._inorder() class Tree(): def __init__(self): self.root = None def insert(self,data): if self.root: return self.root._insert(data) else: self.root = Node(data) return True def inorder(self): if self.root is not None: return self.root._inorder() else: return False if __name__=="__main__": a = Tree() a.insert(16) a.insert(8) a.insert(24) a.insert(6) a.insert(12) a.insert(19) a.insert(29) a.inorder() 

Función inorder para verificar si BST está correctamente implementado.

El siguiente código es básico en la respuesta de @ DTing y lo que aprendo de la clase, que usa un bucle while para insertar (indicado en el código).

 class Node: def __init__(self, val): self.l_child = None self.r_child = None self.data = val def binary_insert(root, node): y = None x = root z = node #while loop here while x is not None: y = x if z.data < x.data: x = x.l_child else: x = x.r_child z.parent = y if y == None: root = z elif z.data < y.data: y.l_child = z else: y.r_child = z def in_order_print(root): if not root: return in_order_print(root.l_child) print(root.data) in_order_print(root.r_child) r = Node(3) binary_insert(r, Node(7)) binary_insert(r, Node(1)) binary_insert(r, Node(5)) in_order_print(r) 

Aquí hay una solución de trabajo.

 class BST: def __init__(self,data): self.root = data self.left = None self.right = None def insert(self,data): if self.root == None: self.root = BST(data) elif data > self.root: if self.right == None: self.right = BST(data) else: self.right.insert(data) elif data < self.root: if self.left == None: self.left = BST(data) else: self.left.insert(data) def inordertraversal(self): if self.left != None: self.left.inordertraversal() print (self.root), if self.right != None: self.right.inordertraversal() t = BST(4) t.insert(1) t.insert(7) t.insert(3) t.insert(6) t.insert(2) t.insert(5) t.inordertraversal() 

La respuesta aceptada omite establecer un atributo principal para cada nodo insertado, sin el cual no se puede implementar un método successor que encuentre al sucesor en un recorrido en árbol en orden en el tiempo O ( h ), donde h es la altura del árbol (como A diferencia del tiempo O ( n ) necesario para la caminata).

Aquí hay una implementación basada en el pseudocódigo dado en Cormen et al., Introducción a los algoritmos , que incluye la asignación de un atributo parent y un método successor :

 class Node(object): def __init__(self, key): self.key = key self.left = None self.right = None self.parent = None class Tree(object): def __init__(self, root=None): self.root = root def insert(self, z): y = None x = self.root while x is not None: y = x if z.key < x.key: x = x.left else: x = x.right z.parent = y if y is None: self.root = z # Tree was empty elif z.key < y.key: y.left = z else: y.right = z @staticmethod def minimum(x): while x.left is not None: x = x.left return x @staticmethod def successor(x): if x.right is not None: return Tree.minimum(x.right) y = x.parent while y is not None and x == y.right: x = y y = y.parent return y 

Aquí hay algunas pruebas para mostrar que el árbol se comporta como se espera para el ejemplo dado por DTing :

 import pytest @pytest.fixture def tree(): t = Tree() t.insert(Node(3)) t.insert(Node(1)) t.insert(Node(7)) t.insert(Node(5)) return t def test_tree_insert(tree): assert tree.root.key == 3 assert tree.root.left.key == 1 assert tree.root.right.key == 7 assert tree.root.right.left.key == 5 def test_tree_successor(tree): assert Tree.successor(tree.root.left).key == 3 assert Tree.successor(tree.root.right.left).key == 7 if __name__ == "__main__": pytest.main([__file__]) 

El problema, o al menos un problema con su código está aquí:

 def insert(self,node,someNumber): if node is None: node = Node(someNumber) else: if node.data > someNumber: self.insert(node.rchild,someNumber) else: self.insert(node.rchild, someNumber) return 

Verá la statement “if node.data> someNumber:” y la statement “else:” asociada tienen el mismo código después de ellos. es decir, haces lo mismo si la afirmación if es verdadera o falsa.

Le sugiero que probablemente tenga la intención de hacer cosas diferentes aquí, tal vez uno de estos debería decir self.insert (node.lchild, someNumber)?

Otra solución BST de Python

 class Node(object): def __init__(self, value): self.left_node = None self.right_node = None self.value = value def __str__(self): return "[%s, %s, %s]" % (self.left_node, self.value, self.right_node) def insertValue(self, new_value): """ 1. if current Node doesnt have value then assign to self 2. new_value lower than current Node's value then go left 2. new_value greater than current Node's value then go right :return: """ if self.value: if new_value < self.value: # add to left if self.left_node is None: # reached start add value to start self.left_node = Node(new_value) else: self.left_node.insertValue(new_value) # search elif new_value > self.value: # add to right if self.right_node is None: # reached end add value to end self.right_node = Node(new_value) else: self.right_node.insertValue(new_value) # search else: self.value = new_value def findValue(self, value_to_find): """ 1. value_to_find is equal to current Node's value then found 2. if value_to_find is lower than Node's value then go to left 3. if value_to_find is greater than Node's value then go to right """ if value_to_find == self.value: return "Found" elif value_to_find < self.value and self.left_node: return self.left_node.findValue(value_to_find) elif value_to_find > self.value and self.right_node: return self.right_node.findValue(value_to_find) return "Not Found" def printTree(self): """ Nodes will be in sequence 1. Print LHS items 2. Print value of node 3. Print RHS items """ if self.left_node: self.left_node.printTree() print(self.value), if self.right_node: self.right_node.printTree() def isEmpty(self): return self.left_node == self.right_node == self.value == None def main(): root_node = Node(12) root_node.insertValue(6) root_node.insertValue(3) root_node.insertValue(7) # should return 3 6 7 12 root_node.printTree() # should return found root_node.findValue(7) # should return found root_node.findValue(3) # should return Not found root_node.findValue(24) if __name__ == '__main__': main() 

Aquí hay una implementación de ejemplo si eso ayuda.