# Lab 7: Binary Search Trees # For this lab, you will be implementing a Binary Search Tree to store integers and do various operations on the tree. A tree is a data structure very similar to a doubly linked list, but instead of linking back and forth, the node pointers point to nodes one layer deeper. The way data is input into the tree also sorts the data by design. ### Lab Instructions ### You will be writing all of the code for the implementation of a tree. You can use any helper functions you would like, but all of the functions that are provided to you need to do the functions that are commented above them. Every function than can be implemented with recursion, needs to be implemented with it. Check out the example recursive function `print_gtl()` for an idea of how to accomplish this. Take note of the auxilary functions 

#include "../inc/tree.h" #include  namespace lab7 { void clear(node *to_clear); // Construct an empty tree tree::tree() { root = nullptr; } // Deconstruct tree tree::~tree() { clear(root); } // Insert void tree::insert(int value) { } // Remove key bool tree::remove(int key) { } // What level is key on? int tree::level(int key) { } // Print the path to the key, starting with root void tree::path_to(int key) { } // Number of items in the tree unsigned tree::size() { } // Calculate the depth of the tree, longest string of connections unsigned tree::depth() { } // Determine whether the given key is in the tree bool tree::in_tree(int key) { } // Return the number of times that value is in the tree int tree::get_frequency(int key) { } // Return a vector with all of the nodes that are greater than the input key in the tree std::vector<int> tree::values_above(int key) { } // Print the tree least to greatest, Include duplicates void tree::print() { } // Print the tree least to greatest, Include duplicates std::ostream &operator<<(std::ostream &stream, tree &RHS) { } // Operator= Overload. Allowing for copying of trees tree &tree::operator=(const tree &rhs) { } /* * Extra credit functions */ // Merge rhs into this. Demo to a TA for credit tree tree::operator+(const tree &rhs) const { } // Balance the tree using any published algorithm. Demo to a TA for credit void tree::balance() { } /* * Recursion Example * Print the linked list from greatest to least using recursion */ // Auxiliary functions void node_print_gtl(node *top) { if (top == nullptr) return; node_print_gtl(top->right); for (int i = 0; i < top->frequency; i++) std::cout << top->data << " "; node_print_gtl(top->left); } void clear(node *to_clear) { if (to_clear == nullptr) return; if (to_clear->left != nullptr) clear(to_clear->left); if (to_clear->right != nullptr) clear(to_clear->right); delete to_clear; } // Class function void tree::print_gtl() { node_print_gtl(root); std::cout << std::endl; } }

header:

#ifndef CMPE126S18_LABS_NODE_H #define CMPE126S18_LABS_NODE_H namespace lab7{ class node{ public: node *left, *right; // Pointers to the left and right children int data; // Integer that is stored in the tree unsigned frequency; // Frequency of that integer in the tree explicit node(int input_data) : data(input_data), frequency(1), left(nullptr), right(nullptr) {} }; } #endif //CMPE126S18_LABS_NODE_H

node header:

#ifndef CMPE126S18_LABS_TREE_H #define CMPE126S18_LABS_TREE_H #include "node.h" #include  #include  namespace lab7 { class tree { node *root; unsigned tree_size; public: tree(); tree(const tree& copy); ~tree(); void insert(int value); bool remove(int key); bool in_tree(int key); int get_frequency(int key); int level(int key); void path_to(int key); std::vector<int> values_above(int key); unsigned size(); unsigned depth(); void print(); tree& operator=(const tree &rhs); friend std::ostream& operator<<(std::ostream& stream, tree& RHS); // Extra credit tree operator+(const tree &rhs) const; void balance(); // Example recursion void print_gtl(); }; } #endif //CMPE126S18_LABS_TREE_H