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 -
class BST:
root=None
def put(self, key, val): # ...
def put2(self, node, key, val): # ...
def createTree(self): # ...
def createBalancedTree(self): # ...
def find(self,key):
p = self.root
while p is not None:
if p.key == key:
return p # return p
elif p.key > key:
p = p.left
else:
p = p.right
return None # 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 -
class BST:
# ...
def get(self, key):
p = self.find(key) # call to find
if not p:
return None
else:
return p.val # return p.val
Next, 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 -
class BST:
# ...
def size(self,key):
return self.size2(self.find(key)) # find, not get
def size2(self, subtree): # define size2 like you did put2
if not subtree:
return 0
else:
return 1 + self.size2(subtree.left) + self.size2(subtree.right)
This means we do not define size in the Node class -
class Node:
left = None
right = None
key = 0
val = 0
def __init__(self, key, val):
self.key = key
self.val = val
# do not define "size" on the Node class
Let's test it out with your createBalancedTree() -
bst = BST()
bst.createBalancedTree()
# F
# / \
# A G
# \ \
# B H
# \ \
# C I
# \ \
# D J
# \
# E
print(bst.size('F')) # 10
print(bst.size('A')) # 5
print(bst.size('H')) # 3
print(bst.size('D')) # 2
height
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 -
class BST:
# ...
def height(self,key):
return self.height2(self.find(key))
def height2(self,subtree):
if not subtree:
return 0
else:
return max(self.height2(subtree.left), self.height2(subtree.right)) + 1
depth
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 -
class BST:
# ...
def depth(self,key):
p = self.root
d = 0
while p is not None:
if p.key == key:
return d
elif p.key > key:
p = p.left
else:
p = p.right
d = d + 1
return None
And 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")) # 5
print(bst2.depth("I")) # 3
print(bst2.depth("B")) # 2
print(bst2.depth("Z")) # 0
improvements
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.py
class node:
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)
def put(t, k, v):
if not 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)
def get(t, k):
r = find(t, k)
if not r:
return None
else:
return r.val
def find(t, k):
if not t:
return None
elif 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)
def size(t):
if not t:
return 0
else:
return 1 + 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)
def from_list(l):
t = None
for (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)
class bst:
def __init__(self, t): self.t = t
def put(self, k, v): return bst(put(self.t, k, v))
def find(self, k): return bst(find(self.t, k))
def get(self, k): return get(self.t, k)
def size(self): return size(self.t)
def from_list(l): return bst(from_list(l))
We're all done. We will write our main program which imports from our bst module -
# main.py
from 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
# \
# E
Remember 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()) # 10
print(t.find('A').size()) # 5
print(t.find('H').size()) # 3
print(t.find('D').size()) # 2
functional
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.py
from 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'))) # 10
print(size(find(t, 'A'))) # 5
print(size(find(t, 'H'))) # 3
print(size(find(t, 'D'))) # 2
additional 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 key
class BST:
def find(self, key):
p = self.root
while p is not None:
if p.key == key:
return p
elif p.key > key:
p = p.left
else:
p = p.right
return
# the function that you asked about
def getSize(self, key):
subroot = self.find(key)
if subroot:
return subroot.size()
return 0 # if the key is not found return zero
# a function in the node class to find the subtree size with that node as root
class Node:
def size(self):
return 1 + (self.left.size() if self.left else 0) + (self.right.size() if self.right else 0)
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 -
class BST:
# ...
def inorder(self):
return self.inorder2(self.root)
def inorder2(self, t):
if not t: return
yield from self.inorder2(t.left)
yield (t.key, t.val)
yield from self.inorder2(t.right)
Another way to write this is with a nested function -
class BST:
# ...
def inorder(self):
def loop(t):
if not t: return
yield from loop(t.left)
yield t
yield from 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 -
class BST:
# ...
def find(self, key):
for node in self.inorder():
if node.key == key:
return node
def size(self, key):
p = self.find(key)
if not p: return 0
return sum(1 for _ in BST(p).inorder())
Post a Comment for "How Do I Get The PreOrder,InOrder,PostOrder To Work?"