First Tree class...could use some help

[vanllabean81]

I'm trying to code a tree class that reads in the constitution and puts all the words in an ordered binary tree (in alphabetical order.) The teacher said he gave us the code to do it, but it isn't working. I've been trying to debug it all day, and I can't find where it's wrong. Can anyone else see where the problem is?

Any help is appreciated.

#include <iostream>
#include <fstream>
#include <string>

using namespace std;

// File Descriptors
ofstream outfile;
ifstream infile;

// Class Definition
class tNode
{
    // Typedefs
    typedef string tType;   // Declare typedef for all values in tree

    private:
        tNode* LChild;      // Points to the left branch of tree
        tType value;        // Value in node
        tNode* RChild;      // Points to the right branch of tree
    public:
        tNode()             // Default Constructor
        {
            LChild = NULL;
            RChild = NULL;
            value = '0';
        }
        void PrintTree(tNode* treeRoot)
        // Prints out the contents of a tree, in order
        // from smallest to largest
        {
            if (treeRoot== NULL)
                return;
            PrintTree(treeRoot->LChild);
            cout << treeRoot->value;
            PrintTree(treeRoot->RChild);
        }
        tNode* myNewTNode()
        // Creates new tree node with a value,
        // a left child, and a right child (pointers)
        {
            tNode* temp;
            temp = new tNode;
            temp->value = '0';
            temp->LChild = NULL;
            temp->RChild = NULL;
            return temp;
        }
        void insert(tNode* r, tType v)
        // Inserts values into tree
        {
            tNode* parent;
            tNode* temp;
            if (r == NULL)
            {
                r = myNewTNode();
                r->value = v;
                return;
            }
            while (r != NULL)
            {
                if (v < r->value)       // Smaller values will go on the left
                {
                    parent = r;         // Set parent to current root
                    r = r->LChild;      // Set root to point to the left side of tree
                }
                else if (v > r->value)  // Larger values go to the right
                {
                    parent = r;         // Set parent to current root
                    r = r->RChild;      // Set root to point to the right side of tree
                }
                temp = myNewTNode();    // Create a new node
                temp->value = v;        // Fill in the value
                if (v < parent->value)  // If passed in value is less than parent's value
                    parent->LChild = temp;// Place new node as parent's left child
                else if ( v> parent->value)// If passed in value is larger than parent's value
                    parent->RChild = temp; // Place new node as parent's right child
                return;
            }
        }

[kbw]

    typedef string tType;   // Declare typedef for all values in tree

    private:
        tType value;        // Value in node
        // ...

    public:
        tNode()             // Default Constructor
        {
            // ...
            value = '0';   // Wrong. Don't assign it a value, let the default constructor initialise it.
        }

You also have member function tNode* myNewTNode(). Have you thought about how a node is used? I would have thought that instantiating a node is creating a new one. It shouldn't need a create member function too. Maybe you're missing a tree class that can create and insert nodes in right place in the tree.

[vanllabean81]

Aha! Okay, so if I get rid of that constructor, I'm still okay with the insert function, right? In there it does create and insert right in that function...
So I deleted that constructor, but the program still doesn't run correctly...hmm...

[kbw]

That's not what I had in mind. If you think more about how a node is used, you'll see where I coming from.

Although a tree is made up of nodes, there's still a tree objects that organises these nodes. And that's what your missing. Your node class has operations like:
construct from value
set left ptr
set right ptr
read value

And the tree class has operations like:
insert value
delete value
find value

A node is just used internally within the tree. Users of your tree don't need to know anything about nodes at all. Node isn't your main data structure, tree is.

[vanllabean81]

So this isn't a tree? Well then I'm even more confused than I thought. This is the exact code that was given to us. Our teacher did say that we could write the functions OUTSIDE the class, and just have very basic functions inside like, set lChild, rChild, and value. Is this what you mean? He also said he didn't like that much, though, and that he thought is was easier if you just wrote all the functions inside the class.

Are you saying that that isn't really the way that it's done, so I should have a Tree class, that has within it a Node class, that only has the 2 children and value fields?

I'm sorry, but this is brand new to me, and I want to get it, it's just always harder to implement than it looks like it will be...

[kbw]

I'll diverge a bit. Let's look at a double threaded linked list. It's made up of nodes that have a value, a front and a back pointer. However, when you use the standard linked list, you don't encounter nodes at all. That was my thinking about your tree.
http://en.cppreference.com/w/cpp/container/list

Back to your tree.

So this isn't a tree?

We can just work with nodes, but that's pushing the implementation into the program that uses it. Have you noticed how myNewTNode() and insert() don't use any member data of tNode?

I will work with your current definitions, but first, can you please post code that uses this? Once I have that, we can look at fixing what's wrong in one final push.

[vanllabean81]

Thank you. I'm at work, but I'll be home in 3 hours, and I'll post the main program then. It's not much though, at all.
It just opens the input and output files, and starts reading in the words from the 'constitution' file. It does seem to do that, although I don't think it's actually placing them in the tree...I tried to debug it all night last night, and when it gets to my Insert function (above) it shuts down. This being my first tree ever, since I can't fix that part, I haven't even been able to start figuring out how to count each instance of each word....

I'll post the code ASAP. Thanks again.

[vanllabean81]

kbw ~ I've been looking at the link you posted, and I have what I'm sure is a stupid question, but I'm asking it anyway.

Do all those functions already exist in a list...how cool is that?! I've never seen a <list> header before. If they already exist, why do we write them? Is it supposed to be a learning experience, or is there something I don't understand here? For instance, if I have a Linked List assignment that I can't seem to code correctly, (which I do) is it cheating to use the <list> header and the ready-made functions?

Almost too good to be true...is there a <tree> header? ;)P

