Skip to content

Instantly share code, notes, and snippets.

@kladd
Created March 20, 2012 14:32
Show Gist options
  • Save kladd/2136212 to your computer and use it in GitHub Desktop.
Save kladd/2136212 to your computer and use it in GitHub Desktop.
binary tree in python
# Binary Tree
#
class Node(object):
left = None
right = None
data = None
def __init__(self, data):
self.data = data
class BinTree(object):
root = None
def __init__(self):
self.root = None
def add(self, nodeData):
self._insertNode(Node(nodeData), self.root)
def find(self, nodeData):
if self.root == None: return None
return(self._findNode(Node(nodeData), self.root))
def traverse(self, node, func):
if node is None: return
self.traverse(node.left, func)
func(node.data)
self.traverse(node.right, func)
def _insertNode(self, inNode, root):
if self.root is None: self.root = inNode
elif inNode.data <= root.data: # go left
if root.left == None: root.left = inNode # add our node
else: self._insertNode(inNode, root.left) # WE MUST GO DEEPER
else: # go right
if root.right == None: root.right = inNode
else: self._insertNode(inNode, root.right)
def _findNode(self, inNode, root):
if root == None: return None
if inNode.data == root.data: return root # not really sure what should be returned here
elif inNode.data < root.data: return self._findNode(inNode, root.left)
else: return self._findNode(inNode, root.right)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment