Sunday, December 5, 2010

Program 12

package program12;


import java.io.*;

public class Main
{

// Program #12
// Zach Krizan
// Data Structures

public static void main(String[] args) throws IOException {
/*********************************************************************
* This program will demonstrate deleting from a tree with 2 children.
* It will insert 7 numbers into the tree.
* Then it will traverse the tree in in-order.
* It will then display the visual of the tree.
* Next it will display a message and delete value 6.
* Then it will traverse the tree and display the tree.
* When it displays the the visual of the tree, it will use a'0' in
* place of the deleted value.
**********************************************************************/

Tree theTree = new Tree(); //tree object


//runs method insert() with numbers 1-7
System.out.println("Inserting...");
theTree.insert(4);
theTree.insert(2);
theTree.insert(6);
theTree.insert(1);
theTree.insert(3);
theTree.insert(5);
theTree.insert(7);
System.out.println("The values inserted are 4,2,6,1,3,5,7");
System.out.println();

System.out.println("Displaying Tree:");
theTree.displayTree(); //runs method displayTree()

System.out.println("Traversing...");
theTree.traverse(); //runs method traverse()



/*************************************
* Deleting Value 6
**************************************/
System.out.println();
System.out.println("+-----------------------------+");
System.out.println("Deleting value '6'...");
System.out.println("+-----------------------------+");
theTree.delete(6); //runs method delete()
System.out.println();
System.out.println("Traversing...");
theTree.traverse(); //runs method traverse()
System.out.println();
System.out.println();
System.out.println("Deleted values will be " +
"replaced by '0'");

System.out.println();
System.out.println("Displaying Tree:");
theTree.displayTree(); //runs method displayTree()


System.out.println("Program will now end");
System.exit(0);


} //end main
} //end Main


/********************************
*
* Same 2 & 3 as 11
*
********************************/
Posted by at No comments:

Program 11

package program11;


import java.io.*;

public class Main
{

// Program #11
// Zach Krizan
// Data Structures

public static void main(String[] args) throws IOException {
/*********************************************************************
* This program will demonstrate deleting from a tree with one child.
* It will insert 7 numbers into the tree.
* Then it will traverse the tree in in-order.
* It will then display the visual of the tree.
* It will display a message and delete value 7.
* Then it will traverse the tree and display the tree.
* Next it will display a message and delete value 6.
* Then it will traverse the tree and display the tree.
* Next it will display a message and delete value 1.
* Then it will traverse the tree and display the tree.
* Next it will display a message and delete value 2.
* Then it will traverse the tree and display the tree.
* When it displays the the visual of the tree, it will use a'0' in
* place of the deleted value.
**********************************************************************/

Tree theTree = new Tree(); //tree object


//runs method insert() with numbers 1-7
System.out.println("Inserting...");
theTree.insert(4);
theTree.insert(2);
theTree.insert(6);
theTree.insert(1);
theTree.insert(3);
theTree.insert(5);
theTree.insert(7);
System.out.println("The values inserted are 4,2,6,1,3,5,7");
System.out.println();

System.out.println("Displaying Tree:");
theTree.displayTree(); //runs method displayTree()

System.out.println("Traversing...");
theTree.traverse(); //runs method traverse()


/*************************************
* Deleting Value 7
**************************************/
System.out.println();
System.out.println();
System.out.println("+-----------------------------+");
System.out.println("Deleting value '7'...");
System.out.println("+-----------------------------+");
theTree.delete(7); //runs method delete()
System.out.println();
System.out.println("Traversing...");
theTree.traverse(); //runs method traverse()
System.out.println();
System.out.println();
System.out.println("Deleted values will be " +
"replaced by '0'");

System.out.println();
System.out.println("Displaying Tree:");
theTree.displayTree(); //runs method displayTree()

/*************************************
* Deleting Value 6
**************************************/
System.out.println();
System.out.println("+-----------------------------+");
System.out.println("Deleting value '6'...");
System.out.println("+-----------------------------+");
theTree.delete(6); //runs method delete()
System.out.println();
System.out.println("Traversing...");
theTree.traverse(); //runs method traverse()
System.out.println();
System.out.println();
System.out.println("Deleted values will be " +
"replaced by '0'");

System.out.println();
System.out.println("Displaying Tree:");
theTree.displayTree(); //runs method displayTree()

/*************************************
* Deleting Value 1
**************************************/
System.out.println();
System.out.println("+-----------------------------+");
System.out.println("Deleting value '1'...");
System.out.println("+-----------------------------+");
theTree.delete(1); //runs method delete()
System.out.println();
System.out.println("Traversing...");
theTree.traverse(); //runs method traverse()
System.out.println();
System.out.println();
System.out.println("Deleted values will be " +
"replaced by '0'");

System.out.println();
System.out.println("Displaying Tree:");
theTree.displayTree(); //runs method displayTree()

/*************************************
* Deleting Value 2
**************************************/
System.out.println();
System.out.println("+-----------------------------+");
System.out.println("Deleting value '2'...");
System.out.println("+-----------------------------+");
theTree.delete(2); //runs method delete()
System.out.println();
System.out.println("Traversing...");
theTree.traverse(); //runs method traverse()
System.out.println();
System.out.println();
System.out.println("Deleted values will be " +
"replaced by '0'");

System.out.println();
System.out.println("Displaying Tree:");
theTree.displayTree(); //runs method displayTree()




System.out.println("Program will now end");
System.exit(0);


} //end main
} //end Main

/********************************
*
* Page 2
*
*********************************/


/*************************
* Node Class
************************/

public class Node
{
public int value; //data used as key value
Node left; //his node's left child
Node right; //this node's right child


//method displayNode
public void displayNode()
{
//This method will print the Node's value
System.out.print('{');
System.out.print(value);
System.out.print('}');
}

}

/********************************
*
* Page 3
*
*********************************/

