Question
Consider the following declaration of Class BinarySearchTree and TreeNode (an inner class):
public class BinarySearchTree
{
private static class TreeNode
{
// 3 private instance variables
private int data;
private TreeNode leftLink;
private TreeNode rightLink;
// One no-argument constructor for an empty node.
Public TreeNode()
{
data = 0;
leftLink = rightLink = null;
}
// One one-argument constructor
public TreeNode (int newData, TreeNode newLeftLink, TreeNode newRightLink)
{
data = newData;
leftLink = newLeftLink;
rightLink = newRightLink;
}
} //End of TreeNode inner class
// Declaration of class BinarySearchTree begins here.
// Three instance variables.
private TreeNode root;
private TreeNode parent;
private int parentLink;
// One no-argument constructor for creating an empty binary tree.
public BinarySearchTree ( )
{
root = parent = null;
parentLink = 0;
}
// One copy constructor to create one by making a deep copy of an existing BST given
// by the root of the tree which is the lone parameter.
public BinarySearchTree (TreeNode rootNode)
{
parent = null;
parentLink = 0;
root = copyBST (rootNode);
}
public TreeNode copyBST (TreeNode rootNode)
// Recursively copies a BST rooted at the given rootNode and returns
// the root node of the copied BST.
{
if (rootNode == null) return rootNode;
// else the current tree or subtree not empty yet.
TreeNode leftChild = copyBST (rootNode.leftLink);
TreeNode rightChild = copyBST (rootNode.rightLink);
return new TreeNode (rootNode.data, leftChild, rightChild);
}
Give a complete definition of the following Copy Constructor: public. Binary SearchTree (BinarySearchTree givenBSD
Explanation / Answer
public class BinarySearchTree { public static Node root; public BinarySearchTree(){ this.root = null; } public boolean find(int id){ Node current = root; while(current!=null){ if(current.data==id){ return true; }else if(current.data>id){ current = current.left; }else{ current = current.right; } } return false; } public boolean delete(int id){ Node parent = root; Node current = root; boolean isLeftChild = false; while(current.data!=id){ parent = current; if(current.data>id){ isLeftChild = true; current = current.left; }else{ isLeftChild = false; current = current.right; } if(current ==null){ return false; } } //if i am here that means we have found the node //Case 1: if node to be deleted has no children if(current.left==null && current.right==null){ if(current==root){ root = null; } if(isLeftChild ==true){ parent.left = null; }else{ parent.right = null; } } //Case 2 : if node to be deleted has only one child else if(current.right==null){ if(current==root){ root = current.left; }else if(isLeftChild){ parent.left = current.left; }else{ parent.right = current.left; } } else if(current.left==null){ if(current==root){ root = current.right; }else if(isLeftChild){ parent.left = current.right; }else{ parent.right = current.right; } }else if(current.left!=null && current.right!=null){ //now we have found the minimum element in the right sub tree Node successor = getSuccessor(current); if(current==root){ root = successor; }else if(isLeftChild){ parent.left = successor; }else{ parent.right = successor; } successor.left = current.left; } return true; } public Node getSuccessor(Node deleleNode){ Node successsor =null; Node successsorParent =null; Node current = deleleNode.right; while(current!=null){ successsorParent = successsor; successsor = current; current = current.left; } //check if successor has the right child, it cannot have left child for sure // if it does have the right child, add it to the left of successorParent. // successsorParent if(successsor!=deleleNode.right){ successsorParent.left = successsor.right; successsor.right = deleleNode.right; } return successsor; } public void insert(int id){ Node newNode = new Node(id); if(root==null){ root = newNode; return; } Node current = root; Node parent = null; while(true){ parent = current; if(id