BinaryTree.java: public class BinaryTree<E extends Comparable<E>> { private Node
ID: 3733659 • Letter: B
Question
BinaryTree.java:
public class BinaryTree<E extends Comparable<E>> {
private Node<E> root;
public BinaryTree (){
root = null;
}
private BinaryTree (Node<E> r){
root = r;
// null or not is controlled inside of Node<E>.
}
public BinaryTree (E data, BinaryTree<E> leftT,
BinaryTree<E> rightT){
root = new Node<E>(data);
if (leftT!=null)
root.left = leftT.root;
else
root.left = null;
if (rightT != null)
root.right = rightT.root;
else
root.right = null;
}
public String toString(){
String s = "";
return rec_toString(root, 1, s);
}
private String rec_toString(Node<E> node, int depth, String s){
s+=" ";
if (node == null)
return s+="null ";
else {
String str ="";
str = rec_toString(node.left, depth+1, s);
str+=s+""+node.data+" ";
str += rec_toString(node.right, depth+1, s);
return str;
}
}
private static class Node<E> {
private E data;
private Node<E> left;
private Node<E> right;
private Node(E item){
data = item;
left = null;
right = null;
}
private Node(E item, Node<E> refLeft, Node<E> refRight){
data = item;
left = refLeft;
right = refRight;
}
}
//end of private class
}
BinaryTreeTest.java:
import javax.swing.JOptionPane;
import java.util.*;
import java.io.*;
public class BinaryTreeTest {
public static void main(String args[]){
BinaryTree<Integer> a = new BinaryTree<Integer>();
String filename =
JOptionPane.showInputDialog("Enter the file name: ");
File inputFile = new File (filename);
try {
Scanner input = new Scanner(inputFile);
while(input.hasNext()){
Integer val = input.nextInt();
a.add(val);
}
input.close();
}
catch (FileNotFoundException e)
{
System.out.println("file reading fails.");
}
System.out.println(a);
Scanner kb = new Scanner(System.in);
System.out.println("1: select the deletion");
System.out.println("2: select the search");
System.out.println("3: find_min");
System.out.println("4: find_max");
System.out.println("5: insert another record");
System.out.println("6: display the tree in infix travel");
System.out.println("7: display the tree in postfix travel");
System.out.println("8: display the tree in prefix travel");
System.out.println("9: display the tree with toString");
System.out.println("0/others: QUiT");
int ans = kb.nextInt();
while(1<=ans && ans<=9){
String str;
switch(ans){
case 1:
str =
JOptionPane.showInputDialog("Key in the item (i.e., content of tree node) to delete:");
a.delete(Integer.parseInt(str));
break;
case 2:
str =
JOptionPane.showInputDialog("Key in the item (i.e., content of tree node) to search:");
System.out.println("Search result: "+a.search(Integer.parseInt(str)));
break;
case 3:
System.out.println("Minimum: "+a.find_min());
break;
case 4:
System.out.println("Maximum: "+a.find_max());
break;
case 5:
str =
JOptionPane.showInputDialog("Key in the item (i.e., content of tree node) to insert");
a.add(Integer.parseInt(str));
break;
case 6:
System.out.println("Display the tree in the infix travel");
System.out.println(a.infixString());
break;
case 7:
System.out.println("Display the tree in the postfix travel");
System.out.println(a.postfixString());
break;
case 8:
System.out.println("Display the tree in the prefix travel");
System.out.println(a.prefixString());
break;
case 9:
System.out.println("The tree display with reserved spaces");
System.out.println(a);
break;
}
System.out.println("1: select the deletion");
System.out.println("2: select the search");
System.out.println("3: find_min");
System.out.println("4: find_max");
System.out.println("5: insert another record");
System.out.println("6: display the tree in infix travel");
System.out.println("7: display the tree in postfix travel");
System.out.println("8: display the tree in prefix travel");
System.out.println("9: display the tree with toString");
System.out.println("0/others: QUiT");
ans = kb.nextInt();
}
}
}
DictionaryTreeTest.java:
import javax.swing.JOptionPane;
import java.util.*;
import java.io.*;
public class DictionaryTreeTest {
public static void main(String args[]){
BinaryTree<String> a = new BinaryTree<String>();
String filename =
JOptionPane.showInputDialog("Enter the file name: ");
File inputFile = new File (filename);
try {
Scanner input = new Scanner(inputFile);
while(input.hasNext()){
String val = input.nextLine();
a.add(val);
}
input.close();
}
catch (FileNotFoundException e)
{
System.out.println("file reading fails.");
}
System.out.println(a);
Scanner kb = new Scanner(System.in);
System.out.println("1: select the deletion");
System.out.println("2: select the search");
System.out.println("3: find_min");
System.out.println("4: find_max");
System.out.println("5: insert another record");
System.out.println("6: display the tree in infix travel");
System.out.println("7: display the tree in postfix travel");
System.out.println("8: display the tree in prefix travel");
System.out.println("9: display the tree with toString");
System.out.println("0/others: QUiT");
int ans = kb.nextInt();
while(1<=ans && ans<=9){
String str;
switch(ans){
case 1:
str =
JOptionPane.showInputDialog("Key in the item (i.e., content of tree node) to delete:");
a.delete(str);
break;
case 2:
str =
JOptionPane.showInputDialog("Key in the item (i.e., content of tree node) to search:");
System.out.println("Search result: "+a.search(str));
break;
case 3:
System.out.println("Minimum: "+a.find_min());
break;
case 4:
System.out.println("Maximum: "+a.find_max());
break;
case 5:
str =
JOptionPane.showInputDialog("Key in the item (i.e., content of tree node) to insert");
a.add(str);
break;
case 6:
System.out.println("Display the tree in the infix travel");
System.out.println(a.infixString());
break;
case 7:
System.out.println("Display the tree in the postfix travel");
System.out.println(a.postfixString());
break;
case 8:
System.out.println("Display the tree in the prefix travel");
System.out.println(a.prefixString());
break;
case 9:
System.out.println("The tree display with reserved spaces");
System.out.println(a);
break;
}
System.out.println("1: select the deletion");
System.out.println("2: select the search");
System.out.println("3: find_min");
System.out.println("4: find_max");
System.out.println("5: insert another record");
System.out.println("6: display the tree in infix travel");
System.out.println("7: display the tree in postfix travel");
System.out.println("8: display the tree in prefix travel");
System.out.println("9: display the tree with toString");
System.out.println("0/others: QUiT");
ans = kb.nextInt();
}
}
}
2. Implement the class BinarvTree to support the program BinaryTreeTest.java. You can test the program with the input files BT1 and BT2 from the above zip file jGRASP exec: java Bin st null null null null null null null 1: select the deletion 2: select the search 3: find min 4: find max 5: insert another record 6: display the tree in infix travel 7: display the tree in postfix travel 8: display the tree in prefix travel 9:display the tree with toString 0/Others : QUT Display the tree in the infix travel 1: select the deletion 2: select the search 3: find min 4: find max 5: insert another record 6: display the tree in infix travel 7: display the tree in postfix travel 8: display the tree in prefix travel 9: display the tree with tostring 0/Others: QUT The same binary tree class should also support the DictionaryTree.java with the input file BTdictionary.Explanation / Answer
code to implement the class Binarytree
public boolean find(int id)
{
while(current!=null)
{
if(current.data==id)
{
}
else if(current.data>id)
{
}
else
{
public boolean delete(int id)
{
while(current.data!=id)
{
if(current.data>id)
{
}
else
{
if(current ==null)
{
if(current==root)
{
if(isLeftChild ==true)
{
}
else
{
else if(current.right==null)
{
if(current==root)
{
}
else if(isLeftChild)
{
}
else
{
else if(current.left==null)
{
if(current==root)
{
}
else if(isLeftChild)
{
}
else
{
}
else if(current.left!=null && current.right!=null)
{
if(current==root)
{
}
else if(isLeftChild)
{
}
else
{
public Node getSuccessor(Node deleleNode)
{
while(current!=null)
{
if(successsor!=deleleNode.right)
{
public void insert(int id)
{
if(root==null)
{
while(true)
{
if(id<current.data)
{
if(current==null)
{
}
else
{
if(current==null)
{
public void display(Node root)
{
if(root!=null)
{
public static void main(String arg[])
{
class Node
{
public Node(int data)
{
public class BinaryTree { public static Node root; public BinaryTree(){ this.root = null; }public boolean find(int id)
{
Node current = root;while(current!=null)
{
if(current.data==id)
{
return true;}
else if(current.data>id)
{
current = current.left;}
else
{
current = current.right; } } return false; }public boolean delete(int id)
{
Node parent = root; Node current = root; boolean isLeftChild = false;while(current.data!=id)
{
parent = current;if(current.data>id)
{
isLeftChild = true; current = current.left;}
else
{
isLeftChild = false; current = current.right; }if(current ==null)
{
return false; } } if(current.left==null && current.right==null){if(current==root)
{
root = null; }if(isLeftChild ==true)
{
parent.left = null;}
else
{
parent.right = null; } }else if(current.right==null)
{
if(current==root)
{
root = current.left;}
else if(isLeftChild)
{
parent.left = current.left;}
else
{
parent.right = current.left; } }else if(current.left==null)
{
if(current==root)
{
root = current.right;}
else if(isLeftChild)
{
parent.left = current.right;}
else
{
parent.right = current.right; }}
else if(current.left!=null && current.right!=null)
{
Node successor = getSuccessor(current);if(current==root)
{
root = successor;}
else if(isLeftChild)
{
parent.left = successor;}
else
{
parent.right = successor; } successor.left = current.left; } return true; }public Node getSuccessor(Node deleleNode)
{
Node successsor =null; Node successsorParent =null; Node current = deleleNode.right;while(current!=null)
{
successsorParent = successsor; successsor = current; current = current.left; }if(successsor!=deleleNode.right)
{
successsorParent.left = successsor.right; successsor.right = deleleNode.right; } return successsor; }public void insert(int id)
{
Node newNode = new Node(id);if(root==null)
{
root = newNode; return; } Node current = root; Node parent = null;while(true)
{
parent = current;if(id<current.data)
{
current = current.left;if(current==null)
{
parent.left = newNode; return; }}
else
{
current = current.right;if(current==null)
{
parent.right = newNode; return; } } } }public void display(Node root)
{
if(root!=null)
{
display(root.left); System.out.print(" " + root.data); display(root.right); } }public static void main(String arg[])
{
BinaryTree b = new BinaryTree(); b.insert(3);b.insert(8); b.insert(1);b.insert(4);b.insert(6);b.insert(2);b.insert(10);b.insert(9); b.insert(20);b.insert(25);b.insert(15);b.insert(16); System.out.println("Original Tree : "); b.display(b.root); System.out.println(""); System.out.println("Check whether Node with value 4 exists : " + b.find(4)); System.out.println("Delete Node with no children (2) : " + b.delete(2)); b.display(root); System.out.println(" Delete Node with one child (4) : " + b.delete(4)); b.display(root); System.out.println(" Delete Node with Two children (10) : " + b.delete(10)); b.display(root); } }class Node
{
int data; Node left; Node right;public Node(int data)
{
this.data = data; left = null; right = null; } }Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.