/*********************
* Tree Class
*********************/
public class Tree
{

private Node root; // the only data field in Tree
int numRuns;

//constructor
public Tree() {
root = null;
numRuns = 0;
}

//method insert
public void insert(int v) {
/**************************************************
* This method will insert a node into the tree.
* It will follow the standard binary tree rule.
* 4, will be the root.
* 2, will be the left child
* 4, will be the right child
* 1, will be the left of the left child
* 3, will be the right of the left child
* 5, will be the left of the right child
* 7, will be the right of the right child
******************************************************/

Node newNode = new Node();
newNode.value = v;
Node current = root;

switch (numRuns)
{
case 0:
root = newNode;
numRuns = 1;
return;
case 1:
current.left = newNode;
numRuns = 2;
return;
case 2:
current.right = newNode;
numRuns = 3;
return;
case 3:
current.left.left = newNode;
numRuns = 4;
return;
case 4:
current.left.right = newNode;
numRuns = 5;
return;
case 5:
current.right.left = newNode;
numRuns = 6;
return;
case 6:
current.right.right = newNode;
numRuns = 7;
return;

default:
System.out.println("Invalid");
break;
}

} // end insert

//method traverse
public void traverse() {

System.out.println();
inOrder(root); //runs method inOrder()
}


//method inOrder
public void inOrder(Node localRoot) {
//This method will traverse the tree and print the nodest in order
//An example of in order (infix):
//If the root is A, the left child is B, and the right child is C
//The infix order would be B,A,C


if (localRoot != null) {
inOrder(localRoot.left);
System.out.print(localRoot.value + " ");
inOrder(localRoot.right);
}

}


//method find
public Node find(int key)
{
//not used in this program but find() is still part of most tree programs

Node current = root; //start a root
while(current.value != key) //while no match
{
if (key < current.value) //go left
current = current.left;
else //go right
current = current.right;
if (current == null) //if no child
return null; //didn't find
} // end while loop
return current; //found it
}



//method delete
public boolean delete(int key)
{
//this method will delete an odd value from the tree

Node current = root;
Node parent = root;
boolean isLeft = true;

while(current.value != key) //search for node
{
parent = current;
if(key < current.value) //go left
{
isLeft=true;
current = current.left;
}
else //go right
{
isLeft = false;
current = current.right;
}
if (current == null) //end of the line
{
return false; //didn't find it
}
}//end while
//found node to delete


//if no children, delete it
if(current.left == null && current.right == null)
{
if (current == root) //if root
{
root = null; //tree is empty
}
else if(isLeft)
{
parent.left = null;
} //disconnect
else //from parent
{
parent.right = null;
}
}

//if no right child, replace with left subtree
else if (current.right == null)
{
if (current == root)
{
root = current.left;
}
else if (isLeft)
{
parent.left = current.left;
}
else
{
parent.right = current.left;
}

}

//if no left child, replace with right subree
else if(current.left == null)
{
if (current == root)
{
root = current.right;
}
else if (isLeft)
{
parent.left = current.right;
}
else
{
parent.right = current.right;
}
}
//two children, so replace with inorder successor
else
{
//get successor of node to delte (current)
Node successor = getSuccessor(current);

//connect parent of current to succesor instead
if (current == root)
{
root = successor;
}
else if (isLeft)
{
parent.left = successor;
}
else
{
parent.right = successor;
}

//connect successor to current's left child
successor.left = current.left;
} //end else with two children

//successor cannot have a left hcild
return true; //success

}//end delete


//method getSuccessor
private Node getSuccessor (Node delNode)
{
//returns node with next-highest value after delNode
//goes to right child, then right child's left descendents

Node successorParent = delNode;
Node successor = delNode;
Node current = delNode.right;
//go to right child until no more left children

while (current != null)
{
successorParent = successor;
successor = current;
current = current.left; //go to left child
}

//if successor not right child, make connection
if (successor != delNode.right)
{
successorParent.left = successor.right;
successor.right = delNode.right;
}
return successor;
}

public void displayTree()
{
//this will display the tree using System.out.print to make a visual
/*
The tree will look like this:
+------------------------------------------+
4
/ \
2 6
/ \ / \
1 3 5 7
+------------------------------------------+*/



//the if statements prevent an error if the value is null as well as
// change the value to 0 if it is null

int t = 0;
if (root != null)
{
t=root.value;
}
int t1 = 0;
if (root.left != null)
{
t1 = root.left.value;
}
int t2 = 0;
if (root.right != null)
{
t2 = root.right.value;
}
int t3 = 0;
if (root.left.left != null)
{
t3 = root.left.left.value;
}
int t4 = 0;
if (root.left.right != null)
{
t4 = root.left.right.value;
}
int t5 = 0;
if (root.right.left != null)
{
t5 = root.right.left.value;
}
int t6 = 0;
if (root.right.right != null)
{
t6 = root.right.right.value;
}


//the visual
System.out.println();
System.out.println("+------------------------------------------+");
System.out.println(" "+t+" ");
System.out.println(" / \\ ");
System.out.println(" "+t1+" "+t2+" ");
System.out.println(" / \\ / \\ ");
System.out.println(" "+t3+" "+t4+" "+t5+" "+t6+" ");
System.out.println("+------------------------------------------+");
System.out.println("");
//you must use \\ because '\' is an escape character
}

}
Posted by at No comments:

Program 6

package program6;


import java.util.Random;

// Zach Krizan
// Program #6
// Data Structures