[kbw]

We use them all the time. In C++, no one implements linked lists anymore, we just use std::list.

There isn't a standard tree class as such, but some containers are implemented using trees such as map, multimap, set, ... almost all of those containers that have a sorted key use a tree implementation internally.

Just to work thru a tree example, I'll do it without using classes first.

#include <string>
#include <iostream>

struct Node
{
        typedef std::string value_type;

        const value_type value;
        Node* lptr;
        Node* rptr;

        Node(value_type value) : value(value) { lptr = rptr = 0; }
};

void insert(Node **tree, Node::value_type value)
{
        if (*tree == 0)
        {
                *tree = new Node(value);
                return;
        }

        if (value < (*tree)->value)
                insert(&((*tree)->lptr), value);
        else
                insert(&((*tree)->rptr), value);
}

void print(Node* tree, std::ostream &os)
{
        if (tree)
        {
                print(tree->lptr, os);
                os << tree->value << std::endl;
                print(tree->rptr, os);
        }
}

int main()
{
        Node* planets = 0;
        insert(&planets, "Mars");
        insert(&planets, "Saturn");
        insert(&planets, "Earth");
        insert(&planets, "Jupiter");
        insert(&planets, "Pluto");

        Node* cities = 0;
        insert(&cities, "Paris");
        insert(&cities, "Orleans");
        insert(&cities, "Lyon");
        insert(&cities, "Bordeaux");
        insert(&cities, "Monaco");

        print(cities, std::cout);
        print(cities, std::cout);

        return 0;
}

We now have a tree structure that stores strings. Note the following.
1. Node just holds the value and pointers.
2. The Node constructor conveniently initialises members.
3. There's only one constructor as we only create Nodes in one way.
4. We could disable copy on Node as it should never be copied, but that's distracting in this example.
5. The tree operations are not members of Node, they take the root node as a parameter. At present the operations are global functions, but eventually we'd encapsulate them in a Tree class.
6. Tree operations are recursive.
7. You must work with Node* in your program and you must explicitly initialise it to zero yourself.
8. I've not shown deletion, but the tree should be deleted on exit.

[Lowest0ne]

^^ With classes :)
http://www.cplusplus.com/forum/beginner/75002/2/

I put the deleting in there, but didn't post the recursion (which makes it a pretty dumb tree). If my words helped, I will post more.

[vanllabean81]

Okay, so here is my latest tree. I've been working like a madwoman on this, but it still isn't printing out correctly. Can you take a look? It seemed like my r was always == NULL, so I thought maybe changing insert() from void to TreeNode* type would help, but I think that was wrong, because it still does the same thing...

ALL comments are appreciated. This bad boy is due tonight, and since I still haven't figured out Link List, I'd like to at least turn this one in on time.

#include <iostream>
#include <fstream>
#include <string>
#include <list>

using namespace std;

// File Descriptors
ofstream outfile;
ifstream infile;

