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; } // 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("\nPreorder traversal: ");
preOrder(root);
break;
case 2: System.out.print("\nInorder traversal: ");
inOrder(root);
break;
case 3: System.out.print("\nPostorder 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 + " ");
}
}
// -------------------------------------------------------------
Add the following methods:
Find the number of leaves of the tree which are left child of their parent.
Find the number of internal nodes.
Find the maximum value in a binary search tree.
Print a binary inorder.
Homework Answers
Java code for the above problem:
Node.java:
-------------
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
//------------------------------------------------------------------
Tree.java:
----------
import java.io.IOException;
import java.util.Stack;
public class Tree {
private Node root; // first node of tree
// -------------------------------------------------------------
public Tree() // constructor
{
root = null;
} // no nodes in tree yet
public Node getRoot() {
return this.root;
}
// -------------------------------------------------------------
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("\nPreorder traversal: ");
preOrder(root);
break;
case 2:
System.out.print("\nInorder traversal: ");
inOrder(root);
break;
case 3:
System.out.print("\nPostorder 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 boolean isLeaf(Node localNode) {
if(localNode == null){
return false;
} else if (localNode.leftChild == null && localNode.rightChild == null) {
return true;
}
return false;
}
public int leftLeaves(Node root) {
int count = 0;
boolean isLeftChild = true;
if(root != null) {
if(isLeaf(root.leftChild)) {
count += 1;
} else {
count += leftLeaves(root.leftChild);
}
count += leftLeaves(root.rightChild);
}
return count;
}
public int internalNodes(Node root) {
if(root == null || (root.leftChild==null && root.rightChild==null)) {
return 0;
}
return 1 + internalNodes(root.leftChild)+ internalNodes(root.rightChild);
}
public int maxNode(Node root) {
if(getRoot() == null) {
return 0;
}
if(root.rightChild==null) {
return root.iData;
} else {
return maxNode(root.rightChild);
}
}
}
// -------------------------------------------------------------
TreeMain.java:
--------------
/**
* Created by pchandul on 20-Nov-18.
*/
public class TreeMain {
public static void main(String[] args) {
Tree t1 = new Tree();
t1.insert(50, 55.55);
t1.insert(20, 60.00);
t1.insert(45, 70.55);
t1.insert(65, 89.12);
t1.insert(100, 34.95);
t1.insert(80, 52.52);
t1.insert(10, 67.00);
System.out.println("Inorder travesal of the tree is: ");
t1.traverse(2);
System.out.println("Number of leaves which are leftchild of their parent: " + t1.leftLeaves(t1.getRoot()));
System.out.println("Number of internal node are: " + t1.internalNodes(t1.getRoot()));
System.out.println("Maximum value in the tree: " + t1.maxNode(t1.getRoot()));
}
}
Sample output:
Inorder travesal of the tree is:
Inorder traversal: 10 20 45 50 65 80 100
Number of leaves which are leftchild of their parent: 2
Number of internal node are: 4
Maximum value in the tree: 100
Process finished with exit code 0
Add Answer to:
Using the following implementation of Tree
class Node
{
public int
iData; //
data item (key)
public...
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....
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;...
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...
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...
Q. write the algorithm for each function in this code: void insert(int x, node*&p) { //cheak...
Q. write the algorithm for each function in this code: void insert(int x, node*&p) { //cheak if the pointer is pointing to null. if (p==NULL) { p = new node; p->key=x; p->left=NULL; p->right=NULL; } else { //Cheak if the element to be inserted is smaller than the root. if (x < p->key) { //call the function itself with new parameters. insert(x,p->left); } //cheak if the alement to be inserted...
write a new test program called RemoveDuplicates.java. The program reads text input from keyboard or a text file and adds the words to a BST. The program then traverses the BST and prints out the word...
write a new test program called RemoveDuplicates.java. The program reads text input from keyboard or a text file and adds the words to a BST. The program then traverses the BST and prints out the words in order (based on ASCII/UNICODE order) on the screen (or to output text file). Note that you may need to make some changes to BST.java. Sample test: ----jGRASP exec: java -ea removeDuplicates Original Text: a B 2 n w C q K l 0...
Test Data would be as follows: Using java language. Build an expression tree. • When you...
Test Data would be as follows:
Using java language. Build an expression tree. • When you see a number: o you create a new node with the number as the data. o Then you push the new node to the stack. . When you see a binary operator: 0 You create a new Node for the operator. Then you pop and set the right child. Then you pop and set the left child o Then you push the new node...
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 =...
In Java. How would this method look? LinkedBinaryTree.java import java.util.Iterator; public class LinkedBinaryTree implements BinaryTreeADT {...
In Java. How would this method look?
LinkedBinaryTree.java
import java.util.Iterator;
public class LinkedBinaryTree implements BinaryTreeADT {
private BinaryTreeNode root;
/**
* Creates an empty binary tree.
*/
public LinkedBinaryTree() {
root = null;
}
/**
* Creates a binary tree from an existing root.
*/
public LinkedBinaryTree(BinaryTreeNode root) {
this.root = root;
}
/**
* Creates a binary tree with the specified element...
Can you take a look at my code that why the maxDepth function is not working?...
Can you take a look at my code that why the maxDepth function is not working? public class BinaryTree { class Node{ int key; Node left,right; public Node(int item) { key = item; left = right = null; } } Node root; public void BinaryTree(){ root = null; } void...
Test Data would be as follows:
Using java language. Build an expression tree. • When you see a number: o you create a new node with the number as the data. o Then you push the new node to the stack. . When you see a binary operator: 0 You create a new Node for the operator. Then you pop and set the right child. Then you pop and set the left child o Then you push the new node...
In Java. How would this method look?
LinkedBinaryTree.java
import java.util.Iterator;
public class LinkedBinaryTree implements BinaryTreeADT {
private BinaryTreeNode root;
/**
* Creates an empty binary tree.
*/
public LinkedBinaryTree() {
root = null;
}
/**
* Creates a binary tree from an existing root.
*/
public LinkedBinaryTree(BinaryTreeNode root) {
this.root = root;
}
/**
* Creates a binary tree with the specified element...
Most questions answered within 3 hours.
-
A 50g ice cube is taken out of a freezer at 0 degrees Celsius
and put...
asked 1 hour ago -
How do ratios help you determine trends? What specific
information do managers look at? Is there...
asked 1 hour ago -
A wavelength of 514 nm is used to find an unknown diffraction
grating. If the separation...
asked 1 hour ago -
Use the central limit theorem to find the mean and standard
error of the mean of...
asked 1 hour ago -
You will be given a file that will contain averages for classes
which are divided into...
asked 1 hour ago -
A Pew Research Center poll surveyed a random sample 850 voters
and asked them if they...
asked 1 hour ago -
Design a class named
NumDays, to
store a value that represents a number of hours and...
asked 1 hour ago -
(R)-2-chloro-(S)-3-bromobutane and
(S)-2-chloro-(S)-3-bromobutane are: A. enantiomers. B.
diastereomers. C. meso compounds. D. the same molecule.
asked 1 hour ago -
1_ What is the Frank-Starling law of the heart? And why the
heart cannot function on...
asked 1 hour ago -
The method of tree ring dating gave the following years A.D. for
an archaeological excavation site....
asked 1 hour ago -
Calculate (in N) the force a mother must exert to hold her 12.0
kg child in...
asked 1 hour ago -
A new lie-detector test has been devised and must be tested
before it is put into...
asked 2 hours ago