Consider the following declaration of Class BinarySearchTree and TreeNode (an in

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);
}

Suppose that the class TreeNode implemented the Comparable Interface. give a complete redefinition of the following two existing methods by taking advantage of this hypothetical implementation: public TreeNode isInsubtree (int oldItem public TreeNode replace (TreeNode target

Explanation / Answer

PROGRAM CODE:

public class BinarySearchTree
{
private static class TreeNode implements Comparable
{
// 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);
}

public TreeNode isInSubtree(int oldItem)
{
TreeNode node = new TreeNode(oldItem, null, null);
TreeNode rootNode = root;
while(rootNode != null)
{
if(rootNode.compareTo(node) == 0)
return rootNode;
else if(rootNode.compareTo(node) < 1)
rootNode = rootNode.leftLink;
else if(rootNode.compareTo(node) > 1)
rootNode = rootNode.rightLink;
}
return null;
}

public TreeNode replace(Treenode target)
{
TreeNode rootNode = root;
while(rootNode != null)
{
if(rootNode.compareTo(target) == 0)
return rootNode;
else if(rootNode.compareTo(node) < 1)
rootNode = rootNode.leftLink;
else if(rootNode.compareTo(node) > 1)
rootNode = rootNode.rightLink;
}
return null;
}
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.