Binary tree

I am trying to complete an insertion function for my binary tree, but i am a little confused, because it uses two classes. Here is the code:

Code:

class CBinTreeNode
{
public:
	CBinTreeNode() :
	left(0), right(0), parent(0) {}
	CBinTreeNode(int k)  :
	left(0), right(0), parent(0) {key = k;}

	CBinTreeNode *left;
	CBinTreeNode *right;
	CBinTreeNode *parent;
	int key;
};

class CBinTree
{
public:
	CBinTree() {root = NULL;}

	void Insert(CBinTreeNode *z, int &c)
	{
		// TO DO
		

		
	}
	CBinTreeNode *root;
};

Code:

int main(int argc, char* argv[])
{
	// declare logistical variables (for testing)
	const size_t sa = 10001;
	int sizes[] = {1,2,3,4,5,6,7,8,9,10,20,30,40,70,100,200,300,500,1000,2000,5000,10000};
	int s_sizes = 22;
	int a[sa];			// This is always the input to work with
	srand((unsigned int)time((time_t)0));

// Demonstrate binary tree
	cout << endl<< "Demonstrate binary search tree:" << endl;
	int ts = 10;
	InitA(a, ts, 100);		// generate small random array
	Print(a, ts);			// display array
	// insert each element onto stack
	CBinTree tree;
	c=0;
	cout << endl<< "Insert:" << endl;
	for (int i=0; i < ts; i++)
	{
		tree.Insert(new CBinTreeNode(a[i]), c);
	}
return 0;
}

All the above code was provided, so i need to do the Insert function (where it says "TO DO"). The pseudocode for this is:

Code:

Tree-Insert(T,z)
y<- NIL
x<-root[T]
while x (does not equal) NIL
     do y<- x
          if key[z]<key[x]
               then x<-left[x]
               else x<-right[x]
p[z]<-y
if y = NIL
     then root[T]<-z
     else if key[z]<key[y]
               then left[y]<-z
               else right[y]<-z

I'm trying to figure out how to make the pseudocode work for my insert function, but i'm a little confused because this program uses two classes for the tree, and i'm not that great with using classes.
So, in the pseudocode insert function, the tree(T) is a parameter, but i don't have it as a parameter in my function. I can't figure out how to create x and assign it the root of the tree. If i can get that, i might be able to continue with the psuedocode.
NOTE* - None of the code should be modified, except for the insert function's body. The parameter c in the function is just a counter.

Any help would be appreciated.
Thanks.

Your Insert function is a class function; hence the "T" that you speak of is implicit. (In other words, it would have to be called like MyTree.Insert(MyNode, counter), and "T" would correspond to MyTree.) You can use the variables of the class (specifically, root) and they will refer to the variables owned by the object (in this case, you can use root and it will refer to MyTree.root).

Ok, my first attempt at this function has failed.

Code:

class CBinTree
{
public:
	CBinTree() {root = NULL;}

	void Insert(CBinTreeNode *z, int &c)
	{
		// TO DO
		CBinTreeNode *y = NULL;
		CBinTreeNode *x = root;
		CBinTreeNode *key;
		CBinTreeNode *parent;

		while(x != NULL)
		{
			y = x;
			if (key[z] < key[x])
			{
				x = left[x];
			}
			else
			{
				x = right[x];
			}
		}
		parent[z] = y;

		if(y == NULL)
		{
			root = z;
		}
		else if(key[z] < key[y])
		{
			left[y] = z;
		}
		else
		{
			right[y] = z;
		}

		
	}

So, i got the errors: "illegal index, indirection not allowed" on almost every line in this function. I'm guessing i didn't declare the variables correctly?

A couple things I see right away: you did remember to move this function after the declaration of root? Otherwise it won't have that variable name ready for you. Remember the class notation! The key of z is not key[z], but z.key (etc.)

Now, i'm getting the error: "left of .key/.left/.parent/.right must have class/struct/union" on almost every line.

Code:

class CBinTree
{
public:
	CBinTree() {root = NULL;}
	
	void Insert(CBinTreeNode *z, int &c)
	{
		// TO DO

		CBinTreeNode *y = NULL;
		CBinTreeNode *x = root;
		
		
		while(x != NULL)
		{
			y = x;
			if (z.key < x.key)
			{
				x = x.left;
			}
			else
			{
				x = x.right;
			}
		}
		z.parent = y;

		if(y == NULL)
		{
			root = z;
		}
		else if(z.key < y.key)
		{
			y.left = z;
		}
		else
		{
			y.right = z;
		}

		
	}

So, should the declarations of x and y be something like:

Code:

CBinTreeNode y;
CBinTreeNode x;

Then x and y would be like:

Code:

y = NULL;
x.parent = root;

But, it's not even recognizing z.key/left/parent/right as having a class either.

I didn't read carefully enough, so I inadvertently steered you wrong, I think:
x.key is for when x is a class
x->key is for when x is a pointer to a class.

So you'll need x and y to be pointers (you can't assign NULL to a class object!), so put those back and use -> instead.

Yep, that fixed it. Now it compiles without any errors. I'll see if it works correctly once i finish the other functions.

Thanks tabstop