Problem A
Binary tree

For this lab you will create a struct that represents a binary node in a binary search tree. You will then create functions that operate on the tree. Note, it is not an object-oriented solution, there shall be no methods in the struct. Knowledge on binary trees are prerequisites for this course. If needed, do refresh your knowledge on binary trees. The assignment will give you practice on pointers, memory handling and references.

You shall upload two files named Complex.cpp and Complex.h containing the implementation of your solution.

Files

• bintree.h contains the struct and function headers

• bintree.cpp contains the function implementations

struct Node

  struct Node {
    int key;
    double data;
    Node * right;
    Node * left;
  };

functions

  void insert(Node * & p, int key, double to\_be\_inserted);  // Note: reference to pointer
  void remove(Node * & p, const int & key);
  const double & find(Node * p, const int & to\_be\_found);
  double & edit(Node * p, const int & to\_be\_changed);
  void delete\_tree(Node * & p);

  unsigned int max\_height(Node * p);
  unsigned int min\_height(Node * p);
  unsigned int size(Node * p);
  bool is\_balanced(Node * p);

You may improve the parameter names and cv-qualifiers in the code above.

In addition you could implement additional data types or help functions such as print_tree or look_for_maximum_replacement.

Implementation

Appropriate functions shall throw std::out_of_range if the key looked for is not in the tree.

• insert - Inserts key and value in the binary tree, initialize the new nodes left and right to nullptr. If the key already exists the value is overwritten, duplicate keys are not allowed. Key is required to have implemented operator<

• find - Find the node with key and returns it associated data.

• edit - Find and return a reference to editable data associated with the key.

• delete_tree - Deletes the entire tree at p.

• max_height - returns the height (longest chain) of the tree

• min_height - returns the shortest chain of the tree

• size - returns the number of nodes (p included) in the tree

• is_balanced - returns true if the tree is balanced

• remove - Remove the node with this key. If the node has two children you need to either find the maximum node to left or the minimum node to the right. Copy that node to the node with the key to be deleted and remove the found minimum/maximum node instead.

  Example: remove key M (top node) from the following tree. Look for
  the biggest key in the left sub tree which is K
  
            M
      B         R
    A   D
          K
         H
  
  
  Copy that (K) nodes data to the top node
  
            K
      B         R
    A   D
          K
         H
  
  Now remove the node with K. In this example that node have only one child (H)
  which, when K is deleted, would be moved upwards.
  
            K
      B         R
    A   D
          H
  
  Be aware that you need to adjust D's right pointer (call remove with the approriate
  pointer) in the D node so its right pointer is properly adjusted after removal of K.