Okay so I have been debugging for hours and I don't understand any of this...I'm kinda mad about not knowing and when I research it all I find how it works but not really how to implement it. I know the general theory of a binary search tree but I'm having a hard time implementing it in the main file.
I'm having trouble with the following functions:
btree(const btree& tree) //How does the copy constructor work?
T& root() //I have no idea what this does
node(const T& x) //Not sure how to implement this
I'm also having trouble with the unsigned int my_size in the header file.
I'm all over the place...it compiles but when I try it in my main some parts don't work.
My main.cpp is crappy I'm not even using it right now, it's just what I would want it to be. I didn't know how to implement the 'a word' case at all.
my_btree.h
#ifndef MY_BTREE_H
#define MY_BTREE_H
// my_btree.h - binary tree class (no balancing)
using namespace std;
// forward declaration of classes defined in this header
template <class T> class btree;
template <class T> class node;
template <class T>
class btree
{
public:
// constructors
btree(); // no-arg constructor
btree(const btree & tree); // copy constructor
~btree(); // destructor
// operations
bool empty() const;
int size() const;
T & root() const;
// print in-order traversal of the tree
void print() const;
// insert x into tree (wherever it goes)
void add_element(const T & x);
// calculate height of tree
int height() const;
protected:
node<T> * rootnode;
unsigned int my_size;
// internal methods used recursively
private:
// calculate height of a tree rooted at n
int height(node<T> *n) const;
// print subtree rooted at n (recursive)
void print(node<T> *n);
// insert x in tree rooted at node n (keep in order!)
void insert(node<T> * n, const T & x);
};
template <class T>
class node
{
private:
node(const T & x); // private constructor
T x; // data
node<T> * left; // left child
node<T> * right; // right child
friend class btree<T>;
};
#include "my_btree.cpp"
#endifmain.cpp
#include <iostream>
#include "my_btree.h"
using namespace std;
void menu(){
cout << "i — initialize the tree";
cout << "p — Print the tree’s contents in-order";
cout << "s — Print the tree’s size (number of elements)";
cout << "h — Height of the tree";
cout << "Enter option: ";
}
int main(){
btree<int> T;
char ch;
while(!cin.eof()){
menu();
cin >> ch;
switch(ch){
case i: if(root != empty){
cout << Tree exists, type 'i' to initialize anyway."<< endl;
}else{
node<int> root;
root = NULL;
cout << "Tree initialized" << endl;
}
break;
case p: cout << T.print(root) << endl;
break;
case s: cout << T.size() << endl;
default: cout << "Incorrect option";
}
};
}my_btree.cpp
#include <iostream>
#include <cmath>
using namespace std;
#include "my_btree.h"
template <class T>
btree<T>::btree(){
rootnode = NULL;
}
template <class T>
btree<T>::btree(const btree& tree){
rootnode = new node<T>;
*rootnode = *tree.rootnode;
}
template <class T>
btree<T>::~btree(){
destruct(rootnode);
}
template <class T>
void btree<T>::destruct(node<T>* n){
if(n != NULL){
destruct(n->left);
destruct(n->right);
delete n;
n = NULL;
}
}
template <class T>
bool btree<T>::empty() const{
if(rootnode == NULL){
return true;
}else{
return false;
}
}
template <class T>
int btree<T>::size() const{
return my_size;
}
template <class T>
T& btree<T>::root() const{
}
template <class T>
void btree<T>::print() const{
if(empty()){
cout << "Empty tree" << endl;
}else{
print(rootnode);
}
}
template <class T>
void btree<T>::add_element(const T& x){
if(rootnode == NULL){
rootnode = new node<T>(x);
++my_size;
}else{
insert(rootnode, x);
}
}
template <class T>
int btree<T>::height() const{
height(rootnode);
}
template <class T>
int btree<T>::height(node<T>* n) const{
if((left == NULL) && (right == NULL)){
return 0;
}
if(left == NULL){
return (height(n->right))+1;
}
if(right == NULL){
return (height(n->left))+1;
}
if((left != NULL) && (right != NULL)){
return (max(height(n->left), height(n->right)))+1;
}
}
template <class T>
void btree<T>::print(node<T>* n){
if(n != NULL){
if(n->left){
print(n->left);
}
cout << n->x << endl;
if(n->right){
print(n->right);
}
}
}
template <class T>
void btree<T>::insert(node<T>* n, const T& x){
if(x < (n->x)){
if((n->left) == NULL){
n->left = new node<T>(x);
}else{
insert(n->left, x);
}
}
if(x > (n->x)){
if((n->right) == NULL){
n->right = new node<T>(x);
}else{
insert(n->right, x);
}
}
}
template <class T>
node<T>::node(const T& x){
this->x = x;
this->left = NULL;
this->right = NULL;
}If you made it down here then you at least skimmed it. Plz help if you can, especially in writing my main file cuz I'm lost....here's some sample output of what it should do
i
>> Tree initialized
a middle
>> Added word "middle" to root of tree
a aardvark
>> Added word "aardvark" to left of "middle"
a zebra
>> Added word "zebra" to right of "middle"
p
>> aardvark, middle, zebra
s
>> 3
i
>> Tree exists, type 'i' again to initialize anyway.