Because code of the Node class is missing in the code coming along with the question I took some from here and adapted it to the provided data:
class Node:
"""
Tree node: left and right child + data which can be any object
"""
def __init__(self, data=(0,' ')):
"""
Node constructor
@param data node data object
"""
self.left = None
self.right = None
self.data = data
def insert(self, data):
"""
Insert new node with data
@param data node data object to insert
"""
if self.data:
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
elif data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data
def lookup(self, data, parent=None):
"""
Lookup node containing data
@param data node data object to look up
@param parent node's parent
@returns node and node's parent if found or None, None
"""
if data < self.data:
if self.left is None:
return None, None
return self.left.lookup(data, self)
elif data > self.data:
if self.right is None:
return None, None
return self.right.lookup(data, self)
else:
return self, parent
def delete(self, data):
"""
Delete node containing data
@param data node's content to delete
"""
# get node containing data
node, parent = self.lookup(data)
if node is not None:
children_count = node.children_count()
if children_count == 0:
# if node has no children, just remove it
if parent:
if parent.left is node:
parent.left = None
else:
parent.right = None
del node
else:
self.data = None
elif children_count == 1:
# if node has 1 child
# replace node with its child
if node.left:
n = node.left
else:
n = node.right
if parent:
if parent.left is node:
parent.left = n
else:
parent.right = n
del node
else:
self.left = n.left
self.right = n.right
self.data = n.data
else:
# if node has 2 children
# find its successor
parent = node
successor = node.right
while successor.left:
parent = successor
successor = successor.left
# replace node data by its successor data
node.data = successor.data
# fix successor's parent's child
if parent.left == successor:
parent.left = successor.right
else:
parent.right = successor.right
def print_tree(self):
"""
Print tree content inorder
"""
if self.left:
self.left.print_tree()
print( self.data, end='')
if self.right:
self.right.print_tree()
def children_count(self):
"""
Returns the number of children
@returns number of children: 0, 1, 2
"""
cnt = 0
if self.left:
cnt += 1
if self.right:
cnt += 1
return cnt
def compare_trees(self, node):
"""
Compare 2 trees
@param node tree's root node to compare to
@returns True if the tree passed is identical to this tree
"""
if node is None:
return False
if self.data != node.data:
return False
res = True
if self.left is None:
if node.left:
return False
else:
res = self.left.compare_trees(node.left)
if res is False:
return False
if self.right is None:
if node.right:
return False
else:
res = self.right.compare_trees(node.right)
return res
def tree_data(self):
"""
Generator to get the tree nodes data
"""
# we use a stack to traverse the tree in a non-recursive way
stack = []
node = self
while stack or node:
if node:
stack.append(node)
node = node.left
else: # we are returning so we pop the node and we yield it
node = stack.pop()
yield node.data
node = node.right
#:class node()
def countNodes(tree):
count = 0
if tree.data[1][0].upper() == 'W':
count += 1
print("visitingNode", tree.data, "count", count, "tree.data[1]", tree.data[1])
if tree.left == None and tree.right==None:
return count
if tree.left != None:
count += countNodes(tree.left)
if tree.right != None:
count += countNodes(tree.right)
return count
def main():
myTree = Node() #create an empty tree
#Create a tree with the nodes [20, 2, 25, 14, 1, 23, 75, 93, 74]
#Note that the add function always returns the root of the BST!
myTree.insert((20, "Jenna"))
myTree.insert((2, "Wendy"))
myTree.insert((25, "Layla"))
myTree.insert((14, "Robert"))
myTree.insert((1, "Jamie"))
myTree.insert((23, "Stephanie"))
myTree.insert((75, "Jay"))
myTree.insert((93, "Barbara"))
myTree.insert((74, "John"))
print("Number of names beginning with 'W' or 'w':", countNodes(myTree))
if __name__ == '__main__':
main()
The countNodes() function in the code above works as expected and prints:
visitingNode (0, ' ') count 0 tree.data[1]
visitingNode (20, 'Jenna') count 0 tree.data[1] Jenna
visitingNode (2, 'Wendy') count 1 tree.data[1] Wendy
visitingNode (1, 'Jamie') count 0 tree.data[1] Jamie
visitingNode (14, 'Robert') count 0 tree.data[1] Robert
visitingNode (25, 'Layla') count 0 tree.data[1] Layla
visitingNode (23, 'Stephanie') count 0 tree.data[1] Stephanie
visitingNode (75, 'Jay') count 0 tree.data[1] Jay
visitingNode (74, 'John') count 0 tree.data[1] John
visitingNode (93, 'Barbara') count 0 tree.data[1] Barbara
Number of names beginning with 'W' or 'w': 1
Notice that if tree.data[1][0].upper() == 'W': is enough to test for both cases 'W' and 'w' and that it makes no sense to branch down to nodes which anyway aren't there (when .left is None or .right is None). This makes the code of 'countNodes()' a bit shorter and easier to follow.
