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()
14 answers
Aquí hay un ejemplo rápido de una inserción binaria:
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
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-09-10 19:54:10
class Node:
rChild,lChild,data = None,None,None
Esto está mal-hace que sus variables variables de clase - es decir, cada instancia de Nodo utiliza los mismos valores (cambiar rChild de cualquier nodo lo cambia para todos los nodos!). Esto claramente no es lo que quieres; intenta
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 encadenarse a 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
También, main() está sangrada demasiado lejos - como se muestra, es un método de Árbol que es incalificable porque no acepta un argumento self.
Además, está modificando los datos del objeto directamente (t.root = Node(4)
), lo que destruye la encapsulación( el punto de tener clases en primer lugar); debería estar haciendo algo más como
def main():
t = Tree()
t.add(4) # <- let the tree create a data Node and insert it
t.add(5)
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-03-26 19:33:49
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
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-08-15 02:31:40
El método de la Op Tree.insert
califica para el premio "Gross Misnomer of the Week" 't no inserta nada. Crea un nodo que no está conectado a ningún otro nodo (no es que haya nodos a los que adjuntarlo) y luego el nodo creado se destruye cuando el método regresa.
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
>>>
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-03-26 19:14:27
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.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-03-26 20:06:20
Encuentro las soluciones un poco torpes en la parte insert
. Puedes 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
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2014-09-23 23:09:46
Solo algo para ayudarte a empezar.
Una (simple idea de) búsqueda de árbol binario sería muy probable que se implementara 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.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-03-26 19:29:23
Otro Python BST con clave de ordenación (valor predeterminado)
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)
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-04-29 10:43:40
Aquí está una implementación compacta, orientada a objetos y recursiva:
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
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-09-04 02:33:15
Es fácil implementar un BST usando dos clases, 1. Nodo y 2. Arbol La clase Tree será solo para la interfaz de usuario, y los métodos reales se implementarán en la clase Node.
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 comprobar si BST está correctamente implementado.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-07-06 08:37:06
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)
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-04-08 10:19:24
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()
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-04-24 19:22:50
La respuesta aceptada omite establecer un atributo padre para cada nodo insertado, sin el cual no se puede implementar un método successor
que encuentre al sucesor en un recorrido de árbol en orden en O(h ) tiempo, donde h es la altura del árbol (a diferencia del O(n) tiempo necesario para la caminata).
Aquí está una implementación basada en el pseudocódigo dado en Cormen et al., Introducción a los algoritmos , incluyendo la asignación de un parent
atributo 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__])
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-08-25 10:42:52
Aquí es una implementación de ejemplo si eso ayuda.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-11-10 15:12:52