public class Main
{

public static void main(String a[])
{
/***********************************************************
* This program will demonstrate MergeSort.
* It will generate 10,000 random numbers.
* Then it will run a loop to display the first 100.
* It will then sort the numbers.
* Afterward, another loop will run to display the first 100
* numbers after being sorted.
***********************************************************/


System.out.println("Generating 10000 random numbers...");
//creates array named myNums with 10000 places
int myNums[] = new int[10000];

//creates a random object
Random rand = new Random();

//this loop will create the 10000 random numbers
for(int i=0; i {
myNums[i] = rand.nextInt(100);
}

System.out.println();
System.out.println("The first 100 numbers are: ");

//this loop will display the first 100 numbers
for (int j=0; j<101; j++)
{
System.out.print(myNums[j]+" ");
}

System.out.println();
System.out.println();
System.out.println("Sorting...");
mergeSort_srt(myNums,0, myNums.length-1); //runs mergesort method
System.out.println();
System.out.println("First 100 values after being sorted are:");

//this loop will print the first 100 numbers after being sorted
for(int i = 0; i <101; i++)
{
System.out.print(myNums[i]+" ");
}
}

//method mergeSort
public static void mergeSort_srt(int array[],int lo, int hi)
{
//This method will sort the array
//It will split the array in half to sort it

int low = lo;
int high = hi;

//ir low is greater than or equal to high return
if (low >= high)
{
return;
}

int middle = (low + high) / 2; //finds the middle
mergeSort_srt(array, low, middle); //runs mergeSort method
mergeSort_srt(array, middle + 1, high); //runs mergeSort method

int end_low = middle;
int start_high = middle + 1;

//while low is less than or equal to middle or middle + 1 is less than
// or equal to high
while ((lo <= end_low) && (start_high <= high))
{
if (array[low] < array[start_high])
{
low++;
} else
{
int Temp = array[start_high];
for (int k = start_high- 1; k >= low; k--)
{
array[k+1] = array[k];
}
array[low] = Temp;
low++;
end_low++;
start_high++;
}
}
}
}
Posted by at No comments:

Thursday, December 2, 2010

Program 10

package program10;

import java.io.*;

public class Main {

// Program #10
// Zach Krizan
// Data Structures

public static void main(String[] args) throws IOException {
/*********************************************************************
* This program will demonstrate deleting from a tree.
* It will insert 7 numbers into the tree.
* Then it will traverse the tree in in-order.
* It will then display the visual of the tree.
* Next it will ask the user if they want to enter a value in the tree
* to delete.
* They can either enter 'd' to delete or 'x' to exit the program.
* Once the user enters 'd' they will insert an odd value to delete.
* It will delete the value, then traverse the tree.
* Then it will display the visual of the tree with '0' in place of the
* deleted value.
* This will loop until the user enters 'x'.
**********************************************************************/

int value;
Tree theTree = new Tree(); //tree object


//runs method insert() with numbers 1-7
System.out.println("Inserting...");
theTree.insert(4);
theTree.insert(2);
theTree.insert(6);
theTree.insert(1);
theTree.insert(3);
theTree.insert(5);
theTree.insert(7);
System.out.println("The values inserted are 4,2,6,1,3,5,7");
System.out.println();

System.out.println();
System.out.println("Displaying Tree:");
theTree.displayTree(); //runs method displayTree()

System.out.println();
System.out.println("Traversing...");
theTree.traverse(); //runs method traverse()




//This loop will run until the user enters 'x' to end the program
while (true)
{

//user instructions
System.out.println();
System.out.println();
System.out.print("Enter 'd' to find a value or " +
"'x' to exit the program: ");
int choice = getChar();

switch (choice) //switch statement for d or x
{
case 'd':
//Will ask the user to insert an odd number to delete
System.out.println();
System.out.print("Insert an odd number to delete: ");
value = getInt(); //runs method getInt()
theTree.delete(value); //runs method delete()
System.out.println();
System.out.println("Traversing...");
System.out.println();
theTree.traverse(); //runs method traverse()
System.out.println();
System.out.println();
System.out.println("Deleted values will be " +
"replaced by '0'");
System.out.println("Displaying Tree:");
theTree.displayTree(); //runs method displayTree()
break;
case 'x': //ends program
System.out.println("Program will now end");
System.exit(0);
default: //shows the user they incorrectly inputted
System.out.print("Invalid entry\n");
} //end switch

}//end while
} //end main

//method getString
public static String getString() throws IOException {
//uses IOException on the string
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}

//method getChar
public static char getChar() throws IOException {
//uses IOException on the char
String s = getString();
return s.charAt(0);
}

//method getInt
public static int getInt() throws IOException {
//uses IOException on the int
String s = getString();
return Integer.parseInt(s);
}
} //end Main


/*************************************
*
* Page 2
*
*************************************/




package program10;


/*************************
* Node Class
************************/

public class Node
{
public int value; //data used as key value
Node left; //his node's left child
Node right; //this node's right child


//method displayNode
public void displayNode()
{
//This method will print the Node's value
System.out.print('{');
System.out.print(value);
System.out.print('}');
}

}

/*************************************
*
* Page 3
*
*************************************/



package program10;


/*********************
* Tree Class
*********************/
public class Tree
{

private Node root; // the only data field in Tree
int numRuns;

//constructor
public Tree() {
root = null;
numRuns = 0;
}

//method insert
public void insert(int v) {
/**************************************************
* This method will insert a node into the tree.
* It will follow the standard binary tree rule.
* 4, will be the root.
* 2, will be the left child
* 4, will be the right child
* 1, will be the left of the left child
* 3, will be the right of the left child
* 5, will be the left of the right child
* 7, will be the right of the right child
******************************************************/

Node newNode = new Node();
newNode.value = v;
Node current = root;

switch (numRuns)
{
case 0:
root = newNode;
numRuns = 1;
return;
case 1:
current.left = newNode;
numRuns = 2;
return;
case 2:
current.right = newNode;
numRuns = 3;
return;
case 3:
current.left.left = newNode;
numRuns = 4;
return;
case 4:
current.left.right = newNode;
numRuns = 5;
return;
case 5:
current.right.left = newNode;
numRuns = 6;
return;
case 6:
current.right.right = newNode;
numRuns = 7;
return;

default:
System.out.println("Invalid");
break;
}

} // end insert

//method traverse
public void traverse() {

System.out.println();
inOrder(root); //runs method inOrder()
}


//method inOrder
public void inOrder(Node localRoot) {
//This method will traverse the tree and print the nodest in order
//An example of in order (infix):
//If the root is A, the left child is B, and the right child is C
//The infix order would be B,A,C


if (localRoot != null) {
inOrder(localRoot.left);
System.out.print(localRoot.value + " ");
inOrder(localRoot.right);
}

}


//method find
public Node find(int key)
{
//not used in this program but find() is still part of most tree programs

Node current = root; //start a root
while(current.value != key) //while no match
{
if (key < current.value) //go left
current = current.left;
else //go right
current = current.right;
if (current == null) //if no child
return null; //didn't find
} // end while loop
return current; //found it
}



//method delete
public boolean delete(int key)
{
//this method will delete an odd value from the tree

Node current = root;
Node parent = root;
boolean isLeft = true;

while(current.value != key) //search for node
{
parent = current;
if(key < current.value) //go left
{
isLeft=true;
current = current.left;
}
else //go right
{
isLeft = false;
current = current.right;
}
if (current == null) //end of the line
{
return false; //didn't find it
}
}//end while
//found node to delete


//if no children, delete it
if(current.left == null && current.right == null)
{
if (current == root) //if root
{
root = null; //tree is empty
}
else if(isLeft)
{
parent.left = null;
} //disconnect
else //from parent
{
parent.right = null;
}
}

//if no right child, replace with left subtree
else if (current.right == null)
{
if (current == root)
{
root = current.left;
}
else if (isLeft)
{
parent.left = current.left;
}
else
{
parent.right = current.left;
}

}

//if no left child, replace with right subree
else if(current.left == null)
{
if (current == root)
{
root = current.right;
}
else if (isLeft)
{
parent.left = current.right;
}
else
{
parent.right = current.right;
}
}
//two children, so replace with inorder successor
else
{
//get successor of node to delte (current)
Node successor = getSuccessor(current);

//connect parent of current to succesor instead
if (current == root)
{
root = successor;
}
else if (isLeft)
{
parent.left = successor;
}
else
{
parent.right = successor;
}

//connect successor to current's left child
successor.left = current.left;
} //end else with two children

//successor cannot have a left hcild
return true; //success

}//end delete


//method getSuccessor
private Node getSuccessor (Node delNode)
{
//returns node with next-highest value after delNode
//goes to right child, then right child's left descendents

Node successorParent = delNode;
Node successor = delNode;
Node current = delNode.right;
//go to right child until no more left children

while (current != null)
{
successorParent = successor;
successor = current;
current = current.left; //go to left child
}

//if successor not right child, make connection
if (successor != delNode.right)
{
successorParent.left = successor.right;
successor.right = delNode.right;
}
return successor;
}

public void displayTree()
{
//this will display the tree using System.out.print to make a visual
/*
The tree will look like this:
+------------------------------------------+
4
/ \
2 6
/ \ / \
1 3 5 7
+------------------------------------------+*/



//the if statements prevent an error if the value is null as well as
// change the value to 0 if it is null

int t = 0;
if (root != null)
{
t=root.value;
}
int t1 = 0;
if (root.left != null)
{
t1 = root.left.value;
}
int t2 = 0;
if (root.right != null)
{
t2 = root.right.value;
}
int t3 = 0;
if (root.left.left != null)
{
t3 = root.left.left.value;
}
int t4 = 0;
if (root.left.right != null)
{
t4 = root.left.right.value;
}
int t5 = 0;
if (root.right.left != null)
{
t5 = root.right.left.value;
}
int t6 = 0;
if (root.right.right != null)
{
t6 = root.right.right.value;
}


//the visual
System.out.println();
System.out.println("+------------------------------------------+");
System.out.println(" "+t+" ");
System.out.println(" / \\ ");
System.out.println(" "+t1+" "+t2+" ");
System.out.println(" / \\ / \\ ");
System.out.println(" "+t3+" "+t4+" "+t5+" "+t6+" ");
System.out.println("+------------------------------------------+");
System.out.println("");
//you must use \\ because '\' is an escape character
}

}
Posted by at No comments:

Wednesday, December 1, 2010

Program 7

package program7;

/*********************
* Tree Class
*********************/

public class Tree
{

private Node root; // the only data field in Tree
int numRuns;

//constructor
public Tree()
{
numRuns = 1;
root = null;
}

//method insert
public void insert(int v)
{
/**************************************************
* This method will insert a node into the tree.
* It will not follow the standard binary tree rule due
* to the requirements of the project.
* 1, will be the root.
* 2, will be the left child
* 3, will be the right child
* 4, will be the left of the left child
* 5, will be the right of the left child
* 6, will be the left of the right child
* 7, will be the right of the right child
******************************************************/

Node newNode = new Node();
newNode.value = v;
Node current =root;

switch (numRuns)
{
case 1: root= newNode;
numRuns =2;
return;
case 2: current.left = newNode;
numRuns =3;
return;
case 3: current.right = newNode;
numRuns =4;
return;
case 4: current.left.left = newNode;
numRuns =5;
return;
case 5: current.left.right = newNode;
numRuns =6;
return;
case 6: current.right.left = newNode;
numRuns =7;
return;
case 7: current.right.right = newNode;
numRuns =8;
return;

default: System.out.println("Invalid");break;
}

} // end insert


//method traverse
public void traverse()
{

System.out.println();
preOrder(root);
System.out.println("");
inOrder(root);
System.out.println("");
postOrder(root);
System.out.println("");
}

//method preOrder
public void preOrder (Node localRoot)
{
//this method will traverse the tree and print the nodest in order
//An example of in order (infix):
//If the root is A, the left child is B, and the right child is C
//The infix order would be A,B,C


if(localRoot != null)
{
System.out.print(localRoot.value + " ");
inOrder(localRoot.left);
inOrder(localRoot.right);
}

}

//method inOrder
public void inOrder (Node localRoot)
{
//this method will traverse the tree and print the nodest in order
//An example of in order (infix):
//If the root is A, the left child is B, and the right child is C
//The infix order would be B,A,C


if(localRoot != null)
{
inOrder(localRoot.left);
System.out.print(localRoot.value + " ");
inOrder(localRoot.right);
}

}

//method postOrder
public void postOrder (Node localRoot)
{
//this method will traverse the tree and print the nodest in order
//An example of in order (infix):
//If the root is A, the left child is B, and the right child is C
//The infix order would be B,C,A


if(localRoot != null)
{
inOrder(localRoot.left);
inOrder(localRoot.right);
System.out.print(localRoot.value + " ");
}

}




//method find
public void find(int key)
{
//this method will be implemented for program # 9
}

//method delete
public void delete(int id)
{
//this method will be implemented for program #10
}

}


/***********************************
*
* Page 2
*
************************************/


package program7;


/*************************
* Node Class
************************/

public class Node
{
int value; //data used as key value
Node left; //his node's left child
Node right; //this node's right child


}


/***********************************
*
* Page 3
*
************************************/



package program7;

/*********************
* Tree Class
*********************/

public class Tree
{

private Node root; // the only data field in Tree
int numRuns;

//constructor
public Tree()
{
numRuns = 1;
root = null;
}

//method insert
public void insert(int v)
{
/**************************************************
* This method will insert a node into the tree.
* It will not follow the standard binary tree rule due
* to the requirements of the project.
* 1, will be the root.
* 2, will be the left child
* 3, will be the right child
* 4, will be the left of the left child
* 5, will be the right of the left child
* 6, will be the left of the right child
* 7, will be the right of the right child
******************************************************/

Node newNode = new Node();
newNode.value = v;
Node current =root;

switch (numRuns)
{
case 1: root= newNode;
numRuns =2;
return;
case 2: current.left = newNode;
numRuns =3;
return;
case 3: current.right = newNode;
numRuns =4;
return;
case 4: current.left.left = newNode;
numRuns =5;
return;
case 5: current.left.right = newNode;
numRuns =6;
return;
case 6: current.right.left = newNode;
numRuns =7;
return;
case 7: current.right.right = newNode;
numRuns =8;
return;

default: System.out.println("Invalid");break;
}

} // end insert


//method traverse
public void traverse()
{

System.out.println();
preOrder(root);
System.out.println("");
inOrder(root);
System.out.println("");
postOrder(root);
System.out.println("");
}

//method preOrder
public void preOrder (Node localRoot)
{
//this method will traverse the tree and print the nodest in order
//An example of in order (infix):
//If the root is A, the left child is B, and the right child is C
//The infix order would be A,B,C


if(localRoot != null)
{
System.out.print(localRoot.value + " ");
inOrder(localRoot.left);
inOrder(localRoot.right);
}

}

//method inOrder
public void inOrder (Node localRoot)
{
//this method will traverse the tree and print the nodest in order
//An example of in order (infix):
//If the root is A, the left child is B, and the right child is C
//The infix order would be B,A,C


if(localRoot != null)
{
inOrder(localRoot.left);
System.out.print(localRoot.value + " ");
inOrder(localRoot.right);
}

}

//method postOrder
public void postOrder (Node localRoot)
{
//this method will traverse the tree and print the nodest in order
//An example of in order (infix):
//If the root is A, the left child is B, and the right child is C
//The infix order would be B,C,A


if(localRoot != null)
{
inOrder(localRoot.left);
inOrder(localRoot.right);
System.out.print(localRoot.value + " ");
}

}




//method find
public void find(int key)
{
//this method will be implemented for program # 9
}

//method delete
public void delete(int id)
{
//this method will be implemented for program #10
}

}
Posted by at No comments:

Program 2

/**********************************************
*
* Program 2 - Needs cleaning up
*
*********************************************/

package javaapplication10;

/* Zach Krizan
* Data Structures
* September 20, 2010
*/
public class Main
{

public static void main(String[] args)
{
int A [] = new int[10];
populateA(A); //runs method populatA
System.out.println("Before Sorting:"); //display line
printA(A); // runs method printA

int key;
int i;



for (int j=1; j {
key = A[j];
i = j-1;
while ((i > -1) && (A[i] > key))
{
A[i+1] = A[i];
i = i-1;
}
A[i+1] = key;

}

System.out.println("\n" +"After Sorting"); //displays line
printA(A); //runs method printA again and it will be sorted now
}


public static void printA (int [] B) //creates method printA
{
for (int i=0; i < B.length; i++)
{
System.out.println(B[i]);
}
}

public static int[] populateA (int [] B) //creates method populateA
{
for (int i=0; i < B.length; i++) //for loop will create 10 random #s
{
B[i] = (int)(Math.random()*100); //generates random number
}
return B; //returns int B
}


}
Posted by at No comments:

Program 1

/**************************************************
*
* This program needs some cleaning up
*
***************************************************/

// Zach Krizan
// Data Structures 351-110
// September 08, 2010


package program1;
import java.util.Scanner;

public class Main
{

public static void main(String[] args)
{



String[] month; // reference to array
month = new String[12]; // make array

month[0]="January";
month[1]="February";
month[2]="March";
month[3]="April";
month[4]="May";
month[5]="June";
month[6]="July";
month[7]="August";
month[8]="September";
month[9]="October";
month[10]="November";
month[11]="December";


// create 2nd array
int[] numDays = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int nElms2 = 12; // number of items in 2nd array

int i = 0; //loop counter
System.out.println("Array month is = ");
while (i<12)
{
System.out.println(month[i]); //will display contents of array
i++;
}


int ii= 0; //2nd loop counter
System.out.println("\nArray numDays is = ");
while (ii<12)
{
System.out.println(numDays[ii]); //will display contents of array
ii++;
}

String searchKey; //key of item to search for
int searchKey2; // key of item to search for in 2nd array



Scanner scan = new Scanner (System.in);

int numberMonth; // will be equal to what the user inputs
System.out.println("\nEnter the Number representing the Month: ");
numberMonth = scan.nextInt();



// System.out.println("\nYou entered: ");

//System.out.println(numberMonth + " and " + wordMonth + "\n");


String ifstat= " "; //variable used in the if statement

if (numberMonth == 1) //if the variable entered is equal to 1,
//then print the line January and so on...
{
System.out.println("January");
ifstat = month[0]; //sets up the next if statement
}
else if (numberMonth == 2)
{
System.out.println("February");
ifstat = month[1];
}
else if (numberMonth == 3)
{
System.out.println("March");
ifstat = month[2];
}
else if (numberMonth == 4)
{
System.out.println("April");
ifstat = month[3];
}
else if (numberMonth == 5)
{
System.out.println("May");
ifstat = month[4];
}
else if (numberMonth == 6)
{
System.out.println("June");
ifstat = month[5];
}
else if (numberMonth== 7)
{
System.out.println("July");
ifstat = month[6];
}
else if (numberMonth== 8)
{
System.out.println("August");
ifstat = month[7];
}
else if (numberMonth == 9)
{
System.out.println("September");
ifstat = month[8];
}
else if (numberMonth == 10)
{
System.out.println("October");
ifstat = month[9];
}
else if (numberMonth == 11)
{
System.out.println("November");
ifstat = month[10];
}
else if (numberMonth == 12)
{
System.out.println("December");
ifstat = month[11];
}
else // presents error message if the if statement wasn't
//equal to anythign
{
System.out.println("\nError in the number you entered");
}



if (ifstat == month[0])
// if the variable ifstat is equal the variable month[0] then print
// line so on.
{
System.out.println("has " + numDays[0] + " days");
}
else if (ifstat == month[1])
{
System.out.println("has " + numDays[1] + " days");
}
else if (ifstat == month[2])
{
System.out.println("has " + numDays[2] + " days");
}
else if (ifstat == month[3])
{
System.out.println("has " + numDays[3] + " days");
}
else if (ifstat == month[4])
{
System.out.println("has " + numDays[4] + " days");
}
else if (ifstat == month[5])
{
System.out.println("has " + numDays[5] + " days");
}
else if (ifstat == month[6])
{
System.out.println("has " + numDays[6] + " days");
}
else if (ifstat == month[7])
{
System.out.println("has " + numDays[7] + " days");
}
else if (ifstat == month[8])
{
System.out.println("has " + numDays[8] + " days");
}
else if (ifstat == month[9])
{
System.out.println("has " + numDays[9] + " days");
}
else if (ifstat == month[10])
{
System.out.println("has " + numDays[10] + " days");
}
else if (ifstat == month[11])
{
System.out.println("has " + numDays[11] + " days");
}
else // presents error if if statement is not equal to anything
{
System.out.println("\nTry again");
}





Scanner scan2 = new Scanner (System.in); //2nd scanner

String wordMonth; // will be equal to what the user inputs the 2nd time
System.out.println
("\nEnter the word representing the Month, please spell the full"
+ " word. Make sure the first word is in Upper case. \n");
wordMonth = scan2.nextLine();



String ifstat2 = " "; //used in the 2nd if statement

if (wordMonth.equals(month[0]))
// if wordMonth is equal to month[0] then print line and so on...
{
System.out.println("\nJanuary");
ifstat2 = month[0]; // sets up the next if statement
}
else if (wordMonth.equals(month[1]))
{
System.out.println("\nFebruary");
ifstat2 = month[1];
}
else if (wordMonth.equals(month[2]))
{
System.out.println("\nMarch");
ifstat2 = month[2];
}
else if (wordMonth.equals(month[3]))
{
System.out.println("\nApril");
ifstat2 = month[3];
}
else if (wordMonth.equals(month[4]))
{
System.out.println("\nMay");
ifstat2 = month[4];
}
else if (wordMonth.equals(month[5]))
{
System.out.println("\nJune");
ifstat2 = month[5];
}
else if (wordMonth.equals(month[6]))
{
System.out.println("\nJuly");
ifstat2 = month[6];
}
else if (wordMonth.equals(month[7]))
{
System.out.println("\nAugust");
ifstat2 = month[7];
}
else if (wordMonth.equals(month[8]))
{
System.out.println("\nSeptember");
ifstat2 = month[8];
}
else if (wordMonth.equals(month[9]))
{
System.out.println("\nOctober");
ifstat2 = month[9];
}
else if (wordMonth.equals(month[10]))
{
System.out.println("\nNovember");
ifstat2 = month[10];
}
else if (wordMonth.equals(month[11]))
{
System.out.println("\nDecember");
ifstat2 = month[11];
}
else // presents error message if the if statement doesn't match
{
System.out.println("\nError in word you entered.");
}


if (ifstat2.equals(month[0]))
// if the variable ifstat2 is equal to month[0] print line
{
System.out.println("has " + numDays[0] + " days");
}
else if (ifstat2.equals(month[1]))
{
System.out.println("has " + numDays[1] + " days");
}
else if (ifstat2.equals(month[2]))
{
System.out.println("has " + numDays[2] + " days");
}
else if (ifstat2.equals(month[3]))
{
System.out.println("has " + numDays[3] + " days");
}
else if (ifstat2.equals(month[4]))
{
System.out.println("has " + numDays[4] + " days");
}
else if (ifstat2.equals(month[5]))
{
System.out.println("has " + numDays[5] + " days");
}
else if (ifstat2.equals(month[6]))
{
System.out.println("has " + numDays[6] + " days");
}
else if (ifstat2.equals(month[7]))
{
System.out.println("has " + numDays[7] + " days");
}
else if (ifstat2.equals(month[8]))
{
System.out.println("has " + numDays[8] + " days");
}
else if (ifstat2.equals(month[9]))
{
System.out.println("has " + numDays[9] + " days");
}
else if (ifstat2.equals(month[10]))
{
System.out.println("has " + numDays[10] + " days");
}
else if (ifstat2.equals(month[11]))
{
System.out.println("has " + numDays[11] + " days");
}
else // presents error message
{
System.out.println("\nTry again");
}
}
}
Posted by at No comments:

Program 9

package program9;

import java.io.*;

public class Main {

// Program #9
// Zach Krizan
// Data Structures

public static void main(String[] args) throws IOException {
/*********************************************************************
* This program will demonstrate searching a tree.
* It will insert 7 numbers into the tree.
* Then it will traverse the tree in in-order.
* Next it will ask the user if they want to find a value in the tree.
* They can either enter 'f' to find a value or 'x' to exit the program.
* The user will enter a value to search for.
* The results will be either: "Found {value}" or "Could not Find value".
* This will loop until the user enters 'x'.
**********************************************************************/
int value;
Tree theTree = new Tree(); //tree object


System.out.println("Inserting...");
theTree.insert(4);
theTree.insert(2);
theTree.insert(6);
theTree.insert(1);
theTree.insert(3);
theTree.insert(5);
theTree.insert(7);
System.out.println("The values inserted are 4,2,6,1,3,5,7");

System.out.println();
System.out.println("Traversing...");
theTree.traverse();




//This loop will run until the user enters 'x' to end the program
while (true) {

//user instructions
System.out.println();
System.out.print("Enter 'f' to find a value or " +
"'x' to exit the program: ");
int choice = getChar();
switch (choice) //switch statement for i or x
{
case 'f':
System.out.println();
System.out.print("Insert a value to search for: ");
value = getInt();
Node found = theTree.find(value);
if(found != null)
{
System.out.print("Found: ");
found.displayNode();
System.out.print("\n");
}
else
System.out.println("Could not find: " + value );
System.out.println();
break;
case 'x': //ends program
System.out.println("Program will now end");
System.exit(0);
default: //shows the user they incorrectly inputted
System.out.print("Invalid entry\n");
} //end switch

}//end while
} //end main

//method getString
public static String getString() throws IOException {
//uses IOException on the string
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}

//method getChar
public static char getChar() throws IOException {
//uses IOException on the char
String s = getString();
return s.charAt(0);
}

//method getInt
public static int getInt() throws IOException {
//uses IOException on the int
String s = getString();
return Integer.parseInt(s);
}
} //end Main




/***************************************
*
* Page 2
*
***************************************/

package program9;

/*************************
* Node Class
************************/

public class Node
{
public int value; //data used as key value
Node left; //his node's left child
Node right; //this node's right child


//method displayNode
public void displayNode()
{
//This method will print the Node's value
System.out.print('{');
System.out.print(value);
System.out.print('}');
}

}


/***************************************
*
* Page 3
*
***************************************/



package program9;

/*********************
* Tree Class
*********************/
public class Tree {

private Node root; // the only data field in Tree

//constructor
public Tree() {
root = null;
}

//method insert
public void insert(int v) {
/**************************************************
* This method will insert a node into the tree.
* It will follow the standard binary tree rule.
******************************************************/

Node newNode = new Node(); //make new node
newNode.value = v; //insert data
if (root == null) //no node in root
{
root = newNode;
} else {
Node current = root; //start at root
Node parent;
while (true) //exists internally
{
parent = current;
if (v < current.value) //go left
{
current = current.left;
if (current == null) //if end of the line
{
parent.left = newNode;
return;
}
} //end if go left
else {
current = current.right;
if (current == null) //if end of the line
{
parent.right = newNode;
return;
}
} //end else go right
} // end while
} //end else not root
} // end insert

//method traverse
public void traverse() {

System.out.println();
inOrder(root);
}

//method inOrder
public void inOrder(Node localRoot) {
//This method will traverse the tree and print the nodest in order
//An example of in order (infix):
//If the root is A, the left child is B, and the right child is C
//The infix order would be B,A,C


if (localRoot != null) {
inOrder(localRoot.left);
System.out.print(localRoot.value + " ");
inOrder(localRoot.right);
}

}

//method find
public Node find(int key)
{
//
Node current = root; //start a root
while(current.value != key) //while no match
{
if (key < current.value) //go left
current = current.left;
else //go right
current = current.right;
if (current == null) //if no child
return null; //didn't find
} // end while loop
return current; //found it
}



//method delete
public void delete(int id) {
//this method will be implemented for program #10
}
}
Posted by at No comments:

Program 8

package program8;

import java.io.*;

public class Main
{

// Program #8
// Zach Krizan
// Data Structures

public static void main(String[] args) throws IOException
{
/*********************************************************************
* This program will demonstrate a tree using Dynamic Memory.
* It will display text asking the user to enter either 'i' or 'x'.
* 'i' will be to insert a value, and 'x' will be to end the program
* Once you insert a value, it will be added to the tree, then it will
* traverse the tree in in-order.
**********************************************************************/

int value;
Tree theTree = new Tree(); //tree object


//This loop will run until the user enters 'x' to end the program
while(true)
{

//user instructions
System.out.println();
System.out.print("Type 'i' to insert or 'x' to exit: ");
int choice = getChar();
switch(choice) //switch statement for i or x
{
case 'i': //inserts the value, then traverses
System.out.println();
System.out.print("Enter value to insert: ");
value = getInt();
theTree.insert(value);
System.out.println();
System.out.println("Traversing...");
theTree.traverse();
System.out.println();
break;
case 'x': //ends program
System.out.println("Program will now end");
System.exit(0);
default: //shows the user they incorrectly inputted
System.out.print("Invalid entry\n");
} //end switch

}//end while
} //end main



//method getString
public static String getString() throws IOException
{
//uses IOException on the string
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}

//method getChar
public static char getChar() throws IOException
{
//uses IOException on the char
String s = getString();
return s.charAt(0);
}

//method getInt
public static int getInt() throws IOException
{
//uses IOException on the int
String s = getString();
return Integer.parseInt(s);
}

} //end Main





/***************************************************
*
*
* Page 2
*
***************************************************/


package program8;

/*************************
* Node Class
************************/

public class Node
{
int value; //data used as key value
Node left; //his node's left child
Node right; //this node's right child


}

/***************************************************
*
*
* Page 3
*
***************************************************/

package program8;

/*********************
* Tree Class
*********************/

public class Tree
{

private Node root; // the only data field in Tree

//constructor
public Tree()
{
root = null;
}

//method insert
public void insert(int v)
{
/**************************************************
* This method will insert a node into the tree.
* It will follow the standard binary tree rule.
******************************************************/

Node newNode = new Node(); //make new node
newNode.value = v; //insert data
if (root==null) //no node in root
root = newNode;
else
{
Node current = root; //start at root
Node parent;
while(true) //exists internally
{
parent = current;
if (v < current.value) //go left
{
current = current.left;
if (current == null) //if end of the line
{
parent.left = newNode;
return;
}
} //end if go left
else
{
current = current.right;
if (current == null) //if end of the line
{
parent.right = newNode;
return;
}
} //end else go right
} // end while
} //end else not root
} // end insert


//method traverse
public void traverse()
{

System.out.println();
inOrder(root);
}


//method inOrder
public void inOrder (Node localRoot)
{
//this method will traverse the tree and print the nodest in order
//An example of in order (infix):
//If the root is A, the left child is B, and the right child is C
//The infix order would be B,A,C


if(localRoot != null)
{
inOrder(localRoot.left);
System.out.print(localRoot.value + " ");
inOrder(localRoot.right);
}

}


//method find
public void find(int key)
{
//this method will be implemented for program # 9
}

//method delete
public void delete(int id)
{
//this method will be implemented for program #10
}

}
Posted by at No comments:

Wednesday, November 17, 2010

Project 5

package project5;

import java.util.Scanner;
import java.util.*;
import java.io.*;
import java.awt.Component;
import javax.swing.JOptionPane;

// Zach Krizan
// Java Program 5
public class Main {

/**********************************************************
* The purpose of a dummy node is to prevent errors when you
* might have an empty list, or when you get an error trying to
* do something at the beginning of the list.
* This program will ask the user for a number, and enter
* it into a list. The user will keep getting an option to
* add to the list until the user chooses to stop.
* Then the user will be asked to choose a number thats on
* the list. If they choose an incorrect number, their will
* be an error checker. If they choose correctly, the will
* be asked if they want to delete the number.
* Then the final list will be displayed.
**********************************************************/
static void printList(ListNode start) {
// Prints the items in the list to which start points.
// They are printed on one line, separated by spaces.

ListNode runner; // For running along the list.
runner = start;
String tempList = "";
// This while loop runs through the entire list.
while (runner != null) {
JOptionPane.showMessageDialog(null, " " + runner.item);
runner = runner.next;
}

} // end printList()

//method numCheck
static boolean numCheck(ListNode start2, String checker) {


// This method checks to see if the number is on the list or not.
// If it is not on the list the boolean errorCheck will be false.
// If it is on the list the boolean errorCheck will be true.

ListNode runner2 = new ListNode(); // A new node to add to the list.
runner2 = start2;

boolean errorCheck = false;

// This while loop will run through the entire list.
while (runner2 != null) {
if (runner2.item.equals(checker)) {
errorCheck = true;
}
runner2 = runner2.next;
}
return errorCheck;

}

//method setNum
static String setNum(String methodNum) {


// This method will ask the number they want to search the list for.
// Then it will set that number equal to tempNum, and return tempNum.
methodNum = JOptionPane.showInputDialog("Enter a number to search"
+ " the list for: ");
//search for the number
String tempNum = methodNum;
return tempNum;
}

//deleteNum
static void deleteNum(ListNode start3, String theNum) {

// This method will only be used if a number on the list is deleted.
// It will print the new list without the deleted number.
// Prints the items in the list to which start points.
// They are printed on one line, separated by spaces.

ListNode runner3 = new ListNode(); // For running along the list.
runner3 = start3;

// This while loop will run through the entire list.
while (runner3 != null) {
if (runner3.next != null) {
if (runner3.next.item.equals(theNum)) //Whenever the number in the list is found use this if statement
{
removeAfter(runner3);
}
}

if (runner3.item.equals(theNum)) {
removeBeg(runner3);
}

JOptionPane.showMessageDialog(null, " " + runner3.item);
// prints list.
runner3 = runner3.next;
}
System.out.println();
}

//method removeAfter()
static void removeAfter(ListNode temp) {
//This will delete list.next

ListNode obsoleteNode;
obsoleteNode = temp.next;
temp.next = temp.next.next;
obsoleteNode = null;

//list.next turns into list.next.next
}

//method removeBeg
static void removeBeg(ListNode l) { // remove first node
ListNode obsoleteNode2;
obsoleteNode2 = l;
obsoleteNode2.item = l.item;
l.item = l.next.item; // point past deleted node
obsoleteNode2 = null;
//This will make the beginning node = to the second node


ListNode obsoleteNode3;
obsoleteNode3 = l.next;
l.next = l.next.next;
obsoleteNode3 = null;
//runs same code to take out second node
}

/****************************************
*
* Main Method
*
****************************************/
public static void main(String[] args) {


JOptionPane.showMessageDialog(null, "You are now running Program 5");

ListNode list = null; // A list, initially empty.

int counter = 0; // counts how long the list is.
String num = "";
String str = "yes";

//This is to create the dummy node
ListNode dummy = new ListNode();
dummy.item = "Dummy Node";
list = dummy;


JOptionPane.showMessageDialog(null, "Dummy Node Created");


while (str.equals("yes")) {
// This while loop will go as long as the user wants to keep
// entering numbers in the list.

num = JOptionPane.showInputDialog("Enter a number to put "
+ "on the list: ");

ListNode head = new ListNode(); // A new node to add to the list.
head.item = num; // Makes the head.item = to the number the
// user entered

//the dummy nodes are head and tail
//tail
//while (temp.getNext() != tail) - instaed of notnull
//

head.next = list;
list = head;



String a = JOptionPane.showInputDialog("Would you"
+ "like to enter another number?"
+ "\nPlease enter 'yes' or 'no'");
str = a;
counter++;



if (str.equals("no")) {
JOptionPane.showMessageDialog(null, "Your final list is: ");
printList(list);
}
}



String part2num = "";

part2num = setNum(part2num);
// set Num will use a scanner to make part2num
// equal to whatever the user enters.


numCheck(list, part2num);
boolean EC; //made to error check
EC = numCheck(list, part2num);
//numCheck will check for the number

//This loop will give an error message if EC is false and have the
// user enter another number
while (EC == false) {
JOptionPane.showMessageDialog(null, "Error: the number you entered "
+ "is not in the list");

String again;
again = JOptionPane.showInputDialog("Would you like to enter another"
+ " number?");
if (again.equals("no")) // This if statement will run if the user choose "no" and
// did not want to continue
{
JOptionPane.showMessageDialog(null, "The final list is: ");
printList(list);
JOptionPane.showMessageDialog(null, "Program will now end");

System.exit(0);
}

part2num = setNum(part2num); //sets the number for the second part
numCheck(list, part2num); //checks the number to see if it exists
EC = numCheck(list, part2num); //makes EC equal to true or false
}
JOptionPane.showMessageDialog(null, "Found Number");
String wishDelete = "";

wishDelete = JOptionPane.showInputDialog("Do you wish to Delete it?"
+ "\nPlease enter 'yes' or 'no'");


if (wishDelete.equals("yes")) {
JOptionPane.showMessageDialog(null, "Deleting");



JOptionPane.showMessageDialog(null, "The final list is:");
deleteNum(list, part2num); //print list with deleted number
JOptionPane.showMessageDialog(null, "The program is now finished");
}
if (wishDelete.equals("no")) //This if statement will be user if the user did not want to
// delete the chosen number
{
JOptionPane.showMessageDialog(null, "The entry will not be "
+ "deleted");

JOptionPane.showMessageDialog(null, "The final list is:");
printList(list);

}

}
}



///////////////////////////////////////////////////////////
*
*
*Page2
*
*
*/////////////////////////////////////////////////////////



package project5;


public class ListNode
{
String item; // An item in the list.
ListNode next; // Pointer to the next node in the list.
}
Posted by at No comments:
Subscribe to: Posts (Atom)