In: Computer Science
Please comments this C++ code and show screenshots of the outputs
main.cpp
#include<iostream>
#include<vector>
#include<string>
#include"BST.h"
#include"BST.cpp"
using namespace std;
std::vector<std::string> tokenize(char line[])
{
std::vector<std::string> tok;
std::string word = "";
for (int i = 0; i <
strlen(line); i++)
{
if (i ==
strlen(line) - 1)
{
word += line[i];
tok.push_back(word);
return tok;
}
else if (line[i]
== ' ')
{
tok.push_back(word);
word = "";
continue;
}
word +=
line[i];
}
return tok;
}
int main()
{
char line[100];
cout << "Enter a line: ";
cin.getline(line, sizeof(line));
vector<string> tokens = tokenize(line);
cout << "********** TOKENS **********" <<
endl;
for (auto token : tokens)
{
cout << token <<
endl;
}
cout << "****************************" <<
endl << endl;
BST<string> T1;
for (auto token : tokens)
T1.insert(token);
cout << "************ T1 ************"
<< endl;
T1.postOrder();
cout << "****************************" <<
endl;
cout << "T1 Leaf Nodes = " << T1.CLeaves()
<< endl;
cout << "T1 Height = " << T1.height()
<< endl;
cout << "****************************" <<
endl << endl;
BST<string> T2;
vector<string> T2x = T1.getPostOrder();
for (auto token : T2x)
T2.insert(token);
cout << "************ T2 ************"
<< endl;
T2.preOrder();
cout << "****************************" <<
endl;
cout << "T2 Leaf Nodes = " << T2.CLeaves()
<< endl;
cout << "T2 Height = " << T2.height()
<< endl;
cout << "****************************" <<
endl << endl;
BST<string> T3;
vector<string> T3x = T2.getPreOrder();
for (auto token : T3x)
T3.insert(token);
cout << "************ T3 ************"
<< endl;
T3.inOrder();
cout << "****************************" <<
endl;
cout << "T3 Leaf Nodes = " << T3.CLeaves()
<< endl;
cout << "T3 Height = " << T3.height()
<< endl;
cout << "****************************" <<
endl << endl;
return 0;
}
BST.CPP
#include "BST.h"
template <typename gen>
void BST<gen>::insert(gen x)
{
insert(root, x);
}
template <typename gen>
bool BST<gen>::remove(string value)
{
return remove(NULL, root, value);
}
template <typename gen>
void BST<gen>::preOrder()
{
preOrder(root);
}
template <typename gen>
void BST<gen>::postOrder()
{
postOrder(root);
}
template <typename gen>
void BST<gen>::inOrder()
{
inOrder(root);
}
template <typename gen>
vector<string> BST<gen>::getPreOrder()
{
vector<string> temp;
getPreOrder(root, temp);
return temp;
}
template <typename gen>
vector<string> BST<gen>::getPostOrder()
{
vector<string> temp;
getPostOrder(root, temp);
return temp;
}
template <typename gen>
vector<string> BST<gen>::getInOrder()
{
vector<string> temp;
getInOrder(root, temp);
return temp;
}
template <typename gen>
int BST<gen>::CLeaves()
{
int s = 0;
CLeaves(root, s);
return s;
}
template <typename gen>
int BST<gen>::height()
{
return HeightL(root);
}
template <typename gen>
void BST<gen>::DestroyRecursive(BNode<gen>* node)
{
if (node)
{
DestroyRecursive(node->LChild);
DestroyRecursive(node->RChild);
delete node;
}
}
template <typename gen>
BST<gen>::~BST()
{
DestroyRecursive(root);
root = nullptr;
}
template <typename gen>
void BST<gen>::insert(BNode<gen>*& t, gen x)
{
if (!t) { t = new BNode<gen>; t->data = x;
t->LChild = t->RChild = nullptr; }
else if (x < t->data)
insert(t->LChild, x);
else
insert(t->RChild, x);
}
template <typename gen>
void BST<gen>::preOrder(BNode<gen>* t) {
if (t) {
cout << t->data <<
"\n";
preOrder(t->LChild);
preOrder(t->RChild);
}
}
template <typename gen>
void BST<gen>::postOrder(BNode<gen>* t) {
if (t) {
postOrder(t->LChild);
postOrder(t->RChild);
cout << t->data <<
"\n";
}
}
template <typename gen>
void BST<gen>::inOrder(BNode<gen>* t) {
if (t) {
inOrder(t->LChild);
cout << t->data <<
"\n";
inOrder(t->RChild);
}
}
template <typename gen>
void BST<gen>::getPreOrder(BNode<gen>* t,
vector<string>& temp) {
if (t) {
temp.push_back(t->data);
getPreOrder(t->LChild,
temp);
getPreOrder(t->RChild,
temp);
}
}
template <typename gen>
void BST<gen>::getPostOrder(BNode<gen>* t,
vector<string>& temp) {
if (t) {
getPostOrder(t->LChild,
temp);
getPostOrder(t->RChild,
temp);
temp.push_back(t->data);
}
}
template <typename gen>
void BST<gen>::getInOrder(BNode<gen>* t,
vector<string>& temp) {
if (t) {
getInOrder(t->LChild,
temp);
temp.push_back(t->data);
getInOrder(t->RChild,
temp);
}
}
template <typename gen>
int BST<gen>::HeightL(BNode<gen>* P) {
if (P == NULL)
return 0;
else
{
/* compute the depth of each
subtree */
int lDepth =
HeightL(P->LChild);
int rDepth =
HeightL(P->RChild);
/* use the larger one */
if (lDepth > rDepth)
return(lDepth +
1);
else return(rDepth + 1);
}
}
template <typename gen>
void BST<gen>::CLeaves(BNode<gen>* P, int& s)
{
if (P) {
if (IsLeaf(P))
s++;
CLeaves(P->LChild, s);
CLeaves(P->RChild, s);
}
}
BST.h
#pragma once
#include<iostream>
#include<vector>
#include<Windows.h>
using namespace std;
template <typename gen>
struct BNode
{
gen data;
BNode<gen>* RChild;
BNode<gen>* LChild;
BNode()
{
RChild = nullptr;
LChild = nullptr;
}
};
template <class gen>
class BST
{
public:
BST()
{
root = nullptr;
}
void insert(gen x);
bool remove(string value);
void preOrder();
void postOrder();
void inOrder();
vector<string> getPreOrder();
vector<string> getPostOrder();
vector<string> getInOrder();
int CLeaves();
int height();
void DestroyRecursive(BNode<gen>* node);
~BST();
private:
BNode<gen>* root;
void insert(BNode<gen>*& t, gen x);
void preOrder(BNode<gen>* t);
void postOrder(BNode<gen>* t);
void inOrder(BNode<gen>* t);
void getPreOrder(BNode<gen>* t,
vector<string>& temp);
void getPostOrder(BNode<gen>* t,
vector<string>& temp);
void getInOrder(BNode<gen>* t,
vector<string>& temp);
int HeightL(BNode<gen>* P);
bool IsLeaf(BNode<gen>* P)
{
return (!(P->LChild) &&
!(P->RChild));
}
void CLeaves(BNode<gen>* P, int& s);
};
text.file
Enter a line: this is a line and it is with spaces and without
semicolons
********** TOKENS **********
this
is
a
line
and
it
is
with
spaces
and
without
semicolons
****************************
************ T1 ************
and
and
a
is
it
semicolons
spaces
line
is
without
with
this
****************************
T1 Leaf Nodes = 4
T1 Height = 5
****************************
************ T2 ************
and
a
and
is
it
is
semicolons
line
spaces
without
with
this
****************************
T2 Leaf Nodes = 4
T2 Height = 9
****************************
************ T3 ************
a
and
and
is
is
it
line
semicolons
spaces
this
with
without
****************************
T3 Leaf Nodes = 4
T3 Height = 9
****************************
main.cpp
#include<iostream>
#include<vector>
#include<string>
#include"BST.h"
#include"BST.cpp"
using namespace std;
std::vector<std::string> tokenize(char line[])
{
std::vector<std::string> tok;
std::string word = "";
for (int i = 0; i <
strlen(line); i++)
{
if (i ==
strlen(line) - 1)
{
word += line[i];
tok.push_back(word);
return tok;
}
else if (line[i]
== ' ')
{
tok.push_back(word);
word = "";
continue;
}
word +=
line[i];
}
return tok;
}
int main()
{
char line[100];
cout << "Enter a line: ";
cin.getline(line, sizeof(line));
vector<string> tokens = tokenize(line);
cout << "********** TOKENS **********" <<
endl;
for (auto token : tokens)
{
cout << token <<
endl;
}
cout << "****************************" <<
endl << endl;
BST<string> T1;
for (auto token : tokens)
T1.insert(token);
cout << "************ T1 ************"
<< endl;
T1.postOrder();
cout << "****************************" <<
endl;
cout << "T1 Leaf Nodes = " << T1.CLeaves()
<< endl;
cout << "T1 Height = " << T1.height()
<< endl;
cout << "****************************" <<
endl << endl;
BST<string> T2;
vector<string> T2x = T1.getPostOrder();
for (auto token : T2x)
T2.insert(token);
cout << "************ T2 ************"
<< endl;
T2.preOrder();
cout << "****************************" <<
endl;
cout << "T2 Leaf Nodes = " << T2.CLeaves()
<< endl;
cout << "T2 Height = " << T2.height()
<< endl;
cout << "****************************" <<
endl << endl;
BST<string> T3;
vector<string> T3x = T2.getPreOrder();
for (auto token : T3x)
T3.insert(token);
cout << "************ T3 ************"
<< endl;
T3.inOrder();
cout << "****************************" <<
endl;
cout << "T3 Leaf Nodes = " << T3.CLeaves()
<< endl;
cout << "T3 Height = " << T3.height()
<< endl;
cout << "****************************" <<
endl << endl;
return 0;
}
BST.CPP
#include "BST.h"
template <typename gen>
void BST<gen>::insert(gen x)
{
insert(root, x);
}
template <typename gen>
bool BST<gen>::remove(string value)
{
return remove(NULL, root, value);
}
template <typename gen>
void BST<gen>::preOrder()
{
preOrder(root);
}
template <typename gen>
void BST<gen>::postOrder()
{
postOrder(root);
}
template <typename gen>
void BST<gen>::inOrder()
{
inOrder(root);
}
template <typename gen>
vector<string> BST<gen>::getPreOrder()
{
vector<string> temp;
getPreOrder(root, temp);
return temp;
}
template <typename gen>
vector<string> BST<gen>::getPostOrder()
{
vector<string> temp;
getPostOrder(root, temp);
return temp;
}
template <typename gen>
vector<string> BST<gen>::getInOrder()
{
vector<string> temp;
getInOrder(root, temp);
return temp;
}
template <typename gen>
int BST<gen>::CLeaves()
{
int s = 0;
CLeaves(root, s);
return s;
}
template <typename gen>
int BST<gen>::height()
{
return HeightL(root);
}
template <typename gen>
void BST<gen>::DestroyRecursive(BNode<gen>* node)
{
if (node)
{
DestroyRecursive(node->LChild);
DestroyRecursive(node->RChild);
delete node;
}
}
template <typename gen>
BST<gen>::~BST()
{
DestroyRecursive(root);
root = nullptr;
}
template <typename gen>
void BST<gen>::insert(BNode<gen>*& t, gen x)
{
if (!t) { t = new BNode<gen>; t->data = x;
t->LChild = t->RChild = nullptr; }
else if (x < t->data)
insert(t->LChild, x);
else
insert(t->RChild, x);
}
template <typename gen>
void BST<gen>::preOrder(BNode<gen>* t) {
if (t) {
cout << t->data <<
"\n";
preOrder(t->LChild);
preOrder(t->RChild);
}
}
template <typename gen>
void BST<gen>::postOrder(BNode<gen>* t) {
if (t) {
postOrder(t->LChild);
postOrder(t->RChild);
cout << t->data <<
"\n";
}
}
template <typename gen>
void BST<gen>::inOrder(BNode<gen>* t) {
if (t) {
inOrder(t->LChild);
cout << t->data <<
"\n";
inOrder(t->RChild);
}
}
template <typename gen>
void BST<gen>::getPreOrder(BNode<gen>* t,
vector<string>& temp) {
if (t) {
temp.push_back(t->data);
getPreOrder(t->LChild,
temp);
getPreOrder(t->RChild,
temp);
}
}
template <typename gen>
void BST<gen>::getPostOrder(BNode<gen>* t,
vector<string>& temp) {
if (t) {
getPostOrder(t->LChild,
temp);
getPostOrder(t->RChild,
temp);
temp.push_back(t->data);
}
}
template <typename gen>
void BST<gen>::getInOrder(BNode<gen>* t,
vector<string>& temp) {
if (t) {
getInOrder(t->LChild,
temp);
temp.push_back(t->data);
getInOrder(t->RChild,
temp);
}
}
template <typename gen>
int BST<gen>::HeightL(BNode<gen>* P) {
if (P == NULL)
return 0;
else
{
/* compute the depth of each
subtree */
int lDepth =
HeightL(P->LChild);
int rDepth =
HeightL(P->RChild);
/* use the larger one */
if (lDepth > rDepth)
return(lDepth +
1);
else return(rDepth + 1);
}
}
template <typename gen>
void BST<gen>::CLeaves(BNode<gen>* P, int& s)
{
if (P) {
if (IsLeaf(P))
s++;
CLeaves(P->LChild, s);
CLeaves(P->RChild, s);
}
}
BST.h
#pragma once
#include<iostream>
#include<vector>
#include<Windows.h>
using namespace std;
template <typename gen>
struct BNode
{
gen data;
BNode<gen>* RChild;
BNode
template <typename gen>
struct BNode
{
gen data;
BNode<gen>* RChild;
BNode
template <typename gen2>
struct BNode
{
gen data;
BNode<gen>* RChild;
BNode
template <typename gen1>
struct BNode
{
gen data;
BNode<gen>* RChild;
BNode
x=3