Skip to content

Instantly share code, notes, and snippets.

@c7h
Created November 16, 2015 23:16
Show Gist options
  • Save c7h/8be076e81b0933f0e682 to your computer and use it in GitHub Desktop.
Save c7h/8be076e81b0933f0e682 to your computer and use it in GitHub Desktop.
understanding binary search trees
class BinSearchTreeElement(object):
def __init__(self, data, leftTree=None, rightTree=None):
self.data = data
self.left = leftTree
self.right = rightTree
def add(self, element):
if element <= self.data:
self._insertElement(self.left, element)
else:
self._insertElement(self.right, element)
def _insertElement(self, tree, element):
if isinstance(tree, type(None)):
tree = BinSearchTreeElement(element)
else:
tree.add(element)
def search(self, searchFor):
if searchFor == self.data:
return id(self)
elif searchFor <= self.data:
searchtree = self.left
else:
searchtree = self.right
if isinstance(searchtree, type(None)):
return None
elif searchtree.data == searchFor:
return id(searchtree.data)
else:
searchtree.search(searchFor)
class TreeEmptyException(Exception):
pass
if __name__ == "__main__":
root = BinSearchTreeElement(2)
# build tree
root.add(2)
root.add(3)
root.add(9)
root.add(2)
root.add(4)
root.add(7)
searchElement = 7
print "Suche nach %s ergab %s" % (searchElement, root.search(searchElement))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment