Question

The goal of this lab is to reinforce binary tree concepts. Specifically, this lab is to do construct a function (and construct a test program using a non-trivial tree) which will display a binary tree by levels showing “vacant spots”. The display for the following tree should be:

M

H T

E null P W

A null null null null Q null null

The function header should be:

template <typename T>

void display_complete_tree (const binary_tree_node<T>* t)

The files "bintree.h" and "bintree.template" are to be used, which are linked here:

https://www.cs.colorado.edu/~main/chapter10/bintree.h

https://www.cs.colorado.edu/~main/chapter10/bintree.template

PLEASE do not use struct node, use the provided template and header and incorporate the function header into the problem. thanks

Answer 1

Complete Test Program:

Sample Output:

CODE TO COPY:

File: main.cpp

// Header files section
#include "bintree.h"
#include <queue>
using namespace std;
using namespace main_savitch_10;

// function prototypes
binary_tree_node<char>* create_tree();
template<class T>
int getHeight(binary_tree_node<T>* node);
template<class T>
void display_complete_tree(binary_tree_node<T>* t);

// start main function
int main()
{
   binary_tree_node<char>* t = create_tree();
   display_complete_tree(t);
  
   return EXIT_SUCCESS;
} // end of main function

// create_tree function implementation
binary_tree_node<char>* create_tree()
{
   binary_tree_node<char>* t8 = new binary_tree_node<char>('Q');
   binary_tree_node<char>* t7 = new binary_tree_node<char>('A');  
   binary_tree_node<char>* t6 = new binary_tree_node<char>('W');
   binary_tree_node<char>* t5 = new binary_tree_node<char>('P', NULL, t8);  
   binary_tree_node<char>* t4 = new binary_tree_node<char>('E', t7, NULL);
   binary_tree_node<char>* t3 = new binary_tree_node<char>('T', t5, t6);
   binary_tree_node<char>* t2 = new binary_tree_node<char>('H', t4, NULL);
   binary_tree_node<char>* t1 = new binary_tree_node<char>('M', t2, t3);
  
   return t1;
} // end of create_tree function

// getHeight function implementation
template<class T>
int getHeight(binary_tree_node<T>* node)
{
   if (node == NULL)
   {
       return 0;
   }
   else
   {
       return (1 + max(getHeight(node->left()), getHeight(node->right())));
   }
} // end of getHeight function

// display_complete_tree function implementation
template<class T>
void display_complete_tree(binary_tree_node<T>* t)
{
   queue<binary_tree_node<T> *> q1;
   binary_tree_node<T> *current;

   bool isEmptyRow;

   q1.push(t);
   int height = getHeight(t);
   isEmptyRow = false;

   while (isEmptyRow == false)
   {
       queue<binary_tree_node<T> *> q2;
       isEmptyRow = true;

       while (q1.empty() == false)
       {
           current = q1.front();
           q1.pop();
           if (current != NULL)
           {
               cout << current->data() << " ";
               q2.push(current->left());
               q2.push(current->right());
               if (current->left() != NULL || current->right() != NULL)
                   isEmptyRow = false;
           }
           else
           {
               cout << "null ";
               q2.push(NULL);
               q2.push(NULL);
           }
       }

       cout << endl;

       while (q2.empty() == false)
       {
           q1.push(q2.front());
           q2.pop();
       }
   }
} // end of display_complete_tree function