1. Write a function in Tree class which returns true if and only if the tree...
1. Write a function in Tree class which returns true if and only if the tree satisfies the binary search tree property.
The function’s header line is
public boolean isValidBST()
And in the attached code, you just need to finish the function after the comment: “//Instructor hint: please write your code here:”
Make sure you execute your code, and the result in the main function after calling your function should be same as the prompt message I write. Clearly you can add extra functions in the class to help you finish this function.
Use this code:
// tree.java
// demonstrates binary tree
// to run this program: C>java TreeApp
import java.io.*;
import java.util.*; // for Stack class
////////////////////////////////////////////////////////////////
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
////////////////////////////////////////////////////////////////
class Tree
{
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 void displayTree()
{
Stack<Node> globalStack = new Stack<Node>();
globalStack.push(root);
int nBlanks = 32;
boolean isRowEmpty = false;
System.out.println(
"......................................................");
while(isRowEmpty==false)
{
Stack<Node> localStack = new Stack<Node>();
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()
// -------------------------------------------------------------
public boolean isValidBST() {
return true;
}// end isValidBST()
// -------------------------------------------------------------
} // end class Tree
////////////////////////////////////////////////////////////////
public class TreeApp
{
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);
theTree.displayTree();
System.out.println("It is a BST tree, after call your function, your result should be true: ");
System.out.println(theTree.isValidBST());
//Instructor: I change the node's value from 75 to 40, and now it is NOT a BST tree.
Node found = theTree.find(75);
found.iData = 40;
theTree.displayTree();
System.out.println("It is NOT a BST tree since one node's value is changed from 75 to 40, after call your function, your result should be false: ");
System.out.println(theTree.isValidBST());
} // 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);
}
// -------------------------------------------------------------
} // end class TreeApp
////////////////////////////////////////////////////////////////Homework Answers
Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. If not, PLEASE let me know before you rate, I’ll help you fix whatever issues. Thanks
//completed code
// demonstrates binary tree
// to run this program: C>java TreeApp
import java.io.*;
import java.util.*; // for Stack class
////////////////////////////////////////////////////////////////
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
// //////////////////////////////////////////////////////////////
class Tree {
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 void displayTree() {
Stack<Node> globalStack = new Stack<Node>();
globalStack.push(root);
int nBlanks = 32;
boolean isRowEmpty = false;
System.out
.println("......................................................");
while (isRowEmpty == false) {
Stack<Node> localStack = new Stack<Node>();
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()
// -------------------------------------------------------------
public boolean isValidBST() {
// calling helper method 1 to check if it is a valid bst, passing root
// node
return isValidBST(root);
}// end isValidBST()
// helper method 1 to check if it is a valid bst
private boolean isValidBST(Node node) {
// empty node is a valid bst
if (node == null) {
return true;
}
// if node is leaf, it is a valid bst
if (node.leftChild == null && node.rightChild == null) {
return true;
}
// getting value at current node
int value = node.iData;
// if any value left of node is bigger than current value, not a valid
// bst
if (node.leftChild != null && value <= max(node.leftChild)) {
return false;
}
// if any value right of node is smaller than current value, not a valid
// bst
if (node.rightChild != null && value >= min(node.rightChild)) {
return false;
}
// otherwise checking if left subtree is a valid bst and right subtree
// is a valid bst, returning true if both return true
return isValidBST(node.leftChild) && isValidBST(node.rightChild);
}
// helper method 2 to find the maximum value starting from a given node, to
// assist helper method 1
// pre condition: node is not null
private int max(Node node) {
// if this is leaf node, returning data
if (node.leftChild == null && node.rightChild == null) {
return node.iData;
}
// storing current value as maximum
int max_value = node.iData;
// if left node is not null,
if (node.leftChild != null) {
// calling max() method passing left node, and if the returned value
// is bigger than max_value, setting it as new max_value, otherwise
// no change
max_value = Math.max(max_value, max(node.leftChild));
}
// if right node is not null,
if (node.rightChild != null) {
// calling max() method passing right node, and if the returned
// value
// is bigger than max_value, setting it as new max_value, otherwise
// no change
max_value = Math.max(max_value, max(node.rightChild));
}
// returning the maximum value
return max_value;
}
// helper method 3, very similar to max, but finds minimum value instead.
// this is also to assist helper method 1
private int min(Node node) {
if (node.leftChild == null && node.rightChild == null) {
return node.iData;
}
int min_value = node.iData;
if (node.leftChild != null) {
min_value = Math.min(min_value, min(node.leftChild));
}
if (node.rightChild != null) {
min_value = Math.min(min_value, min(node.rightChild));
}
return min_value;
}
// -------------------------------------------------------------
} // end class Tree
// //////////////////////////////////////////////////////////////
public class TreeApp {
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);
theTree.displayTree();
System.out
.println("It is a BST tree, after call your function, your result should be true: ");
System.out.println(theTree.isValidBST());
// Instructor: I change the node's value from 75 to 40, and now it is
// NOT a BST tree.
Node found = theTree.find(75);
found.iData = 40;
theTree.displayTree();
System.out
.println("It is NOT a BST tree since one node's value is changed from 75 to 40, after call your function, your result should be false: ");
System.out.println(theTree.isValidBST());
} // 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);
}
// -------------------------------------------------------------
} // end class TreeApp
// //////////////////////////////////////////////////////////////
/*OUTPUT*/
......................................................
50
25 75
12 37 -- 87
-- -- 30 43 -- -- -- 93
-- -- -- -- -- 33 -- -- -- -- -- -- -- -- -- 97
......................................................
It is a BST tree, after call your function, your result should be true:
true
......................................................
50
25 40
12 37 -- 87
-- -- 30 43 -- -- -- 93
-- -- -- -- -- 33 -- -- -- -- -- -- -- -- -- 97
......................................................
It is NOT a BST tree since one node's value is changed from 75 to 40, after call your function, your result should be false:
false
Add Answer to:
1. Write a function in Tree class which returns true if and only
if the tree...
Need help in the below question. Answer in java Start with the tree.java program (Listing 8.1)...
Need help in the below question. Answer in java Start with the tree.java program (Listing 8.1) and modify it to create a binary tree from a string of letters (like A, B, and so on) entered by the user. Each letter will be displayed in its own node. Construct the tree so that all the nodes that contain letters are leaves. Parent nodes can contain some non-letter symbol like +. Make sure that every parent node has exactly two children....
Using the following implementation of Tree class Node { public int iData; // data item (key) public...
Using the following implementation of Tree 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 //------------------------------------------------------------------ import java.io.IOException; import java.util.Stack; public class Tree { private Node root; // first node of tree // ------------------------------------------------------------- public Tree() // constructor { root = null; }...
Please I need help ASAP Java Programing: Binary Search Tree Fully implement the BST class in Listing 25.4 (on page 961 of the 11th Edition of the text). Design and write a (main) driver program to com...
Please I need help ASAP Java Programing: Binary Search Tree Fully implement the BST class in Listing 25.4 (on page 961 of the 11th Edition of the text). Design and write a (main) driver program to completely test every method in the BST class to ensure the class meets all its requirements. You should read the Listing 25.5: TestBST.java for an idea of what your program should look like. Listing 25.4 BST.java public class BST> extends AbstractTree { protected TreeNode...
3. (Gaddis Exercises 20.4) Tree Height Write a recursive member function for the BinaryTree class that...
3. (Gaddis Exercises 20.4) Tree Height Write a recursive member function for the BinaryTree class that returns the height of the tree. The height of the tree is the number of levels it contains. Demonstrate the function in a driver program. CPP FILE CODE: #include "BinaryTree.h" #include <iostream> using namespace std; BinaryTree::BinaryTree() { root = NULL; } BinaryTree::~BinaryTree() { destroy(root); } bool BinaryTree::search(int data) { return search(data, root); } void BinaryTree::insert(int data) { insert(data, root); } void BinaryTree::traverseInOrder() { traverseInOrder(root);...
I need to do a tree sort method but the treesortMethod is not working /****Binarytree class****\...
I need to do a tree sort method but the treesortMethod is not working /****Binarytree class****\ package Tree; public class BinaryTree { private TreeNode root; // head of the list //constructor - create an empty binary tree public BinaryTree() { root = null; } //isEmpty() - return true if tree is empty, false otherwise public boolean isEmpty() { return (root == null); } //deleteTree() - remove all items from tree public void deleteList() { root =...
Question - modify the code below so that for a node, the value of every node...
Question - modify the code below so that for a node, the value of every node of its right subtree is less the node, and the value of each node of its left subtree is greater than the node. - create such a binary tree in the Main method, and call the following method: InOrder(Node theRoot), PreOrder(Node theRoot), PostOrder(Node theRoot), FindMin(), FindMax(), Find(int key) using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks;...
1) Extend the Binary Search Tree ADT to include a public method leafCount that returns the...
1) Extend the Binary Search Tree ADT to include
a public method leafCount that returns the number of leaf nodes in
the tree.
2) Extend the Binary Search Tree ADT to include a
public method singleParent-Count that returns the number of nodes
in the tree that have only one child.
3) The Binary search tree ADT is extended to
include a boolean method similarTrees that receives references to
two binary trees and determines whether the shapes of the trees are...
Question B1 You are given the following Java classes: public class Queue { private static class...
Question B1 You are given the following Java classes: public class Queue { private static class Node { Object object; Node next; Node () { object = null; next = null; } Node (Object object, Node next) { this.object = object; this.next = next; private Node header; private int size = 0; // size shows the no of elements in queue public Object dequeue () { if (size == 0 ) { return null; else { Object remove_object = header.object;...
BST JAVA FILE import java.util.*; public class BST <E extends Comparable <E>> { private TreeNode<E>...
BST JAVA FILE import java.util.*; public class BST <E extends Comparable <E>> { private TreeNode<E> overallRoot; public BST() { overallRoot = null; } // ************ ADD ************ // public void add(E addThis) { if (overallRoot == null) { overallRoot = new TreeNode<>(addThis); } else { add(overallRoot, addThis); } } private TreeNode<E> add(TreeNode<E> node, E addThis) { if...
Return a method as an expression tree Hi guys. I need to return a method as...
Return a method as an expression tree
Hi guys.
I need to return a method as an expression tree, it's currently
returning null.
public static ExpressionTree getExpressionTree(String
expression)
throws Exception {
char[] charArray = expression.toCharArray();
Node root = et.constructTree(charArray);
System.out.println("infix expression is");
et.inorder(root);
return et;
}
In the above method, et needs to have a value.
-- Take a look at the complete class below.
Kindly assist.
; public class ExpressionTree extends BinaryTree { private static final String DELIMITERS...
1) Extend the Binary Search Tree ADT to include
a public method leafCount that returns the number of leaf nodes in
the tree.
2) Extend the Binary Search Tree ADT to include a
public method singleParent-Count that returns the number of nodes
in the tree that have only one child.
3) The Binary search tree ADT is extended to
include a boolean method similarTrees that receives references to
two binary trees and determines whether the shapes of the trees are...
Question B1 You are given the following Java classes: public class Queue { private static class Node { Object object; Node next; Node () { object = null; next = null; } Node (Object object, Node next) { this.object = object; this.next = next; private Node header; private int size = 0; // size shows the no of elements in queue public Object dequeue () { if (size == 0 ) { return null; else { Object remove_object = header.object;...
Return a method as an expression tree
Hi guys.
I need to return a method as an expression tree, it's currently
returning null.
public static ExpressionTree getExpressionTree(String
expression)
throws Exception {
char[] charArray = expression.toCharArray();
Node root = et.constructTree(charArray);
System.out.println("infix expression is");
et.inorder(root);
return et;
}
In the above method, et needs to have a value.
-- Take a look at the complete class below.
Kindly assist.
; public class ExpressionTree extends BinaryTree { private static final String DELIMITERS...
Most questions answered within 3 hours.
-
the period of a pendulum on earth is 5 seconds. what will be the
period of...
asked 14 minutes ago -
The
act of turning media against itself, such as flash mobs and
billboard is called
a....
asked 9 minutes ago -
A set of length measurements are obtained with the values 165.6
± 0.3, 165.1± 0.4,166.4± 1.0,...
asked 11 minutes ago -
Vertical Analysis
Income statement information for Einsworth Corporation
follows:
Sales
$237,000
Cost of goods sold
78,210...
asked 17 minutes ago -
A simple random sample was taken to test the claim that the
population mean is no...
asked 12 minutes ago -
Overview
JAVA LANGUAGE PROBLEM:
The owner of a restaurant wants a program to manage online
orders...
asked 18 minutes ago -
1- What is “progressive production?”
2- Where did the assembly line originate? (Name the industry)
3....
asked 15 minutes ago -
NPV
Project L costs $60,000 it’s expected cash inflows are $13,000
per year for 10 years,...
asked 20 minutes ago -
What would you expect the observed boiling point to be at 10
torrs of a liquid...
asked 28 minutes ago -
write a javascript jquery code to display calendar and let it be
sticked on the textbox...
asked 36 minutes ago -
A Call Spread is
A.
The simultaneous purchase of a call and
sale of a put...
asked 35 minutes ago -
In response to concerns about a future recession, the government
decides to give consumers a tax...
asked 37 minutes ago