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
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.
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
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
}
*/
/* Function for postorder traversal *//////////////////////////////////////////////////
/* public void postorder()
{
//TO DO by students
}*/
/* Recursive approach to find height of binary tree *//////////////////////////////////////////////////
/* public int findHeight(btNode root) {
// TO DO by students
}
*/
}
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help