// Class Definitions
class TreeNode
{
    typedef string valueType;
    private:
        TreeNode* Lchild;       // Points to this node's left child
        TreeNode* Rchild;       // Points to this node's right child
        valueType word;         // Holds the word
        int counter;            // Holds the number of occurences of the word
    public:
        TreeNode* insert(TreeNode*, valueType);    // Adds a word to the bst
        void print(TreeNode*);               // Prints out each word along with it's count and frequency
        TreeNode* myNewNode();      // Creates a new pointer to a new node in the bst
};


// Prototypes
int OpenOutput();
int OpenInput();
void PrintHeader();

int main()
{
    OpenOutput();
    OpenInput();
    PrintHeader();

    string word;                    // Declare variable to hold each word from infile
    TreeNode* root = NULL;          // Declare a pointer of type TreeNode that points to our tree
    TreeNode tree;                  // Declare an object of type TreeNode to start a tree
    tree.myNewNode();               // Create a node for root to point to
    infile >> word;
    while (infile)
    {
       tree.insert(root, word);
       //cout << "Word inserted is: " << word << endl;
       infile >>  word;
    }

    tree.print(root);

    return 0;
}

// Funtion Definitions
// *********************************************************************
TreeNode* TreeNode::myNewNode()
{
    TreeNode* temp = NULL;          // New pointer, points to nothing
    temp = new TreeNode;            // Points to a newly created node
    //.temp->word = NULL;              // Empty value in word section
    temp->Lchild = NULL;            // There are no left children yet to point to
    temp->Rchild = NULL;            // There are no right children yet to point to
    temp->counter = 0;              // There are no words to count yet
    return temp;
}

// *********************************************************************
TreeNode* TreeNode::insert(TreeNode* r, valueType v)    // Adds a word to the bst
{
    TreeNode* parent;       // Points to parent node
    TreeNode* temp;         // Temporary holding place

    if (r == NULL)          // If we don't have a tree yet
    {
        r = myNewNode();    // This starts us off
        r->word = v;        // Put passed in word into tree node
        r->counter = counter + 1;// Increment that word's counter
        return r;             // Get out of function
    }
    while (r != NULL)       // While we do have a tree
    {                       // Search for where to put new value
        if(v < r->word)     // If new word is less than root's word
        {
            parent = r;     // Make the root a parent
            r = r->Lchild;  // Move down left tree
        }
        else if (v > r->word)// If new word is greater than root word
        {
            parent = r;     // Make the root a parent
            r = r->Rchild;  // Move down right tree
        }
    }
    temp = myNewNode();     // Create a new node
    temp->word = v;         // Fill in the word field

    //  Update left and right parents
    if (v < parent->word)
        parent->Lchild = temp;
    else if (v > parent->word)
        parent->Rchild = temp;
    return r;
}

// *********************************************************************
void TreeNode::print(TreeNode* r)
{
    if (r == NULL)
        return;
    print(r->Lchild);
    cout << r->word;
    print(r->Rchild);
}

// *********************************************************************
int OpenOutput()
{
    outfile.open("TreesOUT");
    if (!outfile)
    {
        cout << "Error opening output file." << endl << endl;
        outfile << "Error opening output file." << endl << endl;
        return 1;
    }
    else
    cout << "Output file opened correctly." << endl << endl;
    outfile << "Output file opened correctly." << endl << endl;
}

// *********************************************************************
int OpenInput()
{
    infile.open("USconstitution.dat");
    if (!infile)
    {
        cout << "Error opening input file." << endl << endl;
        outfile << "Error opening input file."  << endl << endl;
        return 1;
    }
    else
    {
        cout << "Input file opened correctly." << endl << endl;
        outfile << "Input file opened correctly." << endl << endl;

    }
}

// *********************************************************************
void PrintHeader()
{
    cout << "Erin Corona" << endl;
    cout << "CS 372.30137" << endl;
    cout << "Trees " << endl;
    cout << "Due Friday, July 13, 2012" << endl << endl;

    outfile << "Erin Corona" << endl;
    outfile << "CS 372.30137" << endl;
    outfile << "Trees " << endl;
    outfile << "Due Friday, July 13, 2012" << endl << endl;
}

[Lowest0ne]

Note kbw's insert
void insert(Node **tree, Node::value_type value)

You must pass a pointer to a pointer to modify the "real" node pointer. Syntax is in that function, and I think it's the only place you need a **.

[vanllabean81]

