n-ary trees

[Leibnitz]

I need some help for implementing a n-ary tree.I have found information on the internet on how to implement a binary tree and binary search tree,but i still can't figure out how to use the same procedure to write some code for a n-ary tree.I need to be able to do the following operation on the tree: insert node,delete node,set empty,print nodes,comparing trees.

Any hint is very welcome !

 

[BoulderBum]

I was thinking about this the other day, and figured I would just start with a Node class containing vector of pointers to other nodes. (I suppose a linked list of Node pointers would work, too).

For inserting, each Node would have to keep track of its own "add" range of criteria. Exactly how you accomplish this depends on what exactly you hope to do with the class.

Printing can simply involve sending a recursive print message through each of a parent node's child nodes, then calling print on itself. Depends on the order you want to print, and what your specific requirements are.

Um, maybe that will help.

 

[Leibnitz]

BoulderBum,thanks for replying !
I want to build the tree from scratch so i wont probably use vectors to do it,anyway i dont know how to use them.
What i would want to do with the class is just the basic operations that we do on binary tree(insert,add,delete...) nodes from the tree.For the first implementation of the code,i would start with a tree that contain integers only,each node could have between 1 an 10 branches,maybe less.

 

[javaguy1]

im curious as to the purpose(need) for such a tree. i just dont get it. if it is a tree of int for example, an int can only be less than, greater than, or equal to another node, therefore a binary tree. do you have an actual need for such a tree? if so what are the criteria for which branch to follow?

 

[Leibnitz]

Well,actually i want to implement a tree that will have strings instead of numbers in it.Each string could be related to many other strings.

Example: the word computer is related to software and hardware,a hardware can be(screen,keyboard,mouse,...).A sofware can be(mathematical software,drawing software,...). A sreen can be( flat screen, monochrome screen,color screen,...) etc.

I hope that you've get the idea!

 

[javaguy1]

ok, i can see it in my mind now, but i dont see how the program will be able to decide where to put a new node. good luck.

 

[Leibnitz]

I will decide where to put each node.

 

[BoulderBum]

"I want to build the tree from scratch so i wont probably use vectors to do it,anyway i dont know how to use them."

In that case, I'd build a linked-list data structure from scratch, then have a Node class containing a linked list of new Nodes.

 

[Leibnitz]

would it be a singly or doubly-linked list? For the implementation of the linked-list i have some idea of how to do it.But how the class that contain the linked list of new Nodes would look like?

 

[BoulderBum]

I would say doubly so you're not limited to sending messages left to right through the child nodes, and you can insert a child node before the first one inserted.

How would it look like? Something like:


Node
{
private DoublyLinkedList nodeLinks(); //list of Nodes
}

Err, I guess that wasn't super helpful, but the structure would visually look something like this:

[tt]

Node
/
Node2-Node
/ Node1 Node
Node3
Node


[/tt]

In Node1's doubly linked-list, there are two Nodes: Node2 and Node3. Node2's linked-list has 3 Nodes, and, of course, Node3's linked-list contains 1 Node.

A recursive print message might be as simple as saying:


print_Function()
{
for every Node less than parent
print_Funtion( each smaller Node )

print contents of current Node

for every Node greater than parent
print_Funtion( each larger Node )
}


The insert function, as mentioned, depends on the range of values you wish to hold in each node. It would be requirements specific.

 

[PerFnurt]

If the nodes' key values are all unique I'd you could put them in a std::map (or std::multimap if they aren't unique), rather than a linked list (I'd recomend std::list prior to making your own).

1) You wouldn't have to worry about implementation.
2) Retrieval/manipulation is fast.

But then, I'm not entirly sure about the intended use for your structure...

/Per
_{Nerdy signatures are as lame as the inconsistent stardates of STTNG.}

 

[Leibnitz]

Thanks again for replying BoulderBum,i think that i've get the idea of what you meant by using nodes of doubly-linked list,i will try to apply this idea.However,since i will not use numbers in the n-ary tree,my print_Function will probably look different.Actually,the components of the tree will be strings instead of numbers.

Thanks for your suggestions PerFnurt,but i really intend to build the tree from scratch.