Tuesday, December 4, 2012

CSC438 - DATA STRUCTURE - LAB BINARY TREE






package LAB_9_TREE; 

 class BinaryTreeNode {
    
    int data;
    BinaryTreeNode right;   
    BinaryTreeNode left;
    
    
    BinaryTreeNode(int a)
    {
        this.data = a;
    } 
  
}

public class BinaryTree {
    
    protected BinaryTreeNode root;
    
    // DEFAULT CONSTRUCTOR
    public BinaryTree()
    { 
        root = null; 
    }
    
    // DESTROY THE BINARY TREE
     public void destroyTree ()
    {
         root = null;
    }
    
    //DETERMINE WHETER THE BINARY TREE IS EMPTY
    public boolean isEmpty()
    {
        return ( root == null );          
    }
    // DETERMINE THE HEIGHT OF THE BINARY TREE
    public int treeHeight()
    {         
        return height(root);
    }    
    
    // A RECURSIVE FUNCTION TO GET THE HEIGHT OF THE BINARY TREE
    public int height( BinaryTreeNode p )
    {
        if ( p == null )
            return 0;
        else
            return 1 + max(height(p.left),height(p.right) );
        
    }
    
    // COMPARE THE TWO VALUE FROM THE LEFT AND THE RIGHT NODE
    public int max( int x,int y)
    {
        if ( x >= y )
            return x;
        else
            return y;
        
    }
    
    
    
    //INSERT A NEW NODE INTO THE BINARY TREE
    public void insertNode(int item)
    {
        BinaryTreeNode current;
        BinaryTreeNode trailCurrent = null;
        BinaryTreeNode newNode;
        
        newNode = new BinaryTreeNode(0);
        
        newNode.data = item;
        newNode.left = null;
        newNode.right = null;
        
        if(root == null)
            root = newNode;
        else
        {
            current = root;
            while(current != null)
            {
                trailCurrent = current;
                if(current.data == item)
                {
                    System.err.print("The insert item is already in the list. Duplicate item are not allowed");
                    return;
                    
                }
                else
                    if(current.data < item)
                        current = current.left;
                    else
                        current = current.right;
                       
            }
             
            if(trailCurrent.data < item)
                trailCurrent.left = newNode;
            else
                trailCurrent.right = newNode; 
            
        }
        
    }
      
}

============================================================



package LAB_9_TREE; 

import javax.swing.*;

public class TestBinaryTree 
{

    public static void main(String[] args)
    {
        BinaryTree tree = new BinaryTree(); 
        int value;
        System.out.println("Inserting the following values : ");
        
        for ( int i = 0; i < 10 ; i++)
        {
            value = (int) (Math.random()*100);
            System.out.print(value + " "); 
            tree.insertNode(value);
        } 
    } 
}

/*
  
 The output :
 
 Inserting the following values : 
 45 60 63 72 67 20 1 28 99 30
 
  
  
 */


1 comment:

  1. This comment has been removed by a blog administrator.

    ReplyDelete

Say whut you want, but be responsible on whut you said...