Add three methods in the binaryTree.java (located below) public void delete(int
ID: 3809336 • 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.
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
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
}
*/
}
Explanation / Answer
InOrder Traversal:
There are three stpes invloved in inOrder Traversal.
a) Traverse to Left Subtree
b) process the current node (display)
c) Traverse to Right Subtree
/* Function for inorder traversal
public void inorder()
{
inorder(root);
}
private void inorder(btNode r)
{
if (r != null) // condition to stop recursion
{
inorder(r.getLeft()); //Traverse to Left Subtree
System.out.print(r.getData() +" "); //process(display) root/current node
inorder(r.getRight()); // Traverse to Right subtree
}
}
Postorder Traversal:
There are three stpes invloved in PostOrder Traversal.
a) Traverse to Left Subtree
b) Traverse to Right Subtree
c) process the current node (display)
public void postorder()
{
postorder(root);
}
private void postorder(btNode r)
{
if (r != null) // condition to stop recursion
{
postorder(r.getLeft()); //Traverse to Left Subtree
postorder(r.getRight()); //Traverse to Right Subtree
System.out.print(r.getData() +" "); //process(display) root/current node
}
}
FIndHeight:
Below logic will calculate height of Left Subtree & height of right subtree. Maximum of these two plus 1 will be height of the tree.
public int findHeight(btNode root)
{
if(root == null) //
return 0;
int leftHeight = findHeight(r.getLeft()); // Calculation of Left Subtree
int rightHeight = maxDepth(r.getRight()); // Calculation of Right subtree
if (leftHeight > rightHeight) // if Left Subtree height is more
return(leftHeight+1); // LeftHeight +1 will be height of the tree
return(rightHeight+1); // RightHeight + 1 will be height of the tree
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.