How to remove a node from an array-based binary tree in c++? I am studying and c

Question

How to remove a node from an array-based binary tree in c++?

I am studying and can't find a good answer.

Here is the code:

#include
#include
#include
using namespace std;
#ifndef BIN_TREE_H

// DECLARATION SECTION FOR THE BINARY TREE CLASS TEMPLATE
const int MAX_TREE_NODES = 15;

template class binary_tree
{
public:
   // Class constructors
   binary_tree();
   binary_tree(const binary_tree &bt);

   // Member functions
   bool isEmpty();
   void insert(const E &item);
   void preorder_traverse(int location);
   void inorder_traverse(int location);
   void postorder_traverse(int location);
   binary_tree& operator = (const binary_tree &bt);
   void display_array();
protected:
   // Data members
   struct node           // The node structure is
   {               // set up so that if the
       bool vacant;           // vacant field is FALSE,
       E data;           // then the data field is
   };               // irrelevant.

   node tree[MAX_TREE_NODES];   // Array of nodes
   int number_nodes;       // Number of nodes in tree

                           // Member function
   void insertStartingHere(const E &item, int location);
};

template
binary_tree::binary_tree()
{
   number_nodes = 0;
   for (int i = 0; i < MAX_TREE_NODES; i++)
       tree[i].vacant = true;
}

// Copy constructor. //
template
binary_tree::binary_tree(const binary_tree &bt)
{
   number_nodes = bt.number_nodes;
   for (int i = 0; i < MAX_TREE_NODES; i++)
       if (bt.tree[i].vacant)
           tree[i].vacant = true;
       else
           tree[i] = bt.tree[i];
}

// Assignment operator. //
template
binary_tree& binary_tree::operator = (const binary_tree &bt)
{
   number_nodes = bt.number_nodes;
   for (int i = 0; i < MAX_TREE_NODES; i++)
       if (bt.tree[i].vacant)
           tree[i].vacant = true;
       else
           tree[i] = bt.tree[i];
   return *this;
}

// Empty function. //
template
bool binary_tree::isEmpty()
{
   return (number_nodes == 0);
}

// Insert function; inserts via insertStartingHere function. //
template
void binary_tree::insert(const E &item)
{
   assert(number_nodes < MAX_TREE_NODES);   // Room in tree?
   insertStartingHere(item, 0);
   number_nodes++;
}

// Preorder_traverse function; prints tree contents in preorder. //
template
void binary_tree::preorder_traverse(int location)
{
   if ((location < MAX_TREE_NODES) && (!tree[location].vacant))
   {
       cout << tree[location].data << ' ';
       preorder_traverse(2 * location + 1);
       preorder_traverse(2 * location + 2);
   }
   return;
}

/////////////////////////////////////////////////////////////////
// Inorder_traverse function; prints tree contents in inorder. //
/////////////////////////////////////////////////////////////////
template
void binary_tree::inorder_traverse(int location)
{
   if ((location < MAX_TREE_NODES) && (!tree[location].vacant))
   {
       inorder_traverse(2 * location + 1);
       cout << tree[location].data << ' ';
       inorder_traverse(2 * location + 2);
   }
   return;
}

/////////////////////////////////////////////////////////////////////
// Postorder_traverse function; prints tree contents in postorder. //
/////////////////////////////////////////////////////////////////////
template
void binary_tree::postorder_traverse(int location)
{
   if ((location < MAX_TREE_NODES) && (!tree[location].vacant))
   {
       postorder_traverse(2 * location + 1);
       postorder_traverse(2 * location + 2);
       cout << tree[location].data << ' ';
   }
   return;
}

// Display_array function; prints tree contents as an //
// array, printing the word vacant if a node is vacant. //
template
void binary_tree::display_array()
{
   int index;
   for (int i = 0; i < MAX_TREE_NODES / 5; i++)
   {
       for (int j = 0; j < 5; j++)
       {
           index = (MAX_TREE_NODES / 5)*j + i;
           cout << setw(2) << index << " = ";
           if (tree[index].vacant)
               cout << setw(6) << "vacant" << setw(3) << "";
           else
               cout << setw(6) << tree[index].data << setw(3) << "";
       }
       cout << endl;
   }
}

template
void binary_tree::insertStartingHere(const E &item, int location)
{
   assert(location < MAX_TREE_NODES); // Must be legitimate
                                       // array index
   if (tree[location].vacant)
   {
       tree[location].data = item;
       tree[location].vacant = false;
   }
   else if (item < tree[location].data)
       insertStartingHere(item, 2 * location + 1);
   else
       insertStartingHere(item, 2 * location + 2);
}

#define BIN_TREE_H
#endif

