I'm trying to put all the elements from a binary search tree into a vector, in order. Here is the function:
edit: adding instructions for clarity. Write a class for implementing a simple binary search tree capable of storing numbers. The class should have member functions:
void insert(double x)
bool search(double x)
void inorder(vector <double> & v)
The insert function should not use recursion directly or indirectly by calling a recursive function. The search function should work by calling a private recursive member function
bool search(double x, <double> & v )
The inorder function is passed an initially empty vector v; if fills v with the inorder list of numbers stored in the binary search tree. Demonstrate the operation of the class using a suitable driver program.
EDIT: Added full code for clarity.
#include "stdafx.h"
#include <iostream>
#include <vector>
class BinaryTree {
private:
struct TreeNode {
double value;
TreeNode *left;
TreeNode *right;
TreeNode(double value1,
TreeNode *left1 = nullptr,
TreeNode *right1 = nullptr) {
value = value1;
left = left1;
right = right1;
}
};
TreeNode *root; //pointer to the root of the tree
bool search(double x, TreeNode *t) {
while (t) {
std::cout << "running through t." << std::endl;
if (t->value == x) {
return true;
}
else if (x < t->value) {
std::cout << "wasn't found, moving left." << std::endl;
search(x, t->left);
}
else {
std::cout << "wasn't found, moving right." << std::endl;
search(x, t->right);
}
}
std::cout << "wasn't found." << std::endl;
return false;
}
public:
std::vector<TreeNode> v;
BinaryTree() {
root = nullptr;
}
void insert(double x) {
TreeNode *tree = root;
if (!tree) {
std::cout << "Creating tree." << x << std::endl;
root = new TreeNode(x);
return;
}
while (tree) {
std::cout << "Adding next value." << std::endl;
if (tree->value == x) return;
if (x < tree->value) {
tree = tree->left;
tree->value = x;
}
else {
tree = tree->right;
tree->value = x;
}
}
}
bool search(double x) {
return search(x, root);
}
void inOrder(std::vector <double> & v) {
{
if (left)
left->inOrder(v);
v.push_back(value);
if (right)
right->inOrder(v);
}
}
TreeNode* left = nullptr;
TreeNode* right = nullptr;
double value;
};
int main() {
BinaryTree t;
std::cout << "Inserting the numbers 5, 8, 3, 12, and 9." << std::endl;
t.insert(5);
t.insert(8);
t.insert(3);
t.insert(12);
t.insert(9);
std::cout << "Looking for 12 in tree." << std::endl;
if (t.search(12)) {
std::cout << "12 was found." << std::endl;
}
std::cout << "Here are the numbers in order." << std::endl;
return 0;
}
I'm unable to get the values to push into the vector. Any ideas as to how I can accomplish this?
You would normally do this recursively:
#include <vector>
class TreeNode {
void inOrder(std::vector<double>& v) const
{
if (left)
left->inOrder(v);
v.push_back(value);
if (right)
right->inOrder(v);
}
TreeNode* left = nullptr;
TreeNode* right = nullptr;
double value;
};
Edit: added #include <vector>
Edit2: That is how I would do it. Feel free to ask any questions:
#include <iostream>
#include <vector>
class BinaryTree {
private:
struct TreeNode {
double value;
TreeNode *left = nullptr;
TreeNode *right = nullptr;
TreeNode(double value1)
: value(value1)
{}
void inOrder(std::vector <double> & v) {
if (left)
left->inOrder(v);
v.push_back(value);
if (right)
right->inOrder(v);
}
};
TreeNode *root = nullptr; //pointer to the root of the tree
bool search(double x, TreeNode *t) {
while (t) {
std::cout << "running through t." << std::endl;
if (t->value == x) {
return true;
}
else if (x < t->value) {
std::cout << "wasn't found, moving left." << std::endl;
return search(x, t->left);
}
else {
std::cout << "wasn't found, moving right." << std::endl;
return search(x, t->right);
}
}
std::cout << "wasn't found." << std::endl;
return false;
}
public:
BinaryTree() {}
void insert(double x) {
TreeNode *tree = root;
if (!tree) {
std::cout << "Creating tree." << x << std::endl;
root = new TreeNode(x);
return;
}
while (tree) {
std::cout << "Adding next value." << std::endl;
if (tree->value == x) return;
if (x < tree->value) {
if (!tree->left)
{
tree->left = new TreeNode(x);
return;
}
tree = tree->left;
}
else {
if (!tree->right)
{
tree->right = new TreeNode(x);
return;
}
tree = tree->right;
}
}
}
bool search(double x) {
return search(x, root);
}
void inOrder(std::vector<double>& v)
{
root->inOrder(v);
}
};
int main() {
BinaryTree t;
std::cout << "Inserting the numbers 5, 8, 3, 12, and 9." << std::endl;
t.insert(5);
t.insert(8);
t.insert(3);
t.insert(12);
t.insert(9);
std::cout << "Looking for 12 in tree." << std::endl;
if (t.search(12)) {
std::cout << "12 was found." << std::endl;
}
std::cout << "Here are the numbers in order." << std::endl;
std::vector<double> v;
t.inOrder(v);
std::cout << "values in order:";
for (double val : v)
{
std::cout << " " << val;
}
std::cout << std::endl;
return 0;
}