//Dipen Patel
//CSC-236
//LAB6-PART A
public class TreeNode {
private int value, pos;
private TreeNode left, right;
public TreeNode()
this(0,0);
public TreeNode(int value)
this(value,0);
public TreeNode(int value, int pos)
this.value = value;
this.pos = pos;
this.right = null;
this.left = null;
public int getValue()
return value;
}
public void setValue(int value)
this.value = value;
public TreeNode getLeft()
return left;
public void setLeft(TreeNode left)
this.left = left;
public TreeNode getRight()
return right;
public int getPos()
return this.pos;
public void setPos(int pos)
this.pos = pos;
}
public void setRight(TreeNode right)
this.right = right;
public String toString()
return value + " ";
}
//Dipen Patel
//CSC-236
//LAB6-PART A
public interface BTInterface {
public abstract TreeNode getRoot();
//gives the root of the tree
public abstract void setRoot(TreeNode root);
//used to set the root
public abstract int getNumOfSingleParent();
//Returns the number of single parents in the tree
public abstract void insert(int value);
//inserts the int value in accordance to BST rules
public abstract void doSwap();
//initialize swapping
public abstract void doPreOrder();
//prints the tree in preorder
public abstract void doInOrder();
//prints the tree in inorder
public abstract void doPostOrder();
//prints the tree in postorder
}
//Dipen Patel
//CSC-236
//LAB6-PART A
public class BinaryTree extends TreeNode implements BTInterface {
private TreeNode root;
private int numOfSingleParent;
public BinaryTree() {
this.root = null;
this.numOfSingleParent = 0;
public BinaryTree(int value) {
this.root = new TreeNode(value);
this.numOfSingleParent = 0;
public TreeNode getRoot() {
return root;
public void setRoot(TreeNode root) {
this.root = root;
public int getNumOfSingleParent() {
this.numOfSingleParent = 0;
singleParent(this.root);
return this.numOfSingleParent;
public void insert(int value) {
TreeNode x = new TreeNode(value);
if (this.root == null) {
this.root = x;
} else {
TreeNode curr = this.root;
TreeNode prev = curr;
while (curr != null) {
prev = curr;
if (value < curr.getValue()) {
curr = curr.getLeft();
} else {
curr = curr.getRight();
if (value < prev.getValue()) {
prev.setLeft(x);
} else {
prev.setRight(x);
}
public void doSwap() {
swap(this.root);
private void swap(TreeNode curr) {
if (curr.getLeft() != null) {
swap(curr.getLeft());
if (curr.getRight() != null) {
swap(curr.getRight());
if (curr.getLeft() != null || curr.getLeft() != null) {
TreeNode temp = curr.getLeft();
curr.setLeft(curr.getRight());
curr.setRight(temp);
private void singleParent(TreeNode curr) {
if (curr.getLeft() != null) {
singleParent(curr.getLeft());
if (curr.getRight() != null) {
singleParent(curr.getRight());
if ((curr.getRight() != null && curr.getLeft() == null) ||
(curr.getRight() == null && curr.getLeft() != null)) {
this.numOfSingleParent++;
public void doPreOrder() {
preOrder(this.root);
private void preOrder(TreeNode curr) {
if (curr != null) {
System.out.print(curr);
preOrder(curr.getLeft());
preOrder(curr.getRight());
public void doInOrder() {
inOrder(this.root);
private void inOrder(TreeNode curr) {
if (curr != null) {
inOrder(curr.getLeft());
System.out.print(curr);
inOrder(curr.getRight());
public void doPostOrder() {
postOrder(this.root);
private void postOrder(TreeNode curr) {
if (curr != null) {
postOrder(curr.getLeft());
postOrder(curr.getRight());
System.out.print(curr);
}
//Dipen Patel
//CSC-236
//LAB6-PART A
public class BinarySearchTree extends BinaryTree{
private TreeNode root;
private int lastPos;
private int numOfSingleParent;
public BinarySearchTree()
this.root = null;
this.lastPos = -1;
public BinarySearchTree(int value)
this.root = new TreeNode(value);
this.lastPos = 0;
public TreeNode getRoot()
return root;
public void setRoot(TreeNode root)
this.root = root;
}
public int getLastPos()
return this.lastPos;
public void setLastPos(int lastPos)
this.lastPos = lastPos;
public int getNumOfSingleParent()
this.numOfSingleParent = 0;
singleParent(this.root);
return this.numOfSingleParent;
public TreeNode find(int pos)
if(pos < 0)
return null;
else if(pos == 0)
return this.root;
else
TreeNode curr = this.root;
pos++;
while(pos > 1)
if(pos % 2 == 0)
curr = curr.getLeft();
else
curr = curr.getRight();
pos = pos / 2;
return curr;
}//else pos > 0 ends
public void insert(int value)
TreeNode temp = new TreeNode(value, lastPos + 1);
if(this.root == null)
this.root = temp;
else
if(lastPos % 2 == 0)
find(lastPos / 2).setLeft(temp);
else
find(lastPos / 2).setRight(temp);
}//else root != null, ends
lastPos++;
public void doSwap()
swap(this.root);
private void swap(TreeNode curr)
if(curr.getLeft() != null)
swap(curr.getLeft());
if(curr.getRight() != null)
swap(curr.getRight());
if(curr.getLeft() != null || curr.getLeft() != null)
TreeNode temp = curr.getLeft();
curr.setLeft(curr.getRight());
curr.setRight(temp);
private void singleParent(TreeNode curr)
{
if(curr.getLeft() != null)
singleParent(curr.getLeft());
if(curr.getRight() != null)
singleParent(curr.getRight());
if((curr.getRight() != null && curr.getLeft() == null) ||
(curr.getRight() == null && curr.getLeft() != null))
this.numOfSingleParent++;
public void doPreOrder()
preOrder(this.root);
private void preOrder(TreeNode curr)
if(curr != null)
System.out.print(curr);
preOrder(curr.getLeft());
preOrder(curr.getRight());
}
public void doInOrder()
inOrder(this.root);
private void inOrder(TreeNode curr)
if(curr != null)
inOrder(curr.getLeft());
System.out.print(curr);
inOrder(curr.getRight());
public void doPostOrder()
postOrder(this.root);
private void postOrder(TreeNode curr)
if(curr != null)
postOrder(curr.getLeft());
postOrder(curr.getRight());
System.out.print(curr);
}
//Dipen Patel
//CSC-236
//LAB6-PART A
public class TreeDemo {
public static void main(String[] args)
//Tree 1 -- Binary Complete Tree
BinarySearchTree compTreeObj = new BinarySearchTree();
for(int i = 1; i < 7; i++)
compTreeObj.insert(i);
System.out.println("\t\tA regular Binary Tree");
System.out.println("---------------------------------"
+ "-----------------------------");
System.out.print("Inorder traversal: ");
compTreeObj.doInOrder();
System.out.print("\nPostorder traversal: ");
compTreeObj.doPostOrder();
System.out.print("\nPreorder traversal: ");
compTreeObj.doPreOrder();
System.out.println("\n*******************************"
+ "*******************************");
System.out.println("\n---------------------------------"
+ "-----------------------------");
compTreeObj.doSwap();
System.out.println("\t\tAfter Swapping...");
System.out.println("---------------------------------"
+ "-----------------------------");
System.out.print("Inorder traversal: ");
compTreeObj.doInOrder();
System.out.print("\nPostorder traversal: ");
compTreeObj.doPostOrder();
System.out.print("\nPreorder traversal: ");
compTreeObj.doPreOrder();
System.out.println("\n*******************************"
+ "*******************************");
System.out.println("\nThe total number of single parent/s is: "
+ compTreeObj.getNumOfSingleParent());
System.out.println("\n---------------------------------"
+ "-----------------------------");
//Tree 2 -- Binary Search Tree
BinaryTree bSTreeObj = new BinaryTree();
bSTreeObj.insert(14);
bSTreeObj.insert(15);
bSTreeObj.insert(4);
bSTreeObj.insert(3);
bSTreeObj.insert(9);
bSTreeObj.insert(7);
bSTreeObj.insert(5);
bSTreeObj.insert(18);
bSTreeObj.insert(16);
bSTreeObj.insert(20);
bSTreeObj.insert(17);
System.out.println("\t\tA regular Binary Search Tree");
System.out.println("---------------------------------"
+ "-----------------------------");
System.out.print("Inorder traversal: ");
bSTreeObj.doInOrder();
System.out.print("\nPostorder traversal: ");
bSTreeObj.doPostOrder();
System.out.print("\nPreorder traversal: ");
bSTreeObj.doPreOrder();
System.out.println("\n*******************************"
+ "*******************************");
bSTreeObj.doSwap();
System.out.println("\n---------------------------------"
+ "-----------------------------");
System.out.println("\t\tAfter Swapping.");
System.out.println("---------------------------------"
+ "-----------------------------");
System.out.print("Inorder traversal: ");
bSTreeObj.doInOrder();
System.out.print("\nPostorder traversal: ");
bSTreeObj.doPostOrder();
System.out.print("\nPreorder traversal: ");
bSTreeObj.doPreOrder();
System.out.println("\n*******************************"
+ "*******************************");
System.out.println("\nThe total number of single parent/s is: "
+ bSTreeObj.getNumOfSingleParent());
System.out.println("---------------------------------"
+ "-----------------------------");
}
OUTPUT:-
//Dipen Patel
//CSC-236
//LAB6-PART B
public interface HeapPriorityQueue
public abstract HeapTreeNode getRoot();
//gives the root of the tree
public abstract void setRoot(HeapTreeNode root);
//used to set the root
public abstract void insert(int value);
//inserts the int value in accordance to Heap tree rules
public abstract void remove();
//removes the root from a non-empty heap
public abstract void doPreOrder();
//prints the tree in preorder
public abstract void doInOrder();
//prints the tree in inorder
public abstract void doPostOrder();
//prints the tree in postorder
}
/Dipen Patel
//CSC-236
//LAB6-PART B
public class HPTree implements HeapPriorityQueue{
private HeapTreeNode root;
private int lastPos;
public HPTree()
this.root = null;
this.lastPos = -1;
public HPTree(int value)
this.root = new HeapTreeNode(value);
this.lastPos = 0;
public HeapTreeNode getRoot()
return root;
public void setRoot(HeapTreeNode root)
this.root = root;
}
public int getLastPos()
return this.lastPos;
public void setLastPos(int lastPos)
this.lastPos = lastPos;
public HeapTreeNode find(int pos)
if(pos < 0)
return null;
else if(pos == 0)
return this.root;
else
HeapTreeNode curr = this.root;
pos++;
int i = -1;
int [] storeDir = new int[10];
while(pos > 1)
if(pos % 2 == 0)
storeDir[++i] = 0;
else
storeDir[++i] = 1;
pos = pos / 2;
while(i >= 0)
if(storeDir[i] == 0)
curr = curr.getLeft();
else
curr = curr.getRight();
i--;
return curr;
}//else pos > 0 ends
public void insert(int value)
HeapTreeNode temp = new HeapTreeNode(value, lastPos + 1);
if(this.root == null)
this.root = temp;
else
{
if(lastPos % 2 == 0)
find(lastPos / 2).setLeft(temp);
else
find(lastPos / 2).setRight(temp);
}//else root != null, ends
swapInsert(temp);
lastPos++;
private void swapInsert(HeapTreeNode curr)
if(curr != null)
HeapTreeNode parent = find((curr.getPos() - 1) / 2);
//if the value inside the curr node is greater than its parent
//then, the values of the parent and the curr will interchange.
if(curr.getValue() > parent.getValue())
int temp = curr.getValue();
curr.setValue(parent.getValue());
parent.setValue(temp);
swapInsert(parent);
}
public void remove()
if(this.lastPos > 0)
//parent of the last node entered
HeapTreeNode lastParent = find((lastPos - 1) / 2);
//sets the last node's value into the root's value
//and setting the parent's pointer
//pointing to the last node to null
if(lastPos % 2 == 0)
//if the last node was a right child
this.root.setValue(lastParent.getRight().getValue());
lastParent.setRight(null);
else
//if the last node was a left child
this.root.setValue(lastParent.getLeft().getValue());
lastParent.setLeft(null);
swapRemove(this.root);
else
{ //if the lastPos == 0, or the tree has just the root node
this.root = null;
this.lastPos--;
}
private void swapRemove(HeapTreeNode curr)
//if the left node is null,
//curr doesn't have even the right child
if(curr.getLeft() != null)
HeapTreeNode left = curr.getLeft();
if(curr.getRight() != null)
HeapTreeNode right = curr.getRight();
//if the left has the largest value
if(left.getValue() > right.getValue()
&&
left.getValue() > curr.getValue())
//swap the values and
//recurse using the left as a new parent/root
int temp = curr.getValue();
curr.setValue(left.getValue());
left.setValue(temp);
swapRemove(left);
//if the right has the largest value
else if(right.getValue() > left.getValue()
&&
right.getValue() > curr.getValue())
//swap the values and
//recurse using the right as a new parent/root
int temp = curr.getValue();
curr.setValue(right.getValue());
right.setValue(temp);
swapRemove(right);
}//if(right != null), ends
//else if(..), right == null but left != null
else if(left.getValue() > curr.getValue())
//swap left's and curr(parent)'s value
int temp = curr.getValue();
curr.setValue(left.getValue());
left.setValue(temp);
}//if(left != null), ends
//if(left == null), no need for swapping
public void doPreOrder()
preOrder(this.root);
private void preOrder(HeapTreeNode curr)
{
if(curr != null)
System.out.print(curr);
preOrder(curr.getLeft());
preOrder(curr.getRight());
public void doInOrder()
inOrder(this.root);
private void inOrder(HeapTreeNode curr)
if(curr != null)
inOrder(curr.getLeft());
System.out.print(curr);
inOrder(curr.getRight());
public void doPostOrder()
postOrder(this.root);
}
private void postOrder(HeapTreeNode curr)
if(curr != null)
postOrder(curr.getLeft());
postOrder(curr.getRight());
System.out.print(curr);
}
//Dipen Patel
//CSC-236
//LAB6-PART B
public class HeapTreeNode {
private int value, pos;
private HeapTreeNode left, right;
public HeapTreeNode()
this(0,0);
public HeapTreeNode(int value)
this(value, 0);
public HeapTreeNode(int value, int pos)
this.value = value;
this.pos = pos;
this.right = null;
this.left = null;
public int getValue()
return value;
}
public void setValue(int value)
this.value = value;
public HeapTreeNode getLeft()
return left;
public void setLeft(HeapTreeNode left)
this.left = left;
public HeapTreeNode getRight()
return right;
public void setRight(HeapTreeNode right)
this.right = right;
public int getPos()
{
return this.pos;
public void setPos(int pos)
this.pos = pos;
public String toString()
return value + " ";
}
//Dipen Patel
//CSC-236
//LAB6-PART B
public class HeapDemo
public static void main(String[] args)
HPTree tree1 = new HPTree();
System.out.println("\t\tADDING 1-10 INTO A HEAP\n"
+ "---------------------------------"
+ "----------------------------");
for (int i = 1; i < 11; i++)
tree1.insert(i);
System.out.print("Inorder traversal: ");
tree1.doInOrder();
System.out.print("\nPostorder traversal: ");
tree1.doPostOrder();
System.out.print("\nPreorder traversal: ");
tree1.doPreOrder();
System.out.println("\n*******************************"
+ "*******************************");
tree1.remove(); tree1.remove(); tree1.remove();
System.out.println("\n\t\tREMOVING 3 ITEMS FROM THE HEAP\n"
+ "---------------------------------"
+ "----------------------------");
System.out.print("Inorder traversal: ");
tree1.doInOrder();
System.out.print("\nPostorder traversal: ");
tree1.doPostOrder();
System.out.print("\nPreorder traversal: ");
tree1.doPreOrder();
System.out.println("\n*******************************"
+ "*******************************");
}
OUTPUT:-
