Reputation: 57
Sorry if my English is bad, I speak Korean as mother tongue.
I am implementing binary search tree in Python 3, but I wasn't able to meet my goal.
Here is code:
class Node(object):
def __init__(self, key=None, data=None):
self.key = key
self.data = data
class BinarySearchTree(object):
keyfunc = None # Will it be worse when using lambda x: x as default?
def __init__(self, node=None):
self.root = node
self.left = None
self.right = None
# I don't want default to be NoneType, but don't know how for now.
def add(self, key, data=None):
node = Node(key, data)
if self.root is None:
self.root = node
return
parent = self.root.key
if self.keyfunc is None:
if key < parent:
if self.left is None:
self.left = __class__(node)
else:
self.left.add(key, data)
elif key > parent:
if self.right is None:
self.right = __class__(node)
else:
self.right.add(key, data)
else:
if keyfunc(key) < keyfunc(parent):
if self.left is None:
self.left = __class__(node)
else:
self.left.add(key, data)
elif keyfunc(key) > keyfunc(parent):
if self.right is None:
self.right = __class__(node)
else:
self.right.add(key, data)
def inorder(self):
if self.root:
if self.left:
self.left.inorder()
print(self.root.key, end=' ')
if self.right:
self.right.inorder()
if __name__ == '__main__':
bst1 = BinarySearchTree()
arr = [2,6,4,3,2,7,8,1,9,5]
for key in arr:
bst1.add(key)
bst1.inorder()
It works anyway, but what I want is:
bst1.left
(or bst1.right
) be always BinarySearchTree.if self.left is None
in add().bst1.left = BinarySearchTree(None)
after class definition, because it will be required to applied to all of nodes.I tried self.left = BinarySearchTree(None)
(of course it resulted bad recursion),
and tried to use __new__()
method and Metaclasses as answered in other stackoverflow questions, but couldn't come up with solution.
It would very grateful if I can get help.
Upvotes: 1
Views: 812
Reputation: 2607
Consider replacing NoneType
child trees with an empty tree object with a None
root. Also, to answer the question in your code comment, I think defaulting keyfunc = lambda x: x
is reasonable, and it simplifies your code further.
class BinarySearchTree:
def __init__(self, node, keyfunc=lambda x: x):
self.root = node
self.keyfunc = keyfunc
if node is not None:
self.left = self.new_empty()
self.right = self.new_empty()
def new_empty(self):
"""Create a new empty child for this tree"""
return BinarySearchTree(None, self.keyfunc)
def add(self, key, data=None):
node = Node(key, data)
if self.root is None:
self.root = node
self.left = self.new_empty()
self.right = self.new_empty()
else:
parent = self.root.key
if self.keyfunc(key) < self.keyfunc(parent):
self.left.add(key, data)
elif self.keyfunc(key) > self.keyfunc(parent):
self.right.add(key, data)
def inorder(self):
if self.root is not None:
self.left.inorder()
print(self.root.key, end=' ')
self.right.inorder()
For ease of use, you may also choose to add a definition like the following:
def __bool__(self):
return self.root is not None
This lets you simplify a test to see if a node is empty by doing something like if self:
instead of if self.root is not None:
in the inorder
method or if self.left:
to see if there is a left child tree instead of if self.left.root is not None:
.
Upvotes: 1