structure of n-ary tree
Class:Node
String:label
List<Node> children
Method
List<Node> TreeToLinkedList(Node n)
{
return list;
}
return List of all nodes;
[image: image.png]Pics Taken From Google Image .
N-Ary Tree
Output head-> 1-2-3-4-5-6-7-8-9
My Approach , Correct me if any thingwong ?
Analysis:
We Have to Traverse the tree from root to leaf node for all nodes , level
by level & keep appending the nodes at given level in
already existing linked list als at each level we can have many nodes. so
each level can have sublist e.g. each node can have many children.
so basically our structure will like list of list. e.g. finaly list has all
nodes of N-Ary tree .
Algorithm:Breadth First Search:
Start from root of N-Ary Tree & Points head of linked list to root of tree .
for each level starts from i=0 to height(tree)
append all nodes at given level to already appended node to linked list
return list containging all the nodes of N-Ary Tree
Psuedo Code:
Class Node
{
String label;
List<Node> children;
}
int height(Node node)
{
if (node==NULL)
return 0;
else
{
/* compute the height of each subtree */
int lheight = height(node.left);
int rheight = height(node.right);
/* use the larger one */
if (lheight > rheight)
return(lheight+1);
else return(rheight+1);
}
}
public List<Node> NAryTreetoLinkedList(Node root)
{
List<Node> subList=new LinkedList<Node>();
List<subList> list=new LinkedList<subList>();
Node node=new Node();
for(int i=1;i<=height(root);i++)
{
//Logic
/*foreach node in tree
append its children to linked list in end.
sublist.add(n.children))
list=list.next
*/
foreach(Node node:subList)
{
subList.add(node); // add
}
list.add(subList);//add sublist level by level to original list
list=list.getNext();//incerement pointer to next node in main
linked list.
subList=new LinkedList<Node>();//Create New Sublist & repeat
same untill depth of tree
}
return list;
}
Time Complexity O(n*max(all nodes having children (say it m))=o(n*m)
Let Me What Other Thinks or Something wrong in my pseudo code ??
Shashank
Computer Science
Birla Institute of Technology,Mesra
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/xvOpoON4E_oJ.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
