Add three methods in the binaryTree.java (located below) public void delete(int
ID: 3813044 • Letter: A
Question
Add three methods in the binaryTree.java (located below)
public void delete(int m); // delete the node with key m
public int countNodes();// count number of nodes in the tree
public btNode search(int m);// search for a node with key m and return it
--------------------------------------------------------------
Delete Method (Pseudoode)
--------------------------------------------------------------
If the tree is empty return false.
Else use binary search algorithm to locate the node
If target is not found return false
Else the target is found remove it
--------------------------------------------------------------
Search Method (Pseudocode)
--------------------------------------------------------------
Method starts at root.
Recursive function!
if the tree is empty
return NULL
else if the item in the node equals the target
return the node value
else if the item in the node is greater than the target
return the result of searching the left subtree
else if the item in the node is smaller than the target
return the result of searching the right subtree
--------------------------------------------------------------
Count Method (HINT)
--------------------------------------------------------------
private int countNodes(btNode r)
Use accessors to count the number of nodes both in right and left side of the tree.
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
binaryTree.java
public class binaryTree {
protected btNode root;
/* Constructor */
public binaryTree()
{
root = null;
}
/* Function to check if tree is empty */
public boolean isEmpty()
{
return root == null;
}
/* Functions to insert data */
public void insert(int data)
{
root = insert(root, data);
}
/* Function to insert data recursively */
private btNode insert(btNode node, int data)
{
if (node == null)
node = new btNode(data);
else
{
if (data <= node.getData())
node.left = insert(node.left, data);
else
node.right = insert(node.right, data);
}
return node;
}
/* Function for preorder traversal */
public void preorder()
{
preorder(root);
}
private void preorder(btNode r)
{
if (r != null)
{
System.out.print(r.getData() +" ");
preorder(r.getLeft());
preorder(r.getRight());
}
}
/*
* Students in the LAB should complete three methods as follows
*/
/* Function for inorder traversal *//////////////////////////////////////////////////
public void inorder()
{
//TO DO by students
inorder(root);
}
private void inorder(btNode r)
{
if (r != null)
{
inorder(r.getLeft());
System.out.print(r.getData() +" ");
inorder(r.getRight());
}
}
/* Function for postorder traversal *//////////////////////////////////////////////////
public void postorder()
{
//TO DO by students
postorder(root);
}
private void postorder(btNode r)
{
if (r != null)
{
postorder(r.getLeft());
postorder(r.getRight());
System.out.print(r.getData() +" ");
}
}
/* Recursive approach to find height of binary tree *//////////////////////////////////////////////////
public int findHeight(btNode root) {
// TO DO by students
if (root == null)
return 0;
else
{
/* compute the depth of each subtree */
int lDepth = maxDepth(root.getLeft());
int rDepth = maxDepth(root.getLeft());
/* use the larger one */
if (lDepth > rDepth)
return (lDepth + 1);
else
return (rDepth + 1);
}
}
}
Explanation / Answer
code to delete the node
public void delete(int key)
{
root = deleteUtil(root, key);
}
btNode deleteUtil(btNode root, int key)
{
if (root == null) return root;
if (key < root.key)
root.left = deleteUtil(root.left, key);
else if (key > root.key)
root.right = deleteUtil(root.right, key);
else
{
if (root.left == null)
return root.right;
else if (root.right == null)
return root.left;
root.key = min(root.right);
root.right = deleteUtil(root.right, root.key);
}
return root;
}
int min(btNode root)
{
int min = root.key;
while (root.left != null)
{
min = root.left.key;
root = root.left;
}
return min;
}
code to find the count of nodes
public int countNodes(btNode root) {
if(root==null)
return 0;
int left = getLeftNodes(root)+1;
int right = getRightNodes(root)+1;
if(left==right){
return (2<<(left-1))-1;
}else{
return countNodes(root.left)+countNodes(root.right)+1;
}
}
public int getLeftNodes(btNode left){
if(left==null) return 0;
int lheight=0;
while(left.left!=null){
lheight++;
left = left.left;
}
return lheight;
}
public int getRightNodes(btNode right){
if(right==null) return 0;
int rheight=0;
while(right.right!=null){
rheight++;
right = right.right;
}
return rheight;
}
code to serach node
public btNode search(int m){
btNode temp = root;
if(temp != null){
if(temp.data == m){
return temp;
} else {
btNode foundNode = search(m, temp.left);
if(foundNode == null) {
foundNode = search(m, temp.right);
}
return foundNode;
}
} else {
return null;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.