Explanation / Answer

PROGRAM CODE:

#include
#include
#include
using namespace std;
#ifndef BIN_TREE_H

// DECLARATION SECTION FOR THE BINARY TREE CLASS TEMPLATE
const int MAX_TREE_NODES = 15;
template class binary_tree
{
public:
// Class constructors
binary_tree();
binary_tree(const binary_tree &bt);
// Member functions
bool isEmpty();
void insert(const E &item);
void preorder_traverse(int location);
void inorder_traverse(int location);
void postorder_traverse(int location);
binary_tree& operator = (const binary_tree &bt);
void display_array();
void remove(E &item);
protected:
// Data members
struct node // The node structure is
{ // set up so that if the
bool vacant; // vacant field is FALSE,
E data; // then the data field is
}; // irrelevant.
node tree[MAX_TREE_NODES]; // Array of nodes
int number_nodes; // Number of nodes in tree
// Member function
void insertStartingHere(const E &item, int location);
};

template
binary_tree::binary_tree()
{
number_nodes = 0;
for (int i = 0; i < MAX_TREE_NODES; i++)
tree[i].vacant = true;
}
// Copy constructor. //
template
binary_tree::binary_tree(const binary_tree &bt)
{
number_nodes = bt.number_nodes;
for (int i = 0; i < MAX_TREE_NODES; i++)
if (bt.tree[i].vacant)
tree[i].vacant = true;
else
tree[i] = bt.tree[i];
}
// Assignment operator. //
template
binary_tree& binary_tree::operator = (const binary_tree &bt)
{
number_nodes = bt.number_nodes;
for (int i = 0; i < MAX_TREE_NODES; i++)
if (bt.tree[i].vacant)
tree[i].vacant = true;
else
tree[i] = bt.tree[i];
return *this;
}
// Empty function. //
template
bool binary_tree::isEmpty()
{
return (number_nodes == 0);
}
// Insert function; inserts via insertStartingHere function. //
template
void binary_tree::insert(const E &item)
{
assert(number_nodes < MAX_TREE_NODES); // Room in tree?
insertStartingHere(item, 0);
number_nodes++;
}
// Preorder_traverse function; prints tree contents in preorder. //
template
void binary_tree::preorder_traverse(int location)
{
if ((location < MAX_TREE_NODES) && (!tree[location].vacant))
{
cout << tree[location].data << ' ';
preorder_traverse(2 * location + 1);
preorder_traverse(2 * location + 2);
}
return;
}
/////////////////////////////////////////////////////////////////
// Inorder_traverse function; prints tree contents in inorder. //
/////////////////////////////////////////////////////////////////
template
void binary_tree::inorder_traverse(int location)
{
if ((location < MAX_TREE_NODES) && (!tree[location].vacant))
{
inorder_traverse(2 * location + 1);
cout << tree[location].data << ' ';
inorder_traverse(2 * location + 2);
}
return;
}
/////////////////////////////////////////////////////////////////////
// Postorder_traverse function; prints tree contents in postorder. //
/////////////////////////////////////////////////////////////////////
template
void binary_tree::postorder_traverse(int location)
{
if ((location < MAX_TREE_NODES) && (!tree[location].vacant))
{
postorder_traverse(2 * location + 1);
postorder_traverse(2 * location + 2);
cout << tree[location].data << ' ';
}
return;
}
// Display_array function; prints tree contents as an //
// array, printing the word vacant if a node is vacant. //
template
void binary_tree::display_array()
{
int index;
for (int i = 0; i < MAX_TREE_NODES / 5; i++)
{
for (int j = 0; j < 5; j++)
{
index = (MAX_TREE_NODES / 5)*j + i;
cout << setw(2) << index << " = ";
if (tree[index].vacant)
cout << setw(6) << "vacant" << setw(3) << "";
else
cout << setw(6) << tree[index].data << setw(3) << "";
}
cout << endl;
}
}
template
void binary_tree::insertStartingHere(const E &item, int location)
{
assert(location < MAX_TREE_NODES); // Must be legitimate
// array index
if (tree[location].vacant)
{
tree[location].data = item;
tree[location].vacant = false;
}
else if (item < tree[location].data)
insertStartingHere(item, 2 * location + 1);
else
insertStartingHere(item, 2 * location + 2);
}

template
void binary_tree::remove(E &item, int location)
{
assert(location < MAX_TREE_NODES);
  
if (item == tree[location].data)
{
   tree[location].vacant = true;
   return;
}
else if (item < tree[location].data)
remove(item, 2 * location + 1);
else
remove(item, 2 * location + 2);
}
#define BIN_TREE_H
#endif

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.