Okay, that was the wrong version. This is the one with me trying to implement it with the help you guys gave me earlier. And...it prints out the first word with the correct counter of 1. But since it's only the first word, I guess I still don't really know if that works right.
Thanks, LowestOne, I'll see what I've got here and make sure the insert() is doing that....

Any other problems jumping out at you in this version?

#include <iostream>
#include <fstream>
#include <string>
#include <list>

using namespace std;

// File Descriptors
ofstream outfile;
ifstream infile;

// Class Definitions
class TreeNode
{
    typedef string valueType;
    private:
        TreeNode* root;         //  The tree's root node's pointer
        TreeNode* Lchild;       // Points to this node's left child
        TreeNode* Rchild;       // Points to this node's right child
        valueType word;         // Holds the word
        int counter;            // Holds the number of occurences of the word
    public:
        // Constructer
      TreeNode()
      {
        root = NULL;            // very important
        counter = 0;            // No words counted yet
      }
      TreeNode* insert(valueType);    // Adds a word to the bst
      //TreeNode* insert(TreeNode*, valueType);    // Adds a word to the bst
      valueType get_word()                // Returns the word in current node
      { return word;}
      int get_counter()             // Returns the counter of current node
      { return counter;}
      void print(TreeNode*);               // Prints out each word along with it's count and frequency
      TreeNode* myNewNode();      // Creates a new pointer to a new node in the bst
};


// Prototypes
int OpenOutput();
int OpenInput();
void PrintHeader();

int main()
{
    OpenOutput();
    OpenInput();
    PrintHeader();

    string word;                    // Declare variable to hold each word from infile
    //TreeNode* root = NULL;          // Declare a pointer of type TreeNode that points to our tree
    TreeNode tree;                  // Declare an object of type TreeNode to start a tree
    //tree.myNewNode();               // Create a node for root to point to
    infile >> word;
    while (infile)
    {
       //tree.insert(root, word);
       tree.insert(word);
       //cout << "Word inserted is: " << word << endl;
       infile >>  word;
       cout << "Word: " << tree.get_word() << "  Absolute: " << tree.get_counter() << endl;
    }
    return 0;
}

// Funtion Definitions
// *********************************************************************
TreeNode* TreeNode::myNewNode()
{
    TreeNode* temp = NULL;          // New pointer, points to nothing
    temp = new TreeNode;            // Points to a newly created node
    //.temp->word = NULL;              // Empty value in word section
    temp->Lchild = NULL;            // There are no left children yet to point to
    temp->Rchild = NULL;            // There are no right children yet to point to
    temp->counter = 0;              // There are no words to count yet
    return temp;
}

// *********************************************************************
//TreeNode* TreeNode::insert(TreeNode* r, valueType v)    // Adds a word to the bst
TreeNode* TreeNode::insert(valueType v)    // Adds a word to the bst

{
    TreeNode* parent;       // Points to parent node
    TreeNode* temp;         // Temporary holding place

    if (root == NULL)          // If we don't have a tree yet
    {
        root = myNewNode();    // This starts us off
        word = v;        // Put passed in word into tree node
        counter = counter + 1;// Increment that word's counter
        return root;             // Get out of function
    }
    while (root != NULL)       // While we do have a tree
    {                       // Search for where to put new value
        if(v < word)     // If new word is less than root's word
        {
            parent = root;     // Make the root a parent
            root = Lchild;  // Move down left tree
        }
        else if (v > word)// If new word is greater than root word
        {
            parent = root;     // Make the root a parent
            root = Rchild;  // Move down right tree
        }
    }
    temp = myNewNode();     // Create a new node
    temp->word = v;         // Fill in the word field

    //  Update left and right parents
    if (v < parent->word)
        parent->Lchild = temp;
    else if (v > parent->word)
        parent->Rchild = temp;
    return root;
}

// *********************************************************************
void TreeNode::print(TreeNode*)
{
    if (root == NULL)
        return;
    print(Lchild);
    cout << word;
    print(Rchild);
}

// *********************************************************************
int OpenOutput()
{
    outfile.open("TreesOUT");
    if (!outfile)
    {
        cout << "Error opening output file." << endl << endl;
        outfile << "Error opening output file." << endl << endl;
        return 1;
    }
    else
    cout << "Output file opened correctly." << endl << endl;
    outfile << "Output file opened correctly." << endl << endl;
}

