How Do I Get The Preorder,inorder,postorder To Work?
Solution 1:
code review and fix
The first problem is that size uses get which returns a value of the tree, not a node. To fix this we rewrite your get function as find, but this time it returns a node -
classBST:
root=Nonedefput(self, key, val): # ...defput2(self, node, key, val): # ...defcreateTree(self): # ...defcreateBalancedTree(self): # ...deffind(self,key):
p = self.root
while p isnotNone:
if p.key == key:
return p # return pelif p.key > key:
p = p.left
else:
p = p.right
returnNone# return None, not "None"We don't need to duplicate this logic in get. Instead we make a call to find which gets the node. If the node is present, then we return the value -
classBST:
# ...defget(self, key):
p = self.find(key) # call to findifnot p:
returnNoneelse:
return p.val # return p.valNext, in the size function, we will use find to get the node. And similar to how you wrote a put2 helper, we can write size2 which handles the looping -
classBST:
# ...defsize(self,key):
return self.size2(self.find(key)) # find, not getdefsize2(self, subtree): # define size2 like you did put2ifnot subtree:
return0else:
return1 + self.size2(subtree.left) + self.size2(subtree.right)
This means we do not define size in the Node class -
classNode:
left = None
right = None
key = 0
val = 0def__init__(self, key, val):
self.key = key
self.val = val
# do not define "size" on the Node classLet's test it out with your createBalancedTree() -
bst = BST()
bst.createBalancedTree()
# F# / \# A G# \ \# B H# \ \# C I# \ \# D J# \# Eprint(bst.size('F')) # 10print(bst.size('A')) # 5print(bst.size('H')) # 3print(bst.size('D')) # 2height
Updated with your help as well, i tried the same method for finding height(), but its returning wrong anwers.
We can write height similar to size -
classBST:
# ...defheight(self,key):
return self.height2(self.find(key))
defheight2(self,subtree):
ifnot subtree:
return0else:
returnmax(self.height2(subtree.left), self.height2(subtree.right)) + 1depth
So if i do a depth('B'), it should return 3. Since B to F, the depth level is 3. And if i do a depth('F'), it should return 0. Since there is no depth in root F
We can write depth very similar to how we wrote find -
classBST:
# ...defdepth(self,key):
p = self.root
d = 0while p isnotNone:
if p.key == key:
return d
elif p.key > key:
p = p.left
else:
p = p.right
d = d + 1returnNoneAnd you did a great job! There is no problem with your code, as demonstrated below -
bst2 = BST()
bst2.createTree()
# F# / \# D I# / \ / \# C E G J# / \# B H# /# A print(bst2.depth("F")) # 5print(bst2.depth("I")) # 3print(bst2.depth("B")) # 2print(bst2.depth("Z")) # 0improvements
Could you explain why there is a need for
put2and a need forsize2? Sorry, i didnt came out with theput2... it was a given code for my assignment
You don't actually need put2 or size2 and I would say they are a bad practice. The problem is that all of the tree logic is tangled up in the class. In this section of the answer, I will show you a total revision of your bst module.
First we begin with a basic node interface. Instead of assigning properties, all we need a simple __init__ constructor. key and val are required. left and right are optional and default to None if not specified -
# bst.pyclassnode:
def__init__(self, key, val, left = None, right = None):
self.key = key
self.val = val
self.left = left
self.right = right
Now we write a plain put function. Notice there's no references to special variables like self. Another thing of key importance is that we never mutate (overwrite) nodes by reassigning the left or right properties. Instead a new node is created -
# bst.py (continued)defput(t, k, v):
ifnot t:
return node(k, v)
elif k < t.key:
return node(t.key, t.val, put(t.left, k, v), t.right)
elif k > t.key:
return node(t.key, t.val, t.left, put(t.right, k, v))
else:
return node(t.key, v, t.left, t.right)
We will continue writing plain functions in this way. Next we define get which is a specialization of find -
# bst.py (continued)defget(t, k):
r = find(t, k)
ifnot r:
returnNoneelse:
return r.val
deffind(t, k):
ifnot t:
returnNoneelif k < t.key:
return find(t.left, k)
elif k > t.key:
return find(t.right, k)
else:
return t
Here we will deviate with size a bit. This time it will not take a key argument. Instead the caller will be able to call size on any node. Usage will be demonstrated below -
# bst.py (continued)defsize(t):
ifnot t:
return0else:
return1 + size(t.left) + size(t.right)
It would be convenient if we could build trees from a list of nodes. This is an improvement from createBalancedTree which calls .put over and over. We can call it from_list -
# main.py
nodes = \
[("F",6), ("A",1), ("B",2), ("C",3), ("D",4), ("E",5), ("G",7), ("H",8), ('I',9), ("J",10)]
t = bst.from_list(nodes)
We can implement from_list easily in our bst module -
# bst.py (continued)deffrom_list(l):
t = Nonefor (k,v) in l:
t = put(t, k, v)
return t
Here's the biggest difference of the module. We write the bst class but it is a simple wrapper around your plain functions, put, find, get, size, and from_list. There is zero complex logic in the class -
# bst.py (continued)classbst:
def__init__(self, t): self.t = t
defput(self, k, v): return bst(put(self.t, k, v))
deffind(self, k): return bst(find(self.t, k))
defget(self, k): return get(self.t, k)
defsize(self): return size(self.t)
deffrom_list(l): return bst(from_list(l))
We're all done. We will write our main program which imports from our bst module -
# main.pyfrom bst import bst
nodes = \
[("F",6), ("A",1), ("B",2), ("C",3), ("D",4), ("E",5), ("G",7), ("H",8), ('I',9), ("J",10)]
t = bst.from_list(nodes)
# F# / \# A G# \ \# B H# \ \# C I# \ \# D J# \# ERemember how I said size does not take a key argument? That's because it can be called on any node. So to find the size of a specific node, we first find it, then size it! This is a core principle of writing reusable functions: each function should do only one thing -
print(t.find('F').size()) # 10print(t.find('A').size()) # 5print(t.find('H').size()) # 3print(t.find('D').size()) # 2functional
An understated advantage of the technique we used is that our bst module can be used in an object-oriented way (above) or in a functional way (below). This dual interface makes our module extremely flexible as it can be used in a variety of styles -
# functional.pyfrom bst import from_list, find, size
nodes = \
[("F",6), ("A",1), ("B",2), ("C",3), ("D",4), ("E",5), ("G",7), ("H",8), ('I',9), ("J",10)]
t = from_list(nodes)
print(size(find(t, 'F'))) # 10print(size(find(t, 'A'))) # 5print(size(find(t, 'H'))) # 3print(size(find(t, 'D'))) # 2additional reading
I've written extensively about the techniques used in this answer. Follow the links to see them used in other contexts with additional explanation provided -
Solution 2:
It seems to me like your stop condition is incorrect. The default values for children (and the root) are None so you should check for z == None. Also it seems like you are mixing up child nodes and keys. It seems to me the best approach would be to first find the node with the desired key and then calculate the subtree size recursively on this node. See the code below.
# a function in the BST class that finds the node with a specific keyclassBST:
deffind(self, key):
p = self.root
while p isnotNone:
if p.key == key:
return p
elif p.key > key:
p = p.left
else:
p = p.right
return# the function that you asked aboutdefgetSize(self, key):
subroot = self.find(key)
if subroot:
return subroot.size()
return0# if the key is not found return zero# a function in the node class to find the subtree size with that node as rootclassNode:
defsize(self):
return1 + (self.left.size() if self.left else0) + (self.right.size() if self.right else0)
Solution 3:
inorder
You should be opening new post for each unique question you have about this code. The current question has deviated a lot from the original. Anyway, following the patterns with your existing code, here's how I might approach inorder -
classBST:
# ...definorder(self):
return self.inorder2(self.root)
definorder2(self, t):
ifnot t: returnyieldfrom self.inorder2(t.left)
yield (t.key, t.val)
yieldfrom self.inorder2(t.right)
Another way to write this is with a nested function -
classBST:
# ...definorder(self):
defloop(t):
ifnot t: returnyieldfrom loop(t.left)
yield t
yieldfrom loop(t.right)
return loop(self.root)
Notice how print is disentangled from the inorder function. This allows the caller to use traversal logic and choose the operation to for each node -
for node in bst.inorder():
print(node.key, node.val)
reusability
After you have inorder defined, you can redefine some of the other functions in your BST class -
classBST:
# ...deffind(self, key):
for node in self.inorder():
if node.key == key:
return node
defsize(self, key):
p = self.find(key)
ifnot p: return0returnsum(1for _ in BST(p).inorder())
Post a Comment for "How Do I Get The Preorder,inorder,postorder To Work?"