CSE030-Lab 11 Binary Trees Solved

In this part of the lab, you will be implementing the basic functions for a Binary Tree, which are provided in the class declaration BTree.h (on CatCourses).  In other words, you have to create and implement the class implementation in a file called BTree.cpp.  The main file you have to use for this lab is also provided on CatCourses (Exercise.cpp).  DO NOT modify the class declaration (BTree.h) or main file (Exercise.cpp).  Looking at the class declaration, you will find that a Node is defined as a structure comprised of a key value (key_value, of type int) and two pointers to the child nodes (left and right, of type Node pointer).  You will also notice (under private) that you will be keeping track of your Binary Tree using a Node pointer, root. This root pointer should always point to the root element of your Binary Tree. If the Binary Tree is empty, the root pointer should point to NULL.  

In this part of the lab, you will need to implement the following functions for the BTree class:  

•      Default Constructor: initializes the root, the binary tree is empty.  

•      Destructor: deletes the entire Binary Tree by calling destroy_tree().  

•      BTree_root(): returns a pointer pointing to the root of the Binary Tree. 

•      destroy_tree(node *leaf): a recursive function that destroys a subtree with the input argument (leaf) as root.  This function will check if leaf exists, then recursively destroy its left and right child nodes. 

•      insert(int key, node *leaf): a recursive function that compares the input argument key with the key_value of the other input argument leaf.  If key is less than key_value, the same function is called with the left child node of leaf as the new input argument; otherwise, the right child node of leaf will be used as the new input argument.  When the leaf node is empty (NULL), a new node is created and its key_value is set to key (remember to set its left and right child nodes to NULL). 

•      search(int key, node *leaf): a recursive function that compares the input argument key with the key_value of the other input argument leaf.  It returns the pointer to leaf if key = key_value.  If key < key_value, the same function is called with the left child node of leaf as the new input argument; otherwise, the right child node of leaf will be used as the new input argument. It returns NULL if leaf is NULL (it reaches the end of the tree but the key is not found). 

•      insert(int key): a public function that inserts a key into the tree.  It creates a new node as root with key_value equals to key if the tree is empty, otherwise it calls insert(key, root) to insert the key at the correct location.

•      search(int key): a public function that starts the search of the input argument key from the root node.  It returns the pointer to the node that has the same key_value as key (you do not need to perform any comparison in this function, only need to call search(int key, node *leaf) with the correct input arguments to start the search). 

•      destroy_tree(): a public function that calls destroy_tree(node *leaf) with the correct input argument to destroy the whole tree. 

 

Note:  

•      a pointer does not point to anything unless you 1) use the reference operator (&) in front of a variable, 2) you dynamically allocate memory for it (using the new operator), or 3) you assign it (set its value to) to another pointer  

•      every time you want to create a node, you will have to use the new operator

•      every time you allocate memory dynamically for a pointer using the new keyword, you have to make sure that you de-allocate the memory once you do not need the data anymore. This can be done using delete (in the destructor, clear and remove functions). 

 

 

 

 

 

 

 

Sample output from Exercise.cpp: 

Root has key: 10 

Left child of root has key: 6 

Right child of root has key: 14 

 

Searching for key 14... 

Key 14 found! 

Its left child has key: 11 

Its left child has key: 18 

 

Searching for key 13... Key 13 not found!