Generic Trees

                 Generic Trees(N-ary Trees)

As in Binary Tree  we cannot have more than two child of each node,so how we can represent a tree in which we don't know how many child are there for each node(As one can have 6,7,or any no. of child).And the other Question is that how we represent them??????????

Let us take an example of following tree:-

TREE

 Bad Approach:-

To Represent this tree we have to take maximum no. of child,any node have in a tree (i.e A is having 4 Child).So, we have to create Node of having 4 child.As:-

class Node{

              int data;

              Node firstChild;

              Node secondChild;

              ............

}   

DisAdvantages:-

• As we are not using all the pointers in all the cases there is a lot of memory wastage.
• In advance we do not know the no. of children for each  node.

Hence,we need a representation which overcome these disadvantages.

First Child/Next Sibling Representation

• At each node link children of same parent(i.e siblings) from left to right.
• Remove the links from parent to all children except the first Children.

The above tree is represented as:-

Generic Tree Representation

Tree Node Declaration can be given as:-

/**

 * @(#)Node.java

 *

 *

 * @author suyash Bhalla

 * @version 1.00 2015/3/29

 */

public class Node {

      public int data;

      public Node firstChild;

      public Node nextSibling;

    

      public int getData(){

         return data;

      }

    

      public void setData(int data){

         this.data=data;

      }

    

      public Node getFirstChild(){

         return firstChild;

      }

    

      public void setFirstChild(Node firstChild){

          this.firstChild=firstChild;

      }

      public Node getNextSibling(){

          return nextSibling;

      }

    

      public void setNextSibling(int nextSibling){

         this.nextSibling=nextSibling;

      }

    

}

----------------X------------------X---------------X-----------------X