Hello All,

I would like to implement a tree with the following properties.

1. The tree is balanced.
2. Each node has a max of 5 sub nodes and min of ceil(5/2) sub nodes.
3. The tree remains static. Number of nodes known from the beginning.

What is the data structure that I can use to implement this?

Thanks,
Vandana.

Vandana wrote:
A struct.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.

Vandana wrote:
) Hello All,
)
) I would like to implement a tree with the following properties.
)
) 1. The tree is balanced.
) 2. Each node has a max of 5 sub nodes and min of ceil(5/2) sub nodes.
) 3. The tree remains static. Number of nodes known from the beginning.
)
) What is the data structure that I can use to implement this?

If it really is static, make it an array.
Each node will have exactly 5 sub nodes except for the very last one.
Finding sub nodes involves a simple calculation in the array index:
subnode(i) = i*5 + 5 + subnode

SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

CBFalconer schrieb:
called "struct".

1. & 2. sound like B-tree, I don't understand requirement 3.

Christian

Christian Gollwitzer wrote:
My first guess, is that it is supposed to be.

It's a keyword in C.

I think that means that it doesn't have to be dynamically allocated.
Every once in a while I see somebody post code, or stories,
about a linked list
where all of the nodes are located in an array of nodes.
I've never been able to remember the explanation of why
somebody would write code like that.

--
pete

Christian Gollwitzer wrote:
What joke? Assuming the use of C, you define a struct with the
appropriate qualities:

typdef struct node {
whatever datum; /* node contents */
int activecount;
struct node *subnodes[5];
} node, *nodeptr;

should do it. Your problem is to write code that maintains the
conditions that you want.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.