N-Ary tree represented in a Binary Tree

[ElPatoGarrido]

HI, i have to do a N-Ary tree and i followed the example of this page http://blog.mozilla.org/nnethercote/2012/03/07/n-ary-trees-in-c/, where the root only point to his first children, if the root have more children then they would be pointed by the other children (like a list where the head is the first son of the father).

So it's like this:

            R                          R
           /|\                         |
          B C D          ->            B -- C -- D
         / \  |                        |         |
        E   F G                        E -- F    G

Where each node have this structure:

struct node {
	string paquete;
	nodo *Brother;
	nodo *Son;
};

At first i have to input the root as i wish, then i have the insert the other nodes with a function where the user tells who's the father.

Now i have a big problem doing another function, i have to do a function where i see all the dependencies of 'x' node, so if the user want to know all the dependencies of 'F' i have to output: R->B->F, but it's dificult, because the N-Ary tree is actually a binary tree in my code, so i don't know how to output: R->B->F, because in the program the tree is literally like this.

R
|
B -- C -- D
|         |
E -- F    G

Sorry if my english is bad, and thanks for the help. If you don't understand something just tell me.

[ElPatoGarrido]

¿Nobody knows?

[ne555]

You'll need to search for `x' every time
By instance, using depth-first search

//not tested
std::stack<node*> dependencies;
dependencies.push(root);
while( not dependencies.empty() ){
	node *current = dependencies.top();
	if( *current == x ) return dependencies; //found it
	
	//expand the node
	if( current->son )
		dependencies.push( current->son );
	else if( current->brother ){ //leaf
		dependencies.pop();
		dependencies.push( current->brother );
	}
	else{ //right leaf
		//backtrack
		while( not dependencies.top()->brother )
			dependencies.pop();
		//`leaf' case
		node *aux = dependencies.top();
		dependencies.pop();
		dependencies.push(aux->brother;
	}
}

If you plan to do this a lot of times, maybe it would be better to put the parent in the node

struct node{
	node *parent;
	std::list<node> children;
};

[SIK]

my understanding/definition of n-ary trees seems different.

i understand them as trees where each node may have no more than [n] number of items.

this then logically allow for one to have [n+1] number of children for that node following basic tree rules (all smaller to left, while larger to right - however in this case its typically not binary ie a subtree Tx between any two items [i & k] in node N will have all its elements (in Tx) greater than i and less than k ...

typically n-ary trees are used for balanced trees - binary trees can become unbalanced leading to performance degradation. rebalancing an unbalanced binary tree can also be a very expensive operation.

n-ary trees breaks down into two specific balanced trees classes.

2-3 trees and 2-3-4 trees.

there are algorithms for inserting into these trees such that the tree always grows at the root and shrinks at root thus maintaining its balance. these algorithms are not straight forward. the insert algorithms for both are simpler than the delete algorithms.

however once you've managed to develope these for both the 2-3 and 2-3-4 tree, all other levels will follow the same pattern - ie for all n that is odd you would base on 2-3 tree logic and for all n even you would base on 2-3-4 logic.

incidentally red-black trees are normal binary trees in structure, but mimic 2-3-4 trees in that they represent all "internal" items/nodes within a 2-3-4 node with a red flag indicator while externals with a black flag indicator - this was done to save on space essentially - however it should be noted that red-black trees do not maintain perfect balance as is possible with a 2-3-4 tree.