CS 15-121 Introduction to Data Structures                 Lab 6

Complete Binary trees and Heaps
	1. Go through the slides in the link named “Main on Heaps Ch.10 ” on the course schedule.
	2. Draw a Complete Binary Tree with the data 0,1,2,3,4,5,6,7,8.
	3. Create a java project called “Trees”, and create a package named “trees” in it.
	4. Copy and paste the code that's provided below, creating new files for each class.
	5. Complete the “addNode” method in CompleteBinaryTree.java
	6. Draw a Max Heap with the data 0,1,2,3,4,5,6,7,8 inserted in order.
	7. Complete the methods “addNode” and “reheapificationupward” in Heap.java

**************************************************************************			TreeNode.java
package trees;

public class TreeNode {
    private int data;
    private TreeNode lchild;
    private TreeNode rchild;
    TreeNode parent;
    
    TreeNode()
    {
        data = 0;
        lchild = null;
        rchild = null;
        parent = null;
    }
    
    TreeNode(int d)
    {
        data = d;
        lchild = null;
        rchild = null;
        parent = null;
    }
    
    public int getData()
    {
        return data;
    }
    public void setData(int n)
    {
        data = n;
    }      
    public TreeNode getLchild()
    {
        return lchild;
    }
    public void setLchild(TreeNode n)
    {
        lchild = n;
    }
    public TreeNode getRchild()
    {
        return rchild;
    }
    public void setRchild(TreeNode n)
    {
        rchild = n;
    }
     
    
}

**************************************************************************
				Queue.java
package trees;


public class Queue {
    TreeNode arr[];
    int front;
    int rear;
    int length = 0;
    
    Queue()
    {
        arr = new TreeNode[30];
        front = 0;
        rear = 0;
    }
    
    void insert(TreeNode n)
    {
        arr[rear++] = n;
        length++;
    }
    
    TreeNode remove()
    {
        if(!(front>rear))
        {
            length--;
            return arr[front++];
        }
        return null;
    }
    
    TreeNode getFront()
    {
        return arr[front];
    }
    
    int getLength()
    {
        return length;
    }
    
    boolean isEmpty()
    {
        return (front==rear) ? true:false;
    }
    
}
**************************************************************************
					CompleteBinaryTree.java
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package trees;

/**
 *
 * @author Aradhana
 */
public class CompleteBinaryTree {
    
    TreeNode root;
    Queue q_add = new Queue();
    Queue q = new Queue();
    
    CompleteBinaryTree()
    {
        root = null;
    }
    
    public void addNode(int n)
    {
        /*
            1.Create a new treenode with data n, called t.
            2.If the root is null, set root to t.
            3.If root is not null, get the front of the queue, q_add.
            4.If the left child of front of queue is null, insert t as the left child.
            5.Otherwise, if the right child of front of queue is null, insert t as the right child.
            6.If both left and right children of front of queue are null, remove front of queue.
            7.Insert t into the queue.
        */       
        
    }
    
     public void LevelOrderTraversal()
    {
        LevelOrderTraversal(root);
    }
    
    public void LevelOrderTraversal(TreeNode t)
    {
        if(t==null)
        { 
            return;
        }
            q.insert(t);
            while(!q.isEmpty())
            {
                TreeNode node = q.remove();
                System.out.println(node.getData());
            
            if(node.getLchild()!=null)
                q.insert(node.getLchild());
            if(node.getRchild()!=null)
                q.insert(node.getRchild());
            }
                
    }
    
    
    public static void main(String args[])
    {
        CompleteBinaryTree cbt = new CompleteBinaryTree();
        cbt.addNode(0);
        cbt.addNode(1);
        cbt.addNode(2);
        cbt.addNode(3);
        cbt.addNode(4);
        cbt.addNode(5);
        cbt.addNode(6);
        cbt.addNode(7);
        cbt.addNode(8);
        cbt.LevelOrderTraversal();
        int len = cbt.q.getLength();
         for(int i=0;i<len;i++)
            {
                System.out.println(cbt.q.remove());
            }
    }
    
}
**************************************************************************
					Heap.java

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package trees;

/**
 *
 * @author Aradhana
 */
public class Heap {
    
    TreeNode root;
    Queue q_add = new Queue();
    Queue q = new Queue();
    
    Heap()
    {
        root = null;
    }
    
    public void addNode(int n)
    {
        
        /*
        This is similar to the addnode method in the complete binary tree. There are, however, a few extra steps to keep in mind.
        1.We will use the "parent" property in the TreeNode class to implement a heap.
        2.As you insert a new node as a child of a node, be sure to set the child's parent.
        3.As soon as you insert an element, call the reheapificationupward method on the newly inserted node.
        */
        
    }
    
    
    void reheapificationupward(TreeNode t)
    {
        //this method needs to continuously swap t's data with its parent's data and update t, until parent's data is greater than t's data.
    }
    
       
    public void LevelOrderTraversal()
    {
        LevelOrderTraversal(root);
    }
    
    public void LevelOrderTraversal(TreeNode t)
    {
        if(t==null)
        { 
            return;
        }
            q.insert(t);
            while(!q.isEmpty())
            {
                TreeNode node = q.remove();
                System.out.println(node.getData());
            
            if(node.getLchild()!=null)
                q.insert(node.getLchild());
            if(node.getRchild()!=null)
                q.insert(node.getRchild());
            }
                
    }
    
    
    public static void main(String args[])
    {
        Heap heap = new Heap();
        heap.addNode(0);
        heap.addNode(1);
        heap.addNode(2);
        heap.addNode(3);
        heap.addNode(4);
        heap.addNode(5);
        heap.addNode(6);
        heap.addNode(7);
        heap.addNode(8);
        heap.LevelOrderTraversal();
        int len = heap.q.getLength();
         for(int i=0;i<len;i++)
            {
                System.out.println(heap.q.remove());
            }
    }
    
}