package treeapp0; /* * To change this license header, choose License Headers in
ID: 3806705 • Letter: P
Question
package treeapp0;
/*
* 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.
*/
import java.io.*;
import java.util.*; // for Stack class
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
class Tree
{
public static void main(String[] args) throws IOException
{
int value;
Tree theTree = new Tree();
theTree.insert(50, 1.5);
theTree.insert(25, 1.2);
theTree.insert(75, 1.7);
theTree.insert(12, 1.5);
theTree.insert(37, 1.2);
theTree.insert(43, 1.7);
theTree.insert(30, 1.5);
theTree.insert(33, 1.2);
theTree.insert(87, 1.7);
theTree.insert(93, 1.5);
theTree.insert(97, 1.5);
while(true)
{
System.out.print("Enter first letter of show, ");
System.out.print("insert, find, delete, or traverse: ");
int choice = getChar();
switch(choice)
{
case 's':
theTree.displayTree();
break;
case 'i':
System.out.print("Enter value to insert: ");
value = getInt();
theTree.insert(value, value + 0.9);
break;
case 'f':
System.out.print("Enter value to find: ");
value = getInt();
Node found = theTree.find(value);
if(found != null)
{
System.out.print("Found: ");
found.displayNode();
System.out.print(" ");
}
else
System.out.print("Could not find ");
System.out.print(value + ' ');
break;
case 'd':
System.out.print("Enter value to delete: ");
value = getInt();
boolean didDelete = theTree.delete(value);
if(didDelete)
System.out.print("Deleted " + value + ' ');
else
System.out.print("Could not delete ");
System.out.print(value + ' ');
break;
case 't':
System.out.print("Enter type 1, 2 or 3: ");
value = getInt();
theTree.traverse(value);
break;
default:
System.out.print("Invalid entry ");
} // end switch
} // end while
} // end main()
// -------------------------------------------------------------
public static String getString() throws IOException
{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
// -------------------------------------------------------------
public static char getChar() throws IOException
{
String s = getString();
return s.charAt(0);
}
//-------------------------------------------------------------
public static int getInt() throws IOException
{
String s = getString();
return Integer.parseInt(s);
}
private Node root; // first node of tree
// -------------------------------------------------------------
public Tree() // constructor
{ root = null; } // no nodes in tree yet
// -------------------------------------------------------------
public Node find(int key) // find node with given key
{ // (assumes non-empty tree)
Node current = root; // start at root
while(current.iData != key) // while no match,
{
if(key < current.iData) // go left?
current = current.leftChild;
else // or go right?
current = current.rightChild;
if(current == null) // if no child,
return null; // didn't find it
}
return current; // found it
} // end find()
// -------------------------------------------------------------
public void insert(int id, double dd)
{
Node newNode = new Node(); // make new node
newNode.iData = id; // insert data
newNode.dData = dd;
if(root==null) // no node in root
root = newNode;
else // root occupied
{
Node current = root; // start at root
Node parent;
while(true) // (exits internally)
{
parent = current;
if(id < current.iData) // go left?
{
current = current.leftChild;
if(current == null) // if end of the line,
{ // insert on left
parent.leftChild = newNode;
return;
}
} // end if go left
else // or go right?
{
current = current.rightChild;
if(current == null) // if end of the line
{ // insert on right
parent.rightChild = newNode;
return;
}
} // end else go right
} // end while
} // end else not root
} // end insert()
// -------------------------------------------------------------
public boolean delete(int key) // delete node with given key
{ // (assumes non-empty list)
Node current = root;
Node parent = root;
boolean isLeftChild = true;
while(current.iData != key) // search for node
{
parent = current;
if(key < current.iData) // go left?
{
isLeftChild = true;
current = current.leftChild;
}
else // or go right?
{
isLeftChild = false;
current = current.rightChild;
}
if(current == null) // end of the line,
return false; // didn't find it
} // end while
// found node to delete
// if no children, simply delete it
if(current.leftChild==null &&
current.rightChild==null)
{
if(current == root) // if root,
root = null; // tree is empty
else if(isLeftChild)
parent.leftChild = null; // disconnect
else // from parent
parent.rightChild = null;
}
// if no right child, replace with left subtree
else if(current.rightChild==null)
if(current == root)
root = current.leftChild;
else if(isLeftChild)
parent.leftChild = current.leftChild;
else
parent.rightChild = current.leftChild;
// if no left child, replace with right subtree
else if(current.leftChild==null)
if(current == root)
root = current.rightChild;
else if(isLeftChild)
parent.leftChild = current.rightChild;
else
parent.rightChild = current.rightChild;
else // two children, so replace with inorder successor
{
// get successor of node to delete (current)
Node successor = getSuccessor(current);
// connect parent of current to successor instead
if(current == root)
root = successor;
else if(isLeftChild)
parent.leftChild = successor;
else
parent.rightChild = successor;
// connect successor to current's left child
successor.leftChild = current.leftChild;
} // end else two children
// (successor cannot have a left child)
return true; // success
} // end delete()
// -------------------------------------------------------------
// returns node with next-highest value after delNode
// goes to right child, then right child's left descendents
private Node getSuccessor(Node delNode)
{
Node successorParent = delNode;
Node successor = delNode;
Node current = delNode.rightChild; // go to right child
while(current != null) // until no more
{ // left children,
successorParent = successor;
successor = current;
current = current.leftChild; // go to left child
}
// if successor not
if(successor != delNode.rightChild) // right child,
{ // make connections
successorParent.leftChild = successor.rightChild;
successor.rightChild = delNode.rightChild;
}
return successor;
}
// -------------------------------------------------------------
public void traverse(int traverseType)
{
switch(traverseType)
{
case 1: System.out.print(" Preorder traversal: ");
preOrder(root);
break;
case 2: System.out.print(" Inorder traversal: ");
inOrder(root);
break;
case 3: System.out.print(" Postorder traversal: ");
postOrder(root);
break;
}
System.out.println();
}
// -------------------------------------------------------------
private void preOrder(Node localRoot)
{
if(localRoot != null)
{
System.out.print(localRoot.iData + " ");
preOrder(localRoot.leftChild);
preOrder(localRoot.rightChild);
}
}
// -------------------------------------------------------------
private void inOrder(Node localRoot)
{
if(localRoot != null)
{
inOrder(localRoot.leftChild);
System.out.print(localRoot.iData + " ");
inOrder(localRoot.rightChild);
}
}
// -------------------------------------------------------------
private void postOrder(Node localRoot)
{
if(localRoot != null)
{
postOrder(localRoot.leftChild);
postOrder(localRoot.rightChild);
System.out.print(localRoot.iData + " ");
}
}
// -------------------------------------------------------------
public void displayTree()
{
Stack globalStack = new Stack();
globalStack.push(root);
int nBlanks = 32;
boolean isRowEmpty = false;
System.out.println(
"......................................................");
while(isRowEmpty==false)
{
Stack localStack = new Stack();
isRowEmpty = true;
for(int j=0; j<nBlanks; j++)
System.out.print(' ');
while(globalStack.isEmpty()==false)
{
Node temp = (Node)globalStack.pop();
if(temp != null)
{
System.out.print(temp.iData);
localStack.push(temp.leftChild);
localStack.push(temp.rightChild);
if(temp.leftChild != null ||
temp.rightChild != null)
isRowEmpty = false;
}
else
{
System.out.print("--");
localStack.push(null);
localStack.push(null);
}
for(int j=0; j<nBlanks*2-2; j++)
System.out.print(' ');
} // end while globalStack not empty
System.out.println();
nBlanks /= 2;
while(localStack.isEmpty()==false)
globalStack.push( localStack.pop() );
} // end while isRowEmpty is false
System.out.println(
"......................................................");
} // end displayTree()
class Node
{
public int iData; // data item (key)
public double dData; // data item
public Node leftChild; // this node's left child
public Node rightChild; // this node's right child
public void displayNode() // display ourself
{
System.out.print('{');
System.out.print(iData);
System.out.print(", ");
System.out.print(dData);
System.out.print("} ");
}
} // end class Node
// -------------------------------------------------------------
} // end class Tree
Using Standard Java code for Data Structures. Add the following methods to TreeApp:
1. int size()
2. int depth(int key)
3. void removeLeaves()
4. int rightMinValue()
5. int leftMaxValue()
6. int maximum()
7. int minimum()
Add to menu options for user to select size(), depth(int key), removeLeaves(), rigtMinValue(), leftMaxValue(), maximum() and minimum().
Explanation / Answer
package treenode;
/*
* 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.
*/
import java.io.*;
import java.util.*; // for Stack class
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
public class Tree {
public static void main(String[] args) throws IOException {
int value;
Tree theTree = new Tree();
theTree.insert(50, 1.5);
theTree.insert(25, 1.2);
theTree.insert(75, 1.7);
theTree.insert(12, 1.5);
theTree.insert(37, 1.2);
theTree.insert(43, 1.7);
theTree.insert(30, 1.5);
theTree.insert(33, 1.2);
theTree.insert(87, 1.7);
theTree.insert(93, 1.5);
theTree.insert(97, 1.5);
while (true) {
System.out.println("Please enter:");
System.out.println("1. Show");
System.out.println("2. Insert");
System.out.println("3. Find");
System.out.println("4. Delete");
System.out.println("5. Traverse");
System.out.println("6. Size");
System.out.println("7. Depth");
System.out.println("8. RemoveLeaves");
System.out.println("9. RightMinValue");
System.out.println("10. LeftMaxValue");
System.out.println("11. Maximum");
System.out.println("12. Minimum");
int choice = getInt();
switch (choice) {
case 1:
theTree.displayTree();
break;
case 2:
System.out.print("Enter value to insert: ");
value = getInt();
theTree.insert(value, value + 0.9);
break;
case 3:
System.out.print("Enter value to find: ");
value = getInt();
Node found = theTree.find(value);
if (found != null) {
System.out.print("Found: ");
found.displayNode();
System.out.print(" ");
} else
System.out.print("Could not find ");
System.out.print(value + ' ');
break;
case 4:
System.out.print("Enter value to delete: ");
value = getInt();
boolean didDelete = theTree.delete(value);
if (didDelete)
System.out.print("Deleted " + value + ' ');
else
System.out.print("Could not delete ");
System.out.print(value + ' ');
break;
case 5:
System.out.print("Enter type 1, 2 or 3: ");
value = getInt();
theTree.traverse(value);
break;
case 6:
System.out.println("Size of the tree is: " + theTree.getSize());
break;
case 7:
System.out.println("Depth of the tree is: " + theTree.depth2(theTree.root));
break;
case 8:
System.out.println("Removing Leaf node of the tree: ");
theTree.root = theTree.removeLeafNode(theTree.root);
System.out.println("Removed leafs");
break;
case 9:
System.out.println("Right Min Value of the tree: "+ theTree.rightMinValue());
break;
case 10:
System.out.println("Left Max Value of the tree: "+ theTree.leftMaxValue());
break;
case 11:
System.out.println("Maximum Value of the tree: "+ theTree.maxValue());
break;
case 12:
System.out.println("Minimum Value of the tree: "+ theTree.minValue());
break;
default:
System.out.print("Invalid entry ");
} // end switch
} // end while
} // end main()
// -------------------------------------------------------------
public static String getString() throws IOException {
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
// -------------------------------------------------------------
public static char getChar() throws IOException {
String s = getString();
return s.charAt(0);
}
// -------------------------------------------------------------
public static int getInt() throws IOException {
String s = getString();
return Integer.parseInt(s);
}
private Node root; // first node of tree
private int size;
// -------------------------------------------------------------
public Tree() // constructor
{
root = null;
size = 0;
} // no nodes in tree yet
// -------------------------------------------------------------
public int getSize() {
return this.size;
}
public int depth2(Node node) {
if (node == null)
return 0;
int left = depth2(node.leftChild);
int right = depth2(node.rightChild);
int x = left > right ? left + 1 : right + 1;
return x;
}
public Node removeLeafNode(Node root) {
if (root == null)
return null;
else {
if (root.leftChild == null && root.rightChild == null) { // if both
// left
// and
// right
// child
// are
// null
root = null; // delete it (by assigning null)
} else {
root.leftChild = removeLeafNode(root.leftChild); // set new left
// node
root.rightChild = removeLeafNode(root.rightChild); // set new
// right
// node
}
return root;
}
}
public int rightMinValue() {
if (root.rightChild != null){
return rightMinValue(root.rightChild);
}
return root.iData;
}
/* Function to return least value recursively */
private int rightMinValue(Node r) {
if (r.leftChild == null)
return r.iData;
return rightMinValue(r.leftChild);
}
public int leftMaxValue() {
if (root.leftChild != null){
return leftMaxValue(root.leftChild);
}
return root.iData;
}
/* Function to return least value recursively */
private int leftMaxValue(Node r) {
if (r.rightChild == null)
return r.iData;
return leftMaxValue(r.rightChild);
}
public int minValue() {
return minValue(root);
}
/* Function to return least value recursively */
private int minValue(Node r) {
if (r.leftChild == null)
return r.iData;
return rightMinValue(r.leftChild);
}
public int maxValue() {
return maxValue(root);
}
/* Function to return least value recursively */
private int maxValue(Node r) {
if (r.rightChild == null)
return r.iData;
//System.out.println(r.iData+" ");
return maxValue(r.rightChild);
}
public Node find(int key) // find node with given key
{ // (assumes non-empty tree)
Node current = root; // start at root
while (current.iData != key) // while no match,
{
if (key < current.iData) // go left?
current = current.leftChild;
else // or go right?
current = current.rightChild;
if (current == null) // if no child,
return null; // didn't find it
}
return current; // found it
} // end find()
// -------------------------------------------------------------
public void insert(int id, double dd) {
Node newNode = new Node(); // make new node
newNode.iData = id; // insert data
newNode.dData = dd;
size++;
if (root == null) // no node in root
root = newNode;
else // root occupied
{
Node current = root; // start at root
Node parent;
while (true) // (exits internally)
{
parent = current;
if (id < current.iData) // go left?
{
current = current.leftChild;
if (current == null) // if end of the line,
{ // insert on left
parent.leftChild = newNode;
return;
}
} // end if go left
else // or go right?
{
current = current.rightChild;
if (current == null) // if end of the line
{ // insert on right
parent.rightChild = newNode;
return;
}
} // end else go right
} // end while
} // end else not root
} // end insert()
// -------------------------------------------------------------
public boolean delete(int key) // delete node with given key
{ // (assumes non-empty list)
Node current = root;
Node parent = root;
boolean isLeftChild = true;
while (current.iData != key) // search for node
{
parent = current;
if (key < current.iData) // go left?
{
isLeftChild = true;
current = current.leftChild;
} else // or go right?
{
isLeftChild = false;
current = current.rightChild;
}
if (current == null) // end of the line,
return false; // didn't find it
} // end while
// found node to delete
// if no children, simply delete it
if (current.leftChild == null && current.rightChild == null) {
if (current == root) // if root,
root = null; // tree is empty
else if (isLeftChild)
parent.leftChild = null; // disconnect
else // from parent
parent.rightChild = null;
}
// if no right child, replace with left subtree
else if (current.rightChild == null)
if (current == root)
root = current.leftChild;
else if (isLeftChild)
parent.leftChild = current.leftChild;
else
parent.rightChild = current.leftChild;
// if no left child, replace with right subtree
else if (current.leftChild == null)
if (current == root)
root = current.rightChild;
else if (isLeftChild)
parent.leftChild = current.rightChild;
else
parent.rightChild = current.rightChild;
else // two children, so replace with inorder successor
{
// get successor of node to delete (current)
Node successor = getSuccessor(current);
// connect parent of current to successor instead
if (current == root)
root = successor;
else if (isLeftChild)
parent.leftChild = successor;
else
parent.rightChild = successor;
// connect successor to current's left child
successor.leftChild = current.leftChild;
} // end else two children
// (successor cannot have a left child)
return true; // success
} // end delete()
// -------------------------------------------------------------
// returns node with next-highest value after delNode
// goes to right child, then right child's left descendents
private Node getSuccessor(Node delNode) {
Node successorParent = delNode;
Node successor = delNode;
Node current = delNode.rightChild; // go to right child
while (current != null) // until no more
{ // left children,
successorParent = successor;
successor = current;
current = current.leftChild; // go to left child
}
// if successor not
if (successor != delNode.rightChild) // right child,
{ // make connections
successorParent.leftChild = successor.rightChild;
successor.rightChild = delNode.rightChild;
}
return successor;
}
// -------------------------------------------------------------
public void traverse(int traverseType) {
switch (traverseType) {
case 1:
System.out.print(" Preorder traversal: ");
preOrder(root);
break;
case 2:
System.out.print(" Inorder traversal: ");
inOrder(root);
break;
case 3:
System.out.print(" Postorder traversal: ");
postOrder(root);
break;
}
System.out.println();
}
// -------------------------------------------------------------
private void preOrder(Node localRoot) {
if (localRoot != null) {
System.out.print(localRoot.iData + " ");
preOrder(localRoot.leftChild);
preOrder(localRoot.rightChild);
}
}
// -------------------------------------------------------------
private void inOrder(Node localRoot) {
if (localRoot != null) {
inOrder(localRoot.leftChild);
System.out.print(localRoot.iData + " ");
inOrder(localRoot.rightChild);
}
}
// -------------------------------------------------------------
private void postOrder(Node localRoot) {
if (localRoot != null) {
postOrder(localRoot.leftChild);
postOrder(localRoot.rightChild);
System.out.print(localRoot.iData + " ");
}
}
// -------------------------------------------------------------
public void displayTree() {
Stack globalStack = new Stack();
globalStack.push(root);
int nBlanks = 32;
boolean isRowEmpty = false;
System.out.println("......................................................");
while (isRowEmpty == false) {
Stack localStack = new Stack();
isRowEmpty = true;
for (int j = 0; j < nBlanks; j++)
System.out.print(' ');
while (globalStack.isEmpty() == false) {
Node temp = (Node) globalStack.pop();
if (temp != null) {
System.out.print(temp.iData);
localStack.push(temp.leftChild);
localStack.push(temp.rightChild);
if (temp.leftChild != null || temp.rightChild != null)
isRowEmpty = false;
} else {
System.out.print("--");
localStack.push(null);
localStack.push(null);
}
for (int j = 0; j < nBlanks * 2 - 2; j++)
System.out.print(' ');
} // end while globalStack not empty
System.out.println();
nBlanks /= 2;
while (localStack.isEmpty() == false)
globalStack.push(localStack.pop());
} // end while isRowEmpty is false
System.out.println("......................................................");
} // end displayTree()
class Node {
public int iData; // data item (key)
public double dData; // data item
public Node leftChild; // this node's left child
public Node rightChild; // this node's right child
public void displayNode() // display ourself
{
System.out.print('{');
System.out.print(iData);
System.out.print(", ");
System.out.print(dData);
System.out.print("} ");
}
} // end class Node
// -------------------------------------------------------------
} // end class Tree
Ouput:
Please enter:
1. Show
2. Insert
3. Find
4. Delete
5. Traverse
6. Size
7. Depth
8. RemoveLeaves
9. RightMinValue
10. LeftMaxValue
11. Maximum
12. Minimum
1
......................................................
50
25 75
12 37 -- 87
-- -- 30 43 -- -- -- 93
-- -- -- -- -- 33 -- -- -- -- -- -- -- -- -- 97
......................................................
Please enter:
1. Show
2. Insert
3. Find
4. Delete
5. Traverse
6. Size
7. Depth
8. RemoveLeaves
9. RightMinValue
10. LeftMaxValue
11. Maximum
12. Minimum
11
Maximum Value of the tree: 97
Please enter:
1. Show
2. Insert
3. Find
4. Delete
5. Traverse
6. Size
7. Depth
8. RemoveLeaves
9. RightMinValue
10. LeftMaxValue
11. Maximum
12. Minimum
12
Minimum Value of the tree: 12
Please enter:
1. Show
2. Insert
3. Find
4. Delete
5. Traverse
6. Size
7. Depth
8. RemoveLeaves
9. RightMinValue
10. LeftMaxValue
11. Maximum
12. Minimum
8
Removing Leaf node of the tree:
Removed leafs
Please enter:
1. Show
2. Insert
3. Find
4. Delete
5. Traverse
6. Size
7. Depth
8. RemoveLeaves
9. RightMinValue
10. LeftMaxValue
11. Maximum
12. Minimum
1
......................................................
50
25 75
-- 37 -- 87
-- -- 30 -- -- -- -- 93
......................................................
Please enter:
1. Show
2. Insert
3. Find
4. Delete
5. Traverse
6. Size
7. Depth
8. RemoveLeaves
9. RightMinValue
10. LeftMaxValue
11. Maximum
12. Minimum
11
Maximum Value of the tree: 93
Please enter:
1. Show
2. Insert
3. Find
4. Delete
5. Traverse
6. Size
7. Depth
8. RemoveLeaves
9. RightMinValue
10. LeftMaxValue
11. Maximum
12. Minimum
12
Minimum Value of the tree: 25
Please enter:
1. Show
2. Insert
3. Find
4. Delete
5. Traverse
6. Size
7. Depth
8. RemoveLeaves
9. RightMinValue
10. LeftMaxValue
11. Maximum
12. Minimum
6
Size of the tree is: 11
Please enter:
1. Show
2. Insert
3. Find
4. Delete
5. Traverse
6. Size
7. Depth
8. RemoveLeaves
9. RightMinValue
10. LeftMaxValue
11. Maximum
12. Minimum
7
Depth of the tree is: 4
Please enter:
1. Show
2. Insert
3. Find
4. Delete
5. Traverse
6. Size
7. Depth
8. RemoveLeaves
9. RightMinValue
10. LeftMaxValue
11. Maximum
12. Minimum
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.