QuestionQuestion

Transcribed TextTranscribed Text

Project 3 The third programming project involves writing a program that allows the user to enter a binary tree in a parenthesized prefix format and then allows it to be categorized and allows various features of that tree to be displayed. An example of a tree written in the input format is the following: (A G (j) (1)) (z (5))) In the above example, data in each node of the tree contains a single alphanumeric character. No spaces are permitted. Each tree is enclosed in parentheses. Inside those parentheses, after the single character are either zero, one or two subtrees also enclosed in parentheses. When only one subtree is present, it is the left subtree and when two are present, they represent the left and right subtrees. So the above string represents the following binary tree: A G z j 1 5 The various categorizations include the following: 1. Whether the binary tree is balanced, which means for each node in the tree, the absolute difference between the height of its left and right subtrees is at most 1. The above binary tree is balanced. 2. Whether the binary tree is full. A full binary tree has the maximum number of nodes for a tree of its height. The above tree is not full because a tree of that height can contain 7 nodes, but the above tree only has 6. 3. Whether the binary tree is proper. In a proper binary tree, every node has either 0 or 2 children. The above tree is not proper because the node containing Z has only one child. In addition, the program should allow the user to request that each of the following features of the tree be displayed: 1. The height of the tree. The height of a tree is the maximum level of all of its nodes. The root node containing A is at the level 0. Because all three leaf nodes in the above tree are at level 2, its height is 2. 2. The number of nodes in the tree. As previously mentioned, the above tree has 6 nodes. 3. An fully parenthesized inorder traversal of the tree. The following should be displayed as the inorder traversal of the above tree: j ) G ( 1 A ( ( 5 ) Z ) ) This project should consist of three classes. The main class should create a GUI that allows the user to input a tree in the above described format and then construct the tree once the Make Tree button is clicked. The GUI should look as follows: Binary Tree Categorizer - X Enter Tree: (A(G(j)(1))(z(5))) Make Tree Is Balanced? Is Full? Is Proper? Height Nodes Inorder Output: (((())G(1))A((5)z)) The GUI must be generated by code that you write. You may not use a drag-and-drop GUI generator. The second class should be the Bi naryTree class, which should contain a static nested class to define the nodes of the binary tree, together with a constructor that is called when the Make Tree button is clicked and is supplied the string representation of the tree and constructs the actual tree from that string. In addition, it should have public methods that are called when each of the remaining six buttons are clicked. All of those public methods should have corresponding private methods that accomplish their tasks using recursion. The third class should be named Inva lidTreeSyntax, which defines a checked exception. It should be thrown when a invalid string is supplied and the Make Tree button is clicked. It should be caught in the main class and a Jopt ionPane window should be displayed that describes the reason for the invalid syntax. You are to submit two files. 1. The first is a zip file that contains all the source code for the project. The zip file should contain only source code and nothing else, which means only the java files. If you elect to use a package the ava files should be in a folder whose name is the package name. Every outer class should be in a separate java file with the same name as the class name. Each file should include a comment block at the top containing your name, the project name, the date, and a short description of the class contained in that file. 2. The second is a Word document (PDF or RTF is also acceptable) that contains the documentation for the project, which should include the following: a. A UML class diagram that includes all classes you wrote. Do not include predefined classes. You need only include the class name for each individual class, not the variables or methods b. A test plan that includes test cases that you have created indicating what aspects of the program each one is testing c. A short paragraph on lessons learned from the project

Solution PreviewSolution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

import java.util.LinkedList;
import java.util.List;

/**
* Binary Tree Class,
* it contains a static class called Node
* which represent a binary tree node.
*
* This class contains methods
* to create a binary tree, finds
* its height, balanced, full
* and proper properties.
*
* @author
*
*/
public class BinaryTree {

private Node root = null;

static class Node {

private char data;
private Node left;
private Node right;

public Node(char charAt, Node left, Node right) {
// TODO Auto-generated constructor stub
this.data = charAt;
this.left = left;
this.right = right;
}
}

public BinaryTree(String prefixFormat) throws InvalidTreeSyntaxException {
String prefixString = removeParenthesis(prefixFormat);
root = makeTree(prefixString);
}

private String removeParenthesis(String input) throws InvalidTreeSyntaxException {
if (input != null && input.length() > 1) {
if (input.charAt(0) == '(') {
if (input.charAt(input.length()-1) == ')') {
return input.substring(1, input.length()-1);
} else {
throw new InvalidTreeSyntaxException("Invalid tree");
}
} else {
return input;
}
} else {
throw new InvalidTreeSyntaxException("Invalid tree");
}
}

// define the makeTree method that builds the binary tree
private Node makeTree(String str) throws InvalidTreeSyntaxException{
if(str == null || str.isEmpty()) return null;
if (str.charAt(0)=='(' || str.charAt(0)==')') {
throw new InvalidTreeSyntaxException("Invalid tree");
}
Node n = new Node(str.charAt(0), null, null);
// get left substring (without the surrounding parenthesis)
String sLeft = getStringLeft(str);
// get right substring (without the surrounding parenthesis)
// returns null if right subtree is missing
String sRight = getStringRight(str);
if (sLeft != null && sRight == null) n.left = makeTree(sLeft);
else { n.left = makeTree(sLeft); n.right = makeTree(sRight);}
return n;
}


private String getStringRight(String str) throws InvalidTreeSyntaxException {
// TODO Auto-generated method stub
List<Character> stack = new LinkedList<>();
int endIndex = getLeftEndIndex(str);
int startIndex = -1;
if (str != null) {
for (int i=endIndex+1; i<str.length(); i++) {
if (str.charAt(i) == '(') {
stack.add('(');
if (startIndex == -1) {
startIndex = i+1;
}
}
if (str.charAt(i) == ')') {
if (stack.size() > 0) {
stack.remove(stack.size()-1);
}

if (stack.isEmpty()) {
endIndex = i;
break;
}
}
}...
$65.00 for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Java Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats