Question

In this assignment you will create a Binary Search Tree to store and retrieve objects of type ItemType. The purpose of this assignment is for you to become familiar with basic tree operations, and understand the efficiency of trees compared to previously studied data structures. Binary Tree nodes have only two children, left and right. Nodes are compared based on their Key instance variable, which in this assignment is of type ItemType. All elements in the left subtree of a given node have key values less than the given node and, all elements in the right subtree have key values greater that the given node. A Binary tree must maintain this sorted property at all times. 
In this assignment, the binary tree should not accept duplicate values. In order to implement this BinaryTree, you will use the ItemType class created in the earlier assignments. You may choose to implement the functions in Binary Tree class iteratively or recursively. As with the previous assignments, you may create additional functions to implement the features asked in the document. Once all functions have been implemented for the Binary Tree class, you will create a Main application that initializes a tree based on file input and allows the user to interactively modify the tree based on the given commands. Finally, make sure to properly document all the code with comments, and make sure that your output exactly matches the example output. 
Project Files: 
● ItemType.h and ItemType.cpp
● BinaryTree.h: 
    ○ Structures
        ■ Node structure that has following members 
               ● ItemType key 
               ● Node *left 
               ● Node *right 
    ○ Instance Variables: 
          ■ Node *root; 
          ■ int length; 
    ○ Public member functions: 
          ■ BinaryTree(); 
               ● Pre-Condition: None. 
               ● Post-Condition: Tree is initialized. 
          ■ ~BinaryTree(); 
               ● Pre-Condition: Tree has been initialized.
               ● Post-Condition: All node pointers freed, root points to null, and length equals 0. 
           ■ void insert(ItemType &key); 
                ● Pre-Condition: Tree and parameter key initialized. 
                ● Post-Condition: Insert a node with the value of key into the tree. No duplicates are allowed. 
           ■ void deleteItem(ItemType &key); 
                ● Pre-Condition: Tree and parameter key initialized. 
                ● Post-Condition: Remove a node with a key value equal to the parameter key’s value and decrement                                length, otherwise leave tree unchanged. In situations, where the node to be deleted has two children,                              replace the deleted node with its immediate predecessor. 
           ■ void retrieve(ItemType &item, bool &found) const; 
                 ● Pre-Condition: Tree, item, and found are all initialized. 
                 ● Post-Condition: item should refer to a key of a Node n in the tree where the value of n.key is equal to the                        value of item and found should be equal to true if n exists. Otherwise found should be equal to false. 
            ■ void preOrder() const; 
                 ● Pre-Condition: The tree has been initialized. 
                 ● Post-Condition: Print out the tree in pre-order. 
            ■ void inOrder() const; 
                 ● Pre-Condition: The tree has been initialized. 
                 ● Post-Condition: Print out the the tree in in-order. 
            ■ void postOrder() const; 
                 ● Pre-Condition: The tree has been initialized. 
                 ● Post-Condition: Print out the tree in post-order. 
            ■ int getLength() const; 
                 ● Pre-Condition: The tree has been initialized. 
                 ● Post-Condition: Return value of length. 
            ■ For the Bonus Question: void getSameLevelNonsiblings(ItemType &key); 
                 ● Pre-Condition: The tree and the parameter key has been initialized 
                 ● Post-Condition: Print the value of the nodes in the same level other than its own siblings. If no same level                        nodes that are not own siblings were found, print “No same level non siblings found”. 
                 ● The maximum time complexity should be O(n). 
● BinaryTree.cpp: 
     ○ Implement all the functions defined in the header file. 
● Main.cpp: 

Answer 1

//main.cpp
#include
#include
#include
#include
#include
#include
#include
#include "BinaryTree.h"

using namespace std;

int main(int argc, char *argv[]){

    BinaryTree list;
    ItemType item4;
    int input;
    fstream fs;/
    if(argv[1] != NULL){
        fs.open("/Users/swapnil/CLionProjects/BinarySearchTreeItemType/input.txt",fstream::in);
        if(fs.is_open()){
            fs >> input;
            while(!fs.eof()){
                ItemType item4(input);
                list.insert(item4);
                fs >> input;
            }
        }else{
            cout << "Failed to open the input file" << endl;
        }
    }

    cout << "Commands: insert (i), delete (d), retrieve (r), length (l), in-order (n),pre-order (p), post-order (o), quit (q), getSameLevelNonSiblings (c), quit (q)" << endl;
    cout << endl;
    while(true){

        string s1;
        cout << "Enter a command: ";
        getline(cin, s1);

        if(s1 == "q"){
            cout << "Quitting program.." << endl;
            exit(EXIT_SUCCESS);
        }else if(s1=="i"){
            cout << "Enter a number: ";
            int val;
            cin >> val;
            cin.ignore(1,'\n');
            ItemType item(val);
            list.insert(item);
            cout << endl;
            cout << "In-Order: ";
            list.inOrder();
            cout << endl;
        }else if(s1=="d"){
        
            cout << "Item to delete: ";
            int val;
            cin >> val;
            cin.ignore(1,'\n');
            ItemType item2(val);
            list.deleteItem(item2);
            cout << endl;
            cout << "In-Order: ";
            list.inOrder();
            cout << endl;
        }else if(s1=="r"){
            cout << "Item to be retrieved: ";
            int val;
            cin >> val;
            cin.ignore(1,'\n');
            ItemType item2(val);
            bool found = false;
            list.retrieve(item2, found);
            cout << endl;
        }else if(s1=="c"){
            cout << "Item to find level for: ";
            int val;
            cin >> val;
            cin.ignore(1,'\n');
            ItemType item3(val);
            list.getSameLevelNonSiblings(item3);
            cout << endl;
        }else if(s1=="o"){
            cout << "Post-Order: ";
            list.postOrder();
            cout << endl;
        }else if(s1=="p"){
            cout << "Pre-Order: ";
            list.preOrder();
            cout << endl;
        }else if(s1=="n"){
            cout << "In-Order: ";
            list.inOrder();
            cout << endl;
        }else if(s1=="l"){
            cout << "Length: " << list.getLength() << endl;
        }else{
            cout << "Command not recognized. Try again" << endl;
        }
        cout << endl;
    }

}

-----------------------------------------------------------------------------------------------------------------------------
//BinaryTree.cpp
#include "BinaryTree.h"
#include
#include
#include

using namespace std;

BinaryTree::BinaryTree(){
    length = 0;
    root = NULL;
}
BinaryTree::~BinaryTree(){
    clearAll(root);
}

void BinaryTree::clearAll(Node *tree){
    if(tree == NULL)
        return;
    if(tree->left !=NULL)
        clearAll(tree->left);
    if(tree->right !=NULL)
        clearAll(tree->right);
    delete tree;
    return;
}

void BinaryTree::insert(ItemType &key){
    bool found = false;
    putItem(key, root, found);
    if(found)
        length++;
}

void BinaryTree::putItem(ItemType item, Node*& node, bool& found){
    if(node==NULL){//base case
        node = new Node;
        node->right = NULL;
        node->left = NULL;
        node->key = item;
        found = true;
    }
    else if(item.getValue() < node->key.getValue()){
        putItem(item, node->left, found);
    }
    else if(item.getValue() > node->key.getValue()){
        putItem(item, node->right, found);
    }
    else{
        cout << "item already in tree." << endl;
        return;
    }
}

void BinaryTree::deleteItem(ItemType &key){
    bool found = false;
    retrieve(key, found);
    if(found){
        Delete(root, key);
        length--;
    }
}

void BinaryTree::Delete(Node*& root, ItemType& item){
    if(item.getValue()key.getValue())
        Delete(root->left, item);
    else if(item.getValue()>root->key.getValue())
        Delete(root->right, item);
    else
        DeleteNode(root);
}

void BinaryTree::DeleteNode(Node*& tree){
    ItemType data;
    Node* tempPtr;
    tempPtr = tree;
    if(tree->left==NULL){
        tree = tree->right;
        delete tempPtr;
    }
    else if(tree->right == NULL){
        tree = tree->left;
        delete tempPtr;
    }
    else{
        getPredecessor(tree->left, data);
        tree->key = data;
        Delete(tree->left, data);
    }
}

void BinaryTree::getPredecessor(Node*& node, ItemType& data){
    while(node->right != NULL){
        node = node->right;
    }
    data = node->key;
}

void BinaryTree::getSameLevelNonSiblings(ItemType &key){
    bool found = false;
    Node* node;
    int val2 = findLevel(key, root, 0);
    printSameLevelNonSiblings(root, key, val2+1, found);
    if(!found)
        cout << "No same level non siblings found" << endl;

}

void BinaryTree::printSameLevelNonSiblings(Node*& tree, ItemType& item, int level, bool &found){
    if(level < 2 || tree == NULL){
        return;
    }
    if(level ==2){
        if(tree->left == NULL)
            return;
        if(tree->right == NULL)
            return;
        if(tree->left->key.getValue() == item.getValue() || tree->right->key.getValue() == item.getValue())
            return;
        if(tree->left != NULL && tree->left->key.getValue() != item.getValue()){
            cout << tree->left->key.getValue() << " ";
            found = true;
        }
        if(tree->right != NULL && tree->right->key.getValue() != item.getValue()){
            cout << tree->right->key.getValue() << " ";
            found=true;
        }

    }
    else if(level >2){
        printSameLevelNonSiblings(tree->left, item, level-1, found);
        printSameLevelNonSiblings(tree->right, item, level-1, found);
    }

}

int BinaryTree::findLevel(ItemType& item, Node*& tree, int level){
    if(tree == NULL){
        return 0;
    }
    if(tree->key.getValue() == item.getValue())
        return level;
    int traverseLevel = findLevel(item, tree->left, level+1);
    if(traverseLevel !=0)
        return traverseLevel;
    else
        return findLevel(item, tree->right, level+1);
}

void BinaryTree::retrieve(ItemType &item, bool &found) {
    getItem(root, item, found);
    if(found)
        cout << "Item found in tree." << endl;
    else
        cout << "Item not in tree." << endl;
}

void BinaryTree::getItem(Node* node, ItemType& item, bool&found) {
    if(node==NULL)
        found = false;
    else if(item.getValue()< node->key.getValue())
        getItem(node->left, item, found);
    else if(item.getValue()>node->key.getValue())
        getItem(node->right, item, found);
    else{
        item = node->key;
        found = true;
    }
}

void BinaryTree::preOrder(){
    printPreOrder(root);
}

void BinaryTree::printPreOrder(Node* root){
    if(root != NULL){
        cout << root->key.getValue() << " ";
        printPreOrder(root->left);
        printPreOrder(root->right);
    }
}

void BinaryTree::inOrder(){
    printInOrder(root);
}

void BinaryTree::printInOrder(Node* root){
    if(root !=NULL){
        printInOrder(root->left);
        cout << root->key.getValue() << " ";
        printInOrder(root->right);
    }
}

void BinaryTree::postOrder(){
    printPostOrder(root);
}

void BinaryTree::printPostOrder(Node* root){
    if(root!=NULL){
        printPostOrder(root->left);
        printPostOrder(root->right);
        cout << root->key.getValue() << " ";
    }
}

int BinaryTree::getLength() const{
    return length;
}
-----------------------------------------------------------------------------------------------------------------------------
//BinaryTree.h
#include "ItemType.h"
#include "ItemType.cpp"

struct Node{
    ItemType key;
    Node *left;
    Node *right;
};

class BinaryTree{
public:
    BinaryTree();
    ~BinaryTree();
    void clearAll(Node* tree);
    void insert(ItemType &key);
    void deleteItem(ItemType &key);
    void retrieve(ItemType &item, bool &found);
    void getItem(Node* node, ItemType& item, bool&found);
    void putItem(ItemType item, Node*& node, bool& found);
    void preOrder();
    void inOrder();
    void printInOrder(Node* root);
    void printPreOrder(Node* root);
    void printPostOrder(Node* root);
    void getPredecessor(Node*& node, ItemType& data);
    void DeleteNode(Node*& tree);
    void Delete(Node*& root, ItemType& item);
    void postOrder();
    int getLength() const;
    int findLevel(ItemType& item, Node*& tree, int level);
    void printSameLevelNonSiblings(Node*& tree, ItemType& item, int level, bool&found);
    void getSameLevelNonSiblings(ItemType &key);
    Node *root;
private:
    int length;
};
-----------------------------------------------------------------------------------------------------------------------------
//ItemType.cpp
#include "ItemType.h"
#include
#include

using namespace std;
ItemType::ItemType(){}

ItemType::ItemType(int value){
    this->value = value;
}

void ItemType::print(){
    cout << getValue() << endl;
}

void ItemType::initialize(int number){
    this->value = number;
}

int ItemType::getValue() const{
    return value;
}

-----------------------------------------------------------------------------------------------------------------------------
//ItemType.h
#include
#pragma once

typedef enum {GREATER, LESS, EQUAL} Comparison;

class ItemType{

public:
    ItemType();
    ItemType(int value);
    void print();
    void initialize(int number);
    int getValue() const;
private:
    int value;

};