7. Binary search tree
-
In this task a binary search tree data structure will be
programmed. A part of the implementation of the search tree
is given in the program
bintree.py.
- The binary tree is represented by the
BinaryTree class.
The root of the tree is contained by the
root attribute.
If the tree is empty, the value of this attribute is
None,
otherwise the root is an instance of the class
TreeNode.
-
The nodes are the instances of
the TreeNode
class.
The values of the left and
right attributes
are None,
if no child is there, or
the TreeNode instance
representing the child node.
-
The methods of the
BinaryTree class
are
insert,
search_key,
level,
preorder_walk.
They check if there is a root of the tree and then call on the
appropriate recursion methods of the
TreeNode class.
-
The common recursive part of the
insert and
search_key methods
is the
search_node method
of the
TreeNode class.
This searches in the tree to find the key value received as a
parameter and returns the node where the search stops. This is
the node that contains the value we are looking for, or if
the key value is not in the tree, the node which the key value
node should be the child of.
- The main program reads integers from a oneline file given as a command
line argument, and then inserts them into
the binary tree. Then print out the values in the preorder
order to the standard output and calculate and print out the
number of tree levels.
-
Complete
the file
bintree.py
with the missing parts!
- Insert the given key into the tree in the
insert method of the
BinaryTree.
You may use
search_node
method of
TreeNode, which
returns the node that either contains the value you are
looking for or the value of the node the child of which will
be the value you are looking for.
The use of this method is also illustrated by the
search_key
method of the
BinaryTree class.
Make sure that the insertion works on an empty binary tree or
if a node is already contains the value you want to insert. In the
latter case you do not insert the value, as the insertion is
idempotent.
- Print out the values of the tree with a recursion in the preorder
order to the standard output in the
preorder_walk
method of
TreeNode.
-
Using recursion, determine the number of levels of the tree in
level method of
TreeNode.
- Test the program with the
bintree1.text,
bintree2.text
and with your own testfiles!