I dont understand

[Dustin Poff]

So I have a program due tomorrow. I have been working on it for some time now and I have gotten to a point where I am stuck what we are doing is making a BST which is pretty easy. But I am having difficulties getting the binary search trees in a since that once it is created the root and is corresponding offspring never change from NULL. This is in 3 seprate .cpp's so im only going to post the 2 that seem needed.

BST.cpp and Node.cpp

Bst.cpp

#include "BST.h"


void BST::Const()
{
    root = new node;
    root = NULL;
}
void BST::Dest()
{
    root->Destructor();
}
void BST::Ins(int Key, string Data, node* r)
{
    if (r == NULL)
    {
        r = new node(Key, Data);
    }
    else if (r->getKey() < Key)
    {
        Ins(Key, Data, r->getLeft());
    }
    else if (r->getKey() >= Key)
    {
        Ins(Key, Data, r->getRight());
    }
    
}
void BST::PrintKT(node* r, int level)
{
    if (r == NULL)
    {
        cout << endl;
        return;
    }
    PrintKT(r->getRight(), level + 1);
    for (int i = 1; i <= level * 5; i++)
    {
        cout << " ";
    }
    cout << r->getKey() << endl;
    PrintKT(r->getLeft(), level + 1);
}
string BST::Sea(int Key, node* r)
{
    if (r==NULL)
    {
        return "";
    }
    else if (r->getKey() == Key)
    {
        return r->getData();
    }
    else if (r->getKey() > Key)
    {
        return Sea(Key, r->getRight());
    }
    else if (r->getKey() < Key)
    {
        return Sea(Key, r->getLeft());
    }
}
int BST::NNodes(node* r)
{
    int i = 0;
    if (r == NULL)
    {
        return 1;
    }
    i = i + NNodes(r->getRight());
    i = i + NNodes(r->getLeft());
    return i - 1;
}
int BST::Dep(node* r) 
{
    if (r == NULL)
    {
        return 0;
    }
    else
    {
        int rDepth = Dep(r->getRight());
        int lDepth = Dep(r->getLeft());
        if (rDepth > lDepth)
        {
            return (rDepth + 1);
        }
        else
        {
            return (lDepth + 1);
        }

    }
}
int BST::MinK(node * r)
{
    if (r == NULL)
    {
        return -1;
    }
    else if (r->getLeft() == NULL)
    {
        return r->getKey();
    }
    else
    {
        return MinK(r->getLeft());
    }
}
void BST::PrintS(node* r)
{
    if (r == NULL)
    {
        return;
    }
    PrintS(r->getLeft());
    cout << r->getKey() << "=" << r->getData() << endl;
    PrintS(r->getRight());
}


void BST::Constructor()
{
    Const();
}
void BST::Destructor()
{
    Dest();
}
void BST::Insert(int Key, string Data)
{
    Ins(Key, Data, root);
}
void BST::PrintKeyTree()
{
    PrintKT(root, 0);
    return;
}
string BST::Search(int Key)
{
    return Sea(Key, root);
}
int BST::NumNodes()
{
    return NNodes(root);
}
int BST::Depth()
{
    return Dep(root);
}
int BST::MinKey()
{
    return MinK(root);
}
void BST::PrintSorted()
{
    PrintS(root);
}

the Ins(int Key, string Data, node*r) is the function dealing with changing the first root and corresponding offspring using recursion to decided where the new item in the tree should go.


Node.h

#include "Node.h"
#include <iostream>

using namespace std;

node::node()
{
    key = -1;
    data = "";
    rightChild = NULL;
    leftChild = NULL;
}
node::node(int Key, string Data)
{
    key = Key;
    data = Data;
    rightChild = NULL;
    leftChild = NULL;
}

void node::setKey(int Key)
{
    key = Key;
}
void node::setData(string Data)
{
    data = Data;
}
void node::setLeft(node* Left)
{
    leftChild = Left;
}
void node::setRight(node* Right)
{
    rightChild = Right;
}
void node::Destructor()
{
    if (leftChild != NULL)
    {
        delete leftChild;
    }
    if(rightChild != NULL)
    {
        delete rightChild;
    }
}
node* node::getLeft()
{
    return leftChild;
}
node* node::getRight()
{
    return rightChild;
}
int node::getKey()
{
    return key;
}
string node::getData()
{
    return data;
}

Deals with setting the key and data to the right values as well as creating the new children

[algorism]

Well, look at your code:

void BST::Ins(int Key, string Data, node* r)
{
    if (r == NULL)
    {
        r = new node(Key, Data);
        // and then it returns
    }
    ...

r is a local variable (a parameter).
It is ceases to exist when the function returns.
You may want to assign to the actual root instead (presumably a member of the BST class).

BTW, you should obviously show your .h files, too, since those contain the class declarations.

[Salem]

Why do you have so many functions acting like constructors and destructors?

Eg, where is

BST::BST() {
  // do something?
}

Also this, right at the start of the first function.
root = new node;
root = NULL;
You create a new node, then immediately drop it on the floor.