Help: Binary Trees in C++

[thirty9th]

This class assignment [I]seemed[/I] pretty simple until I actually started working on it.

Normally I'd say I have a pretty good grasp on pointers, classes and structures, but something about this concept of binary search trees is baffling me.

[B]What we were asked to do:[/B]
* Create a binary search tree class in C++ and implement it in a driver (main.cpp)
* Use the following file format: Tree.h header file, Tree.cpp class definition, Main.cpp driver
* Add functionality to the tree CLASS to insert nodes, print out the Inorder of the tree, and, for bonus points, print the height of the tree

Here is what I have so far:

[B]Tree.h[/B]

//    Header file for 'Tree' class

class Tree {
    public:
        Tree();
        Tree(int data);
        void insert(int data);
        void printInorder(int data);

    private:
        int data;
        Tree *left;
        Tree *right;
};

[B]Tree.cpp[/B]

//    Class definition for 'Tree' class

#include "Tree.h"

Tree::Tree() {
    this->data = NULL;
    this->left = NULL;
    this->right = NULL;
}

Tree::Tree(int data) {
    this->data = data;
    this->left = NULL;
    this->right = NULL;
};

void Tree::insert(int newData, Tree root) {
    // Adds a node with input data to the current tree
    // Adds to left if < parent, to right if >= parent
    if (newData < root->data) {
        if (root->left == NULL) {
            root->left = new Tree(newData);
        } else {
            Tree::insert(newData, root->left);
        }
    } else {
        if (root->right == NULL) {
            root->right = new Tree(newData);
        }
        else {
            Tree::insert(newData, root->right);
        }
    }
};

void Tree::inorder(int data) {
    // Inorder implementation
};

void Tree::getHeight(int data) {
    // Get height implementation
};

[B]Main.cpp[/B]

//==============================================================================
//
//    Binary Tree Operations by Dillon Fisher
//    17 November, 2011
//    Description: Given a sequence of integers via command line, this program
//    will create a binary tree structure of the given integers. For each 
//    parent node, its left child will be less than or equal to itself, and
//    its right child will be greater than or equal to itself. Main.cpp has
//    the ability to add nodes to the tree, output the tree's Inorder, and
//    output the height of the tree.
//
//==============================================================================

#include "Tree.h"
#include <iostream>
#include <cstdlib>

using namespace std;

int main(int argc, char *argv[]) {

    // Variable Declarations
    int i;

    // Input Via Command Line, Fill the Tree
    for (i = 1; i < argc; i++) {
        if (i == 1) {
            Tree dataTree = new Tree(atoi(argv[i]));
        } else {
            dataTree.insert(atoi(argv[i]));
        }
    }

    cout << endl;

    // Output
    dataTree.printInorder(dataTree, *root);

    return 0;
    
}

-----

My first confounding error is right here:

// Input Via Command Line, Fill the Tree     
for (i = 1; i < argc; i++) {         
if (i == 1) {             
[B]Tree dataTree = new Tree(atoi(argv[i]));[/B]         
} else {             
dataTree.insert(atoi(argv[i]));         
}     
}

G++ gives me the error: Conversion from type 'Tree *' to non-scalar type 'Tree' requested

I cannot get any farther than this in the compiler.

What the fuck is up with my code?

[thrawn2787]

Pretty sure that new returns a pointer (so a pointer to a Tree rather than a Tree)

So either call the constructor like this:

Tree dataTree(atoi(argv[i]));

Or make dataTree a pointer

[pollyzoid]

