Class struct

[mythos061]

Generic task:

I am assigned to store student information in a binary search tree.

I have a templated tree class, school class, and student class.

The school class inherits from the tree class. The student class is on its own.

Now, I want to encapsulate a student in a struct, and enter it into a tree.

Problem:

I want to use the student class as the template argument in the tree.

Ex: tree<student>

But technically I want to use a struct as the template arugment, not a class.

Question:

Is there someway I can incorporate a struct into the student class? I would need to use the struct globally so I don't see how to do this.

Please help, I am confused.

[Moschops]

You do sound confused.

If I point out to you that in C++, a struct and a class are identical except for default privacy levels, does that help?

But technically I want to use a struct as the template arugment, not a class.

There's no difference.

[mythos061]

Okay that helps. So I guess my question would be:

So if I used a student CLASS instead of a struct, how would I pass that onto a template arugment:

example:

student<????> stu; <----would I even need to declare this in main?
school<student> abc; // create object of school class

[mythos061]

Okay student should not be templated....

[mythos061]

I am having difficulty listing a students record that is only of a particular major. When I insert a student into a tree. How do I access its members?
How do I access student.major from the tree?

[mythos061]

Okay, a little more specific:

When I declare a student object:

student stu;

And then insert it into a tree:

insert(stu);

How do I access and change that students data members now that it is inserted into a binary tree?

[Moschops]

Your binary tree, if it is well written, allows you to change values stored in it. Without knowing how your particular binary tree has been made, though, we can't tell you how to use it.

[mythos061]

Here are the public functions of the tree:

tree(); //BaseData would equal student
~tree();
tree(tree<BaseData> &t); //copy constructor
tree<BaseData> & operator = (const tree<BaseData> &t); //assignment
void insert(BaseData &item); //insert into tree
void SearchAndDestroy(BaseData target); //search and destory node
void writeTree(int) ; //write tree traversals (prints to screen)
                      //1 for preorder
                      //2 for inorder
                      //3 for postorder
int fullTree() const; //is the tree full?
int emptyTree() const;//is the tree empty?

[Moschops]

Looks like your tree doesn't let you read from it, except to print the whole thing to screen. The only way I see with this to update something is actually to remove that data, and to put fresh data in, but this requires you to keep track yourself of the values so you know which one to delete, which makes it a bit silly.

[mythos061]

Is there a function I could add to retrieve the data from the tree?

[Moschops]

If you're writing this tree yourself, sure.

[mythos061]

Well yes I am, any hints?

[mythos061]

Anyone? I really am stuck, and cannot seem to figure it out.

[Moschops]

If you're written the binary tree in a way I would expect, you have a set of nodes. One of these nodes is especially privileged; it is the first node, or the start node, or the head node, or whatever else you want to call it. For practical purposes, this is the node that you start at whenever you are doing something with your tree.

Each node will contain some variation on the theme of a piece of data, and pointers to two sub-nodes. Some nodes might not have any sub-nodes. If you want to call these something special like end nodes or leaf nodes or some other such, that's up to your choice of terminology. It's common to call those two sub-nodes of a node its child nodes, and going the other way, parent node.

It's common (but not compulsory) for each node to also have a pointer to its parent node.

So, getting data from the tree. Start at the top node. The node you probably keep a pointer to in your program. If you're retrieving data, look at the node, and if it's the data you want, return a copy of the data. If it's not the data you want, you've now got to decide which of the two child-nodes to follow. If you have a sensible system for putting the data into the tree, it will be clear which to follow. Move to that node, and repeat (i.e. look at the node, and if it's the data you want, return a copy of the data, and if it's not, move on to the next child node). If you find that the child node you need to move on to does not exist, the data does not exist and return something meaningful to indicate that.

This is very much the sort of thing you should do on paper first, and only code when you've worked out what you're doing. This is programming; working out how to solve the problem in a way that lends itself to a programmatic implementation. The rest is memorising syntax and typing. Seriously; work out how to make your tree on paper first.

[mythos061]

Thanks for the response. You have helped me a lot so far. I already have built the tree, and it is working properly. Right now I am trying to come up with a search function that returns all the nodes in the tree that match a certain criteria. For example, I want to be able to list all students who have a major of CS. The problem is that everytime I find one student with a major of CS, it returns that pointer, and ends the search. I am trying to think about how I could search and return, but then leave off where I was searching from, and keep returing. So far no luck. Is there a better way to do this?

[mythos061]

Right now I am thinking I could declare a boolean in my node, and mark it true, if I returned it....

[Moschops]

You could update a pointer as you search indicating the last node you visited, and when you begin a search indicate if the search is to begin from the head or from the last visited node.

That's just off the top of my head; if you just sketch it out on paper and think about how you could do such things, you could come up with many other options. Maybe you could search the entire tree, and as you go, if you find what you're looking for don't return - just add it to a list or the like, and then when the function finally does return, you've got a list of all matches. The possibilities are endless.

[mythos061]

Thank you, I used the approach to create a temporary tree, and create a new inorder traversal to find all the nodes with a certain major that stores them in the temporary tree.
Thank you, thank you, thank you.