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 !

 

[vinkesh79]

you might have to use linked list.
declare a parent and a child.
initially the parent & child will pt to the 1st node.

now the implementation part:
check whether parent is null ( for no elements)
if not increment the child till child->next==NULL;
then copy the element which u want 2 insert i.e
child->next=temp;temp->next=NULL;
once u can insert follow the same procedure for everything else

 

[Salem]

If a binary tree is just

struct node {
    int data;
    struct node *left;
    struct node *right;
};

Isn't an N-ary tree

struct node {
    int data;
    struct node *children[N];
};

 

[Salem]

Maybe this site will help

http://www.nist.gov/dads/

 

[lionelhill]

As a matter of interest, what do you use n-ary trees for? I can see that binary ones are very useful because they reflect exactly the "greater-than/less-than/wow-i've-found-it" comparison when I'm searching for a particular entry, and maximise efficiency of search. I can't see at first glance how a higher tree-order helps much.
Anyone know anywhere where I can find out more (for fun)?

 

[Leibnitz]

lionehill,
with a binary tree,you only have two choices at each node and in my current problem,i need to have more than that.
Example,i might need to have between 1 and 10 branches per
node,maybe less.I can't do this with a binary tree.

Thanks Salem for the site,i had checked it before.

vinkesh79 you seems to catch the idea,can you be more specific on how per example i could write each node,since Salem had pointed out that:

struct node {
int data;
struct node *children[N];
};

wouldn't work.

This is what i have found so far,the structure for the nodes might look like this:

struct node
{
int data;
node *parent;
node *first_child, *last_child;
node *prev_sibling, *next_sibling;
};

but i dont know how it would work for the implementation part.

For people who are interested,i've also found this site about data structures and algorithms:

http://www.brpreiss.com/books/opus4/html/page9.html

 

[vinkesh79]

As u know there r 2 paths in a BTree.
So u need lchild & rchild in ur structure.

initiall ur ur first node will b ur parent .
I have 4gotten the exact concept of how to traverse in a binary tree i.e where 2 go first (left or right) so u have to decide. i am assuming right.

now check parent->rchild==NULL (conider this case is true)
now check parent->lchild==NULL.
if this is also true then u to the right and insert there.
everytime u will check right first(remember i am assuming that v will traverse right)
put this in a loop.

hope i have helped u.
bye

 

[Leibnitz]

Thanks for replying,however i would like to know how to implement the stucture for the nodes,for a binary it is pretty simple:

struct node {
int data;
node *right;
node *left;
};

but what would it be for a n-ary tree?
any hint is very welcome !

 

[vinkesh79]

hey no probs
i am sorry i did not get ur question?

the only structure u need is

struct node
{
int data;
struct node *lnode;
struct node *rnode;
};
typedef struct node *NODE;

if u r not clear dont hesitate 2 ask

 

[lionelhill]

Well, the two ways that leap out are
(1) an array of next-nodes (traverse by for-next loop)
(2) a linked list of next-nodes (traverse by scanning the entire linked list; more work, but allows a variable number of next nodes). In this case your node structure just has to hold a pointer to the head of the linked list.

 

[Leibnitz]

thanks vinkesh79 and lionelhill for replying.

winkesh79,the structure that you have post looks more like the one that we use for a binary tree,do you really think that it would also work for a n-ary tree?

lionelhill,your second idea looks fine,i will probably use this technic to build the n-ary tree.

 

[Clairvoyant1332]

The structure you would use for an n-ary tree would be the following:

const int n={some number};

struct node {
  int data[n];
  struct node *childptr[n+1];
};

What you have here is n data elements and n+1 children. For element

data[n]

, anything under

childptr[a]

with a<=n is less and anything under

childptr[b]

with b>n is greater.

The rules for a B-Tree are a little more stringent than this so that all leaf nodes are at the same level.

Dennis

 

[Leibnitz]

Thanks for replying Clairvoyant1332,your technic looks very simple! I will take some time to try it.