class TreeNode:
"""
Class for a node in a binary searching tree
The user does not use this class directly, but
the BinaryTree class representing the whole tree,
which is able to call the root node methods.
"""
def __init__(self, key):
"""
Initialize a new binary tree node.
The left and right subtree is empty at the beginning.
:param key: an integer number, the key of the node
"""
self.key = key
self.left = None
self.right = None
def search_node(self, key):
"""
Search for a node labeled by the key.
If there is no such a node in the tree, then that node is
returned the children of which could be labeled by the given key.
:param key: the key to search
:returns: the last touched node with this key
"""
if key < self.key and self.left is not None:
return self.left.search_node(key)
elif key > self.key and self.right is not None:
return self.right.search_node(key)
else:
return self
def levels(self):
"""
Determine the number of levels of the tree
:returns: the number of levels
"""
# TODO determine the number of levels by recursion
return -1
def preorder_walk(self):
"""
Prints the nodes in the order of preorder walk
"""
# TODO Print the sequence of keys of nodes by recursion!
pass
class BinaryTree:
"""
Represent a binary tree
The nonempty trees are represented by the TreeNode object of the
root of the tree.
"""
def __init__(self):
"""
Initialize an empty binary tree.
"""
self.root = None
def insert(self, key):
"""
Insert the key in the tree if it is not alredy in it.
:param key: the key to insert
"""
# TODO Insert the key in the correct place by sort.
# If necessary, initialize the root of the tree.
# If the tree has a root, determine the place of the node
# of the given key using the search_node method.
pass
def search_key(self, key):
"""
Verifies that the parameter key is in the tree.
:param key: the key to search
:returns: True if the key is in the tree, False otherwise.
"""
if self.root is None:
return False
else:
csucs = self.root.search_node(key)
return key == csucs.key
def levels(self):
"""
Count the number of levels of the tree.
:returns: the number of levels
"""
if self.root is None:
return 0
else:
return self.root.levels()
def preorder_walk(self):
"""
Prints the key values of nodes in the order of preorder walk
in separate lines.
"""
if self.root is not None:
self.root.preorder_walk()
if __name__ == '__main__':
import sys
with open(sys.argv[1], 'r') as f:
nodes = [int(i) for i in f.readline().split()]
bintree = BinaryTree()
for node in nodes:
bintree.insert(node)
bintree.preorder_walk()
print("The number of levels in the tree: " + str(bintree.levels()))