You have some mistakes in main.cpp (didn't look through the others)

First of all, your dataTree declaration is out of scope whenever you're actually using it. You should declare it in an outer scope, like outside the main function or just inside it.
Secondly, you shouldn't use new when you don't need the object on heap. Your definition should just be
dataTree = Tree(atoi(argv[i]));
which creates the object on stack, where it will automatically be destroyed when it goes out of scope. [del]Also, why are you creating the Tree inside the for-loop? You could just move the whole declaration out of the loop and it would be good.[/del] Nevermind, I see you're doing that to give the root node a value.

[thirty9th]

I changed Main.cpp's code to:

// Input Via Command Line, Fill the Tree     
for (i = 1; i < argc; i++) {         
    if (i == 1) {             
        Tree dataTree(atoi(argv[i]));         
    } else {             
        dataTree.insert(atoi(argv[i]));         
    }     
}

G++ returns the error: dataTree undeclared

By the way, thank you for the responses so far.

I didn't know the difference between throwing it into the heap and that this simply puts it into the stack.

[thrawn2787]

[QUOTE=thirty9th;33352167]I changed Main.cpp's code to:

// Input Via Command Line, Fill the Tree     
for (i = 1; i < argc; i++) {         
    if (i == 1) {             
        Tree dataTree(atoi(argv[i]));         
    } else {             
        dataTree.insert(atoi(argv[i]));         
    }     
}

G++ returns the error: dataTree undeclared

By the way, thank you for the responses so far.

I didn't know the difference between throwing it into the heap and that this simply puts it into the stack.[/QUOTE]

Change it to

// Input Via Command Line, Fill the Tree  
Tree dataTree(atoi(argv[i]));     
for (i = 2; i < argc; i++) {           
    dataTree.insert(atoi(argv[i]));         
}

The stack and the heap are both basically memory spaces, but the stack is more temporary than the heap.

Basically what you need to know right now is the

// Output
dataTree.printInorder(dataTree, *root);

line had no idea what dataTree was since dataTree was declared inside the for loop and thus only existed inside the for loop (and would be destroyed as soon as it was finished). Declaring it outside solves this problem. This is what rabbish means by "scope" (basically what code can see what).

Also don't forget there is the what do you need help on thread. And rabbish keep in mind he may be really new and not know every programming term ever (like scope, heap, and stack)

[pollyzoid]

[QUOTE=thirty9th;33352167]G++ returns the error: dataTree undeclared[/QUOTE]

That's the first problem I mentioned. You're currently declaring it inside the for-loop, so it doesn't exist outside it. Like this it creates a Tree on the first iteration, which is then destroyed immediately because it goes out of scope. You need to move the declaration outside the loop, like so:

[cpp]
if (argc < 2)
{
cout << "usage goes here" << endl;
return 0;
}

Tree dataTree(atoi(argv[1]));

for (int i = 2; i < argc; ++i)
{
dataTree.insert(atoi(argv[i]));
}[/cpp]

Since your program uses the arguments, it's a good idea to check that there's enough of them and print the correct usage if there isn't. I would avoid using if like that inside for (having it only run when i == 1), so I moved it outside the loop and merged the definition with the declaration.

e: Also as a side note, you don't need to (and probably shouldn't) declare int i outside and separately from the for-loop.

e2: Just noticed this.

[cpp]dataTree.printInorder(dataTree, *root);[/cpp]

Why are you passing dataTree as the first argument? And you're passing a pointer to root but you haven't declared it. Also, in your header, printInorder takes an int as the argument, so why are you passing a pointer to it?

[ROBO_DONUT]

