Question

The one missing piece was inserting into a binary search tree; we'll take care of that today and write the insert function, as well as a height function. Both functions will be implemented in the "bst.h" header file, and tested using a provided main program in "main.cpp".

Step one is to implement the insert function --- go ahead and modify "bst.h", adding the necessary code to (1) allocate a new node, and (b) link it into the tree. Once you have insert implemented, test your work using Codio's interactive terminal window. In this exercise we are building a tree of strings, with "#" as the sentinel. Example:

mom

dad

pizza

apple

uncle

aunt

#

Size: 6

Inorder: apple aunt dad mom pizza uncle

Height: 3

You'll know the tree is built properly if the inorder output is in sorted order --- if not, then your insert function is not linking the new nodes into the tree correctly. Ignore the height for now (which is probably displayed as -1).

Once insert is working, step two is to implement the height function in "bst.h". Since height needs to recursively traverse the entire tree, you'll want to take a public-private approach where a private helper function does the actual work of computing the height.

Here is the main.cpp:

#include <iostream>
#include <string>

#include "bst.h"

using namespace std;

int main()
{
binarysearchtree<string> tree;
string key;

//
// 1. Inputs values from the keyboard and builds a binary search
// tree; reads input until the sentinel ("#") is input. The
// resulting binary search tree is returned.
//
cin >> key;

while (key != "#")
{
tree.insert(key);

cin >> key;
}

//
// 2. Output size and contents (in order):
//
cout << "Size: " << tree.size() << endl;
tree.inorder();

//
// 3. Output height:
//
cout << "Height: " << tree.height() << endl;

// done:
return 0;
}

Here is the bst.h:

#pragma once

#include <iostream>
#include <algorithm> // std::max

using namespace std;

template<typename TKey>
class binarysearchtree
{
private:
struct NODE
{
TKey Key;
NODE* Left;
NODE* Right;
};

NODE* Root; // pointer to root node of tree (nullptr if empty)
int Size; // # of nodes in the tree (0 if empty)

//
// _inorder does the actual inorder traversal and output
// to console. Each key is output to the console followed
// by " ", including the last key.
//
void _inorder(NODE* cur)
{
if (cur == nullptr)
return;
else
{
_inorder(cur->Left);
cout << cur->Key << " ";
_inorder(cur->Right);
}
}

public:
//
// default constructor:
//
// Creates an empty tree.
//
binarysearchtree()
{
Root = nullptr;
Size = 0;
}

//
// size:
//
// Returns the # of nodes in the tree, 0 if empty.
//
int size()
{
return Size;
}

//
// height
//
// Computes and returns height of tree; height of an empty tree is
// defined as -1.
//
int height()
{
//
// TODO:
//
  
return -1;
}

//
// search:
//
// Searches the tree for the given key, returning true if found
// and false if not.
//
bool search(TKey key)
{
NODE* cur = Root;

while (cur != nullptr)
{
if (key == cur->Key) // already in tree
return true;

if (key < cur->Key) // search left:
{
cur = cur->Left;
}
else
{
cur = cur->Right;
}
}//while
  
// if get here, not found
return false;
}

//
// insert
//
// Inserts the given key into the tree; if the key has already been insert then
// the function returns without changing the tree.
//
void insert(TKey key)
{
NODE* prev = nullptr;
NODE* cur = Root;

//
// 1. Search to see if tree already contains key:
//
while (cur != nullptr)
{
if (key == cur->Key) // already in tree
return;

if (key < cur->Key) // search left:
{
prev = cur;
cur = cur->Left;
}
else
{
prev = cur;
cur = cur->Right;
}
}//while

//
// 2. if we get here, key is not in tree, so allocate
// a new node to insert:
//

//
// TODO: allocate a new node, store key, initialize
// pointer fields:
//

//
// 3. link in the new node:
//
// NOTE: cur is null, and prev denotes node where
// we fell out of the tree. if prev is null, then
// the tree is empty and the Root pointer needs
// to be updated.
//

//
// TODO: link in the new node, updating Root
// pointer as appropriate
//

//
// 4. update size and we're done:
//
  
//
// TODO:
//
}

//
// inorder:
//
// Performs an inorder traversal of the tree, outputting
// the keys to the console.
//
void inorder()
{
cout << "Inorder: ";

_inorder(Root);

cout << endl;
}

};

Answer 1

See the modified bst.h file

bst.h

#pragma once

#include <iostream>

#include <algorithm> // std::max

using namespace std;

template<typename TKey>

class binarysearchtree

{

private:

struct NODE

{

TKey Key;

NODE* Left;

NODE* Right;

};

NODE* Root; // pointer to root node of tree (nullptr if empty)

int Size; // # of nodes in the tree (0 if empty)

//

// _inorder does the actual inorder traversal and output

// to console. Each key is output to the console followed

// by " ", including the last key.

//

void _inorder(NODE* cur)

{

if (cur == nullptr)

return;

else

{

_inorder(cur->Left);

cout << cur->Key << " ";

_inorder(cur->Right);

}

}

public:

//

// default constructor:

//

// Creates an empty tree.

//

binarysearchtree()

{

Root = nullptr;

Size = 0;

}

//

// size:

//

// Returns the # of nodes in the tree, 0 if empty.

//

int size()

{

return Size;

}

//

// height

//

// Computes and returns height of tree; height of an empty tree is

// defined as -1.

//

int height(NODE *p)

{

if (p == nullptr)

return -1;

else

return 1 + max(height(p->Left), height(p->Right));

}

int height()

{

return height(Root);

}

//

// search:

//

// Searches the tree for the given key, returning true if found

// and false if not.

//

bool search(TKey key)

{

NODE* cur = Root;

while (cur != nullptr)

{

if (key == cur->Key) // already in tree

return true;

if (key < cur->Key) // search left:

{

cur = cur->Left;

}

else

{

cur = cur->Right;

}

}//while

// if get here, not found

return false;

}

//

// insert

//

// Inserts the given key into the tree; if the key has already been insert then

// the function returns without changing the tree.

//

void insert(NODE *tr, TKey key)

{

if (tr == NULL)

{

tr = new NODE;

tr->Key = key;

tr->Left = NULL;

tr->Right = NULL;

return;

}

if (tr->Key == key)

{

return;

}

if (tr->Key > key)

{

if (tr->Left != NULL)

{

insert(tr->Left, key);

}

else

{

tr->Left = new NODE;

tr->Left->Key = key;

(tr->Left)->Left = NULL;

(tr->Left)->Right = NULL;

return;

}

}

else

{

if (tr->Right != NULL)

{

insert(tr->Right, key);

}

else

{

tr->Right = new NODE;

tr->Right->Key = key;

(tr->Right)->Left = NULL;

(tr->Right)->Right = NULL;

return;

}

}

}

void insert(TKey key)

{

NODE* prev = nullptr;

NODE* cur = Root;

if (Root == nullptr)

{

Root = new NODE;

Root->Key = key;

Root->Left = NULL;

Root->Right = NULL;

}else{

insert(cur,key);

}

++Size;

}

//

// inorder:

//

// Performs an inorder traversal of the tree, outputting

// the keys to the console.

//

void inorder()

{

cout << "Inorder: ";

_inorder(Root);

cout << endl;

}

};

===================================================================

SEE OUTPUT



Thanks, PLEASE COMMENT if there is any concern.