Where to start with a binary tree?

Okay, this is my problem. I want to write a not so simple database using linked lists and a binary tree, but the data that I'm using consists of three categories.

It's a database for a movie rental store, it stores info for the customers, the employees and the inventory. There are also supposed to be three locations each with customers, employees and an inventory.

As I understand it, a binary tree can't have more than two children per node. This makes it rather difficult in designing a program that requires three children per node. Does anyone have any idea as to how I can start this program?

Well, per definition a binary tree has 2 children, however you may aswell have as many children as you want to, though it would not be a binary tree any more, just a linked list.

Please specify the problem a little more exact and I might be able to help you with the coding.

/Laos

Quite simply, I don't know how to build the tree with the data that I'm required to have. The three categories are employees, customers, and inventory. Each of those categories has a location, one of three total, and as far as I can determine the employee data has nothing to do with the customer data. However, the inventory data merges a bit with the customer data because the program should know if a customer has rented a movie.

This makes designing a binary tree difficult because some of the data doesn't have anything to do with the rest and some is a requirement for others. My problem is first building the tree with the data, then figuring out how to search the data. Everything else I can manage just fine.

It sounds like you have more problem with how to structure your data rather than implementing a binary tree. If all of the data is in one class/struct you could create three instances of your tree that stores pointers to your struct/class instances. You would insert the pointers in each tree based on the different category (your tree implementation would need to accept a pointer to a function for comparing the data). Then when you need a search based on a particular category you could use the relevant tree instance.

So I should create a generic binary tree class and three linked lists, one for each data category. Then I instance the binary tree class and pass it a pointer to each node of one of the linked lists. I do that three times to end up with three linked lists and three binary trees?

Also, is it possible to pass a void pointer to the binary tree so that I only have to create one tree class and pass it a void pointer that points to any one of the three linked list nodes?

Quote:

---

So I should create a generic binary tree class and three linked lists, one for each data category. Then I instance the binary tree class and pass it a pointer to each node of one of the linked lists. I do that three times to end up with three linked lists and three binary trees?

---

It's hard to say without knowing how you're storing the data, and what type of classes/structs hold it. In theory something like this should work but you probably wouldn't need three linked lists. One may be enough, just insert different parts of the list into each tree.

Quote:

---

Also, is it possible to pass a void pointer to the binary tree so that I only have to create one tree class and pass it a void pointer that points to any one of the three linked list nodes?

---

You could do it like this, but all the necessary casting would make the tree messy and error prone. It would be simpler to create a tree and nodes that use templates.

Quote:

---

It's hard to say without knowing how you're storing the data, and what type of classes/structs hold it. In theory something like this should work but you probably wouldn't need three linked lists. One may be enough, just insert different parts of the list into each tree.

---

At current I'm storing the data in three different classes, one for employess, one for customers, and one for inventory. The two classes for employees and customers are derived from an abstract person class.

If I don't need three linked lists, why not just use a dynamic array instead? That way I can partition the data better into three parts and I'd have direct access when I need it as well as the super fast searching of a binary tree.

Quote:

---

You could do it like this, but all the necessary casting would make the tree messy and error prone. It would be simpler to create a tree and nodes that use templates.

---

I figured I'd end up using templates, but I was asking that question to see if I could do it without templates and thus, create a similar program in C.

Quote:

---

If I don't need three linked lists, why not just use a dynamic array instead?

---

Yes, if you think it would make it easier. As I presume you'll just be using this initially to fill the tree I don't think it matters what data structure you use.

Quote:

---

but I was asking that question to see if I could do it without templates and thus, create a similar program in C.

---

If you want to make it possible to convert it to C more easily then you could do this, or if you're sure that you don't need to extend the functionality of the trees then you could always create three seperate tree implementations (they would share the majority of the code). Another alternative if you don't mind not being able to port to C easily would be to create a base tree class and deriving the seperate trees from this base. However I think using templates would still be easiest, as as long as you make the nodes templates the use of templates in your actual tree implementation would be minimal(you could implement a static comparison function in as part of your node).