[QUOTE=raBBish;33351979]You have some mistakes in main.cpp (didn't look through the others)

First of all, your dataTree declaration is out of scope whenever you're actually using it. You should declare it in an outer scope, like outside the main function or just inside it.
Secondly, you shouldn't use new when you don't need the object on heap. Your definition should just be
dataTree = Tree(atoi(argv[i]));
which creates the object on stack, where it will automatically be destroyed when it goes out of scope. [del]Also, why are you creating the Tree inside the for-loop? You could just move the whole declaration out of the loop and it would be good.[/del] Nevermind, I see you're doing that to give the root node a value.[/QUOTE]
I don't think it's advisable to use stack memory in this sort of situation.
It might be OK here because it's just a 'dumb' binary search tree, but if it was an AVL tree implementation or something you'd run into real problems since you'd have one root node on the stack and the rest in the heap and the root node could be shifted into a branch somewhere during balancing.

[pollyzoid]

[QUOTE=ROBO_DONUT;33352591]I don't think it's advisable to use stack memory in this sort of situation.
It might be OK here because it's just a 'dumb' binary search tree, but if it was an AVL tree implementation or something you'd run into real problems since you'd have one root node on the stack and the rest in the heap and the root node could be shifted into a branch somewhere during balancing.[/QUOTE]

I didn't notice Tree used heap for the children. Yeah, using heap for this case is probably smarter.
I'd separate the tree and nodes into two classes (or class and struct), so you could have a single Tree on the stack acting as the root, containing pointers to the children.

[ROBO_DONUT]

[QUOTE=raBBish;33352761]I didn't notice Tree used heap for the children.[/QUOTE]
There is literally no way you can build a structure with an arbitrary number of nodes exclusively using stack memory.

[thirty9th]

Okay, I'm making progress...

Right now I'm assuming there will be at least 2 command line arguments and will account for other possibilities later.

G++ is telling me:
* no matching function for call to 'Tree::insert (int, Tree &)'
candidates are: void Tree::insert(int)
* no matching function for call to 'Tree::printInorder (Tree &)'
candidates are: void Tree::printInorder()

I've played around with how to pass root to the functions, but with no luck. What's the deal here?

Snippet of Tree.cpp

...

void Tree::insert(int newData, Tree *root) {
	// Adds a node with input data to the current tree
	// Adds to left if < parent, to right if >= parent
	if (newData < root->data) {
		if (root->left == NULL) {
			root->left = new Tree(newData);
		} else {
			Tree::insert(newData, root->left);
		}
	} else {
		if (root->right == NULL) {
			root->right = new Tree(newData);
		}
		else {
			Tree::insert(newData, root->right);
		}
	}
};

...

void Tree::printInorder(Tree *root) {
	// Prints the inorder of the current tree
	if (root != NULL) {
		Tree::printInorder(root->left);
		cout << root->data << " ";
		Tree::inorderPrint(root->right);
	}
};

Driver

...

int main(int argc, char *argv[]) {
	
	// Input Via Command Line, Fill the Tree
	Tree dataTree(atoi(argv[1]));
	Tree *root = &dataTree;
	for (int i = 2; i < argc; i++) {
		dataTree.insert(atoi(argv[i]), *root);
	}

	cout << endl;

	// Output
	dataTree.printInorder(*root);

	return 0;
	
}

I'm afraid I've confused myself with passing the pointer to root to these functions somehow.

Also, thank you for telling me about the Help thread. I'll be sure to use that in the future.

[ROBO_DONUT]

You need to update the method function prototypes in the class definition. It doesn't look like the match the actual function definitions.

[pollyzoid]

As ROBO_DONUT said, your function prototypes don't match. The * operator in *root dereferences it (ie. the function should take a Tree&), but to pass a pointer you'd need to pass the function &root (& is reference operator). I recommend using references whenever possible, since they're safer than pointers (can't be NULL, for example).
Also, since printInorder doesn't modify the tree, you should make the argument const.

[cpp]void Tree::insert(int newData, Tree& root)
void Tree::printInorder(const Tree& root)[/cpp]

The operators: &root would be the point in memory where root is. *root would be the value in memory pointed by root.
In variables: "type &name" is a reference to "type". In "type *name" name holds the address to a variable of type "type".

Sorry if it's confusing, I'm bad at explaining [img]http://www.facepunch.com/fp/emoot/frown.gif[/img]

e: Why do your class methods take a Tree as the argument? It's redundant, since you can just use "this" inside the methods to access the object.

The above would be
[cpp]void Tree::insert(int newDatat)
void Tree::printInorder()[/cpp]

Inside the method, for example:
[cpp]void Tree::printInorder() {
// Not sure if we can assume left and right to be non-null, check for nullptr if we can't
this->left->printInorder();
cout << this->data << " ";
this->right->printInorder();
};[/cpp]

And usage:

[cpp]Tree *someTree = new Tree(1);
someTree->insert(2);
someTree->printInorder();[/cpp]

[dajoh]

[QUOTE=ROBO_DONUT;33356205]There is literally no way you can build a structure with an arbitrary number of nodes exclusively using stack memory.[/QUOTE]

You could use alloca()

[ROBO_DONUT]

[QUOTE=dajoh;33370775]You could use alloca()[/QUOTE]
Neat to know that exists, but it's still not part of ANSI/ISO C/C++, nor do you probably want to use it (at least not in that way), lest you invoke the wrath of the dreaded stack overflow.