I made a program that inserts values, sorts them using binary search, and outputs the sorted values. However, I also would like to use the function PrintTree() to print the tree. I can't think of any way to implement a functioning code in that function. Here is my code up until now.
#ifndef b_h
#define b_h
#include <iostream>
class BSTNode
{
public:
int Key;
BSTNode * Left;
BSTNode * Right;
BSTNode * Parent;
int Height;
};
class BST
{
private:
BSTNode * root;
BSTNode * insertKey(BSTNode * node, int newKey);
void PrintTreeInOrder(BSTNode * node);
BSTNode * hasKey(BSTNode * node, int searchKey);
public:
BST();
~BST();
void insertKey(int newKey);
void PrintTreeInOrder();
bool hasKey(int searchKey);
void TreePrint();
};
#endif
The header file above.
#include "b.h"
BST::BST() : root(NULL)
{
}
BSTNode * BST::insertKey(BSTNode * node, int newKey)
{
if(node == NULL)
{
node = new BSTNode;
node->Key = newKey;
node->Left = NULL;
node->Right = NULL;
node->Parent = NULL;
}
else if(node->Key < newKey)
{
node->Right = insertKey(node->Right, newKey);
node->Right->Parent = node;
}
else
{
node->Left = insertKey(node->Left, newKey);
node->Left->Parent = node;
}
return node;
}
void BST::insertKey(int newKey)
{
root = insertKey(root, newKey);
}
void BST::PrintTreeInOrder(BSTNode * node)
{
if(node == NULL)
return;
PrintTreeInOrder(node->Left);
std::cout << node->Key << " ";
PrintTreeInOrder(node->Right);
}
void BST::PrintTreeInOrder()
{
PrintTreeInOrder(root);
std::cout << std::endl;
}
BSTNode * BST::hasKey(BSTNode * node, int key)
{
if (node == NULL)
return NULL;
else if(node->Key == key)
return node;
else if(node->Key < key)
return hasKey(node->Right, key);
else
return hasKey(node->Left, key);
}
bool BST::hasKey(int searchKey)
{
BSTNode * result = hasKey(root, searchKey);
return result == NULL ?
false :
true;
}
The cpp file above.
#include <cstddef>
#include <iostream>
#include <vector>
#include <limits>
#include "b.h"
using namespace std;
int main()
{
cout << "Binary Search Tree" << endl;
BST * tree = new BST;
cout << "Enter the numbers to be stored (end with a letter): ";
int value;
int i = 0;
vector <int> keys;
cin >> value;
while (!cin.fail()){
keys.push_back(value);
cin >> value;
i++;
}
cin.clear(); // reset failbit
cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
for(const int& key : keys){
tree->insertKey(key);}
int number;
cout << "Which number do you want to look up? " <<endl;
cin >> number;
bool b = tree->hasKey(number);
if(b){
cout << number << " is in the tree: yes";}
else{
cout << number << " is in the tree: no";
cout << endl;}
cout << "The numbers in sorted order: ";
tree->PrintTreeInOrder();
tree->TreePrint();
return 0;
}
And the main.
This program works and it sorts the vector using binary search and has a search-for-key function, however, I want to print the tree in the function PrintTree(); as follows for example;
8
3 10
1 6 14
4 7 13
Can anyone help?