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

Stack Implemention in Java

  Stack Implementation [Static and Dynamic] in                                 Java

A Stack is a ordered list in which insertion and deletion are done at one end,calles as top.The last element inserted is the first one to be deleted.

Hence,it is called LAST IN FIRST OUT(LIFO)  and FIRST IN LAST OUT(FILO).

Stack ADT

->void push(String data)    :-         Insert data into stack

->String pop()                    :-          Delete data from top of statck.

Applications:-

• Balancing of symbols.
• Infix-to-postfix operation.
• Evaluation of postfix expression.
• Implementing function calls(including recursion).
• Page-visisted history in a Web Browser(Back Buttons).
• Undo sequence in a text Editor.
• Matching Tags in HTML and XML.

Implementations:-

These examples is given for only stack of strings and in which input as String separated by one space means push that two strings in stack and Hyphen i.e.(-) means perform pop operation.

e.g.

Hi I - am - 

means     

                    push("Hi")

                    push("I")

                    pop()

                    push("am")

                    pop()

                               Fixed size Array Implementation in Java.

Java Program:-

/**
 * @(#)FixedCapacityStack.java
 *
 *
 * @author 
 * @version 1.00 2015/3/2
 */

import java.io.*;
import java.util.*;


class FixedSizeStringStack{

private String s[];
private int top=0;

public FixedSizeStringStack(int N){
s=new String[N];
}

public void push(String data){
if(top==s.length){
System.out.println("OverFlow...");
return;
}
s[top++]=data;
}

public String pop(){
if(top==0){
System.out.println("UnderFlow");
return null;
}
String data=s[--top];
s[top]=null;
return data;
}

public boolean isEmpty(){
return top==0;
}


}

class FixedCapacityStack {

    public static void main(String ar[])throws IOException{
   
   
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer str=new StringTokenizer(br.readLine());
    FixedSizeStringStack s=new FixedSizeStringStack(10);
   
    String input=str.nextToken();
   
    while(true){
   
    if(input.equals("-")){
    System.out.print(s.pop()+" ");
    }else{
    s.push(input);
    }
   
    if(str.hasMoreTokens()){
    input=str.nextToken();
    }else{
    break;
    }
    }
   
   
    }
    
    

}
 

                                    Dynamic Implementation of Stack in Java.

Java Program:-


/**
 * @(#)StackOfStrings.java
 *
 *
 * @author Suyash Bhalla
 * @version 1.00 2015/3/2
 */

import java.io.*;
import java.util.*;


class StringStack{

private Node first=null;

private class Node{
String data;
Node next;
}

public void push(String s){
Node temp=new Node();
temp.data=s;
temp.next=first;
first=temp;
}

public String pop(){
String data=first.data;
first=first.next;
return data;
}

public boolean isEmpty(){
return first==null;
}
}


class StackOfStrings {

    public static void main(String ar[])throws IOException{
   
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer str=new StringTokenizer(br.readLine());
    StringStack s=new StringStack();
   
    String input=str.nextToken();
   
    while(true){
   
    if(input.equals("-")){
    System.out.print(s.pop()+" ");
    }else{
    s.push(input);
    }
   
    if(str.hasMoreTokens()){
    input=str.nextToken();
    }else{
    break;
    }
    }
    }
    

}



Input:-
to be or not to - be - - that - - - is

Output:-
to be not that or be


Performance:-

push operation               =>       O(1)

pop operation                 =>       O(1)

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