// *********************************************************************
int OpenInput()
{
    infile.open("USconstitution.dat");
    if (!infile)
    {
        cout << "Error opening input file." << endl << endl;
        outfile << "Error opening input file."  << endl << endl;
        return 1;
    }
    else
    {
        cout << "Input file opened correctly." << endl << endl;
        outfile << "Input file opened correctly." << endl << endl;

    }
}

// *********************************************************************
void PrintHeader()
{
    cout << "Erin Corona" << endl;
    cout << "CS 372.30137" << endl;
    cout << "Trees " << endl;
    cout << "Due Friday, July 13, 2012" << endl << endl;

    outfile << "Erin Corona" << endl;
    outfile << "CS 372.30137" << endl;
    outfile << "Trees " << endl;
    outfile << "Due Friday, July 13, 2012" << endl << endl;
}

[vanllabean81]

Note kbw's insert

void insert(Node **tree, Node::value_type value)

You must pass a pointer to a pointer to modify the "real" node pointer. Syntax is in that function, and I think it's the only place you need a **. 

But, if root is private, how do I pass it in? This is what really confuses me. I get that I declare a pointer of type TreeNode called root;

TreeNode* root;
But then, what I don't get, is don't I need to create an object of type TreeNode to be able to access all the member functions? That's why I created tree, but my teacher didn't do this.

Do I declare root in main like my teacher, or make root a private variable, like it was done in the example here?

[vanllabean81]

Oh, oh! I got it to work, kind of. I need it to convert the words to lowercase, and then count each occurrence of EACH word, but right now it is just counting how many words there are, total. Is there a function to convert a string to lowercase, or just to convert it by char?

Here's the link to the latest version!
http://pastebin.com/embed_js.php?i=0JVEYWxU

[vanllabean81]

http://pastebin.com/embed_iframe.php?i=0JVEYWxU
Making slow progress. Can someone point me in the right direction for the count part?
How do I count each instance of each word? I need to know how many time 'the' appears, etc.

For anyone who cares, here is what the above link's output looks like:
http://pastebin.com/embed_iframe.php?i=gcctMs9u

So, I'm at least making progress, right? My tree is a tree now, right? (Please God, say yes.)

[Lowest0ne]

So, I'm at least making progress, right? My tree is a tree now, right? (Please God, say yes.)

I don't think so. You haven't really done any of the things suggested (make a node class separate from the tree, use a node** during insert, deleting your memory, creating a header).

The way you get the count is during your insert. You have a less than and a greater than comparison, so you can increase a count if neither of those are true.

A few days ago I made a tree and have since updated it. Good Luck.

tTree.h : http://pastebin.com/uytRJpc8
tTree.cpp : http://pastebin.com/Kb9tUhZb
simple main.cpp : http://pastebin.com/Xi3ap37K

[vanllabean81]

Oh, really? Damn it! I even used that tree you made to *fix* mine. Ugh. I suck at this. I can't believe I haven't done anything, after all this time! I'm so going to fail this class.
:(
Well, LowestOne, thanks for letting me know. I'll take another look at your tree. Can you let me know, though, what my FIRST mistake is? I don't want to start screwing it up before I should be...

[Lowest0ne]

Well, I think the order of mistakes is up for debate :)

I would say the first one is the memory leak, for every new you need a delete. Whenever I do this, I run my program through an infinite loop and watch the task-manager for leaking memory. Generally something like this:

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

void classTest(void)
{
  bTree myTree;
}

int main(void)
{
  while (true)
    classTest();

  std::cout << "\nI'm Done";
  return 0;
}

Can my class even be instantiated without a memory leak? That program will tell me. The loop can easily be commented out if I only want to call classTest() once.

classTest() then evolves:

 void classTest(void)
{
  bTree myTree;
  myTree.insert("hello");
}

Does this cause a leak? Are the left/right nodes pointing to NULL? Then to add more than one string, which means implementing a recursive insert/print/destroy. Is my insert actually working? Do things go where they are supposed to? Is everything getting deleted?

The biggest clue to something is wrong is that you never call void TreeNode::print(TreeNode*). This function should work outside of the while loop.

[vanllabean81]

Well, I think the order of mistakes is up for debate :)

Hahahahaha. Well, don't I get points for trying? Lol. You know, I'm using yours as a model, and now going through the debugger with it, stopping pretty much everywhere so I can see what's going on.