I cannot edit anything else. I have highlighted what can be edited. Given: MyTre
ID: 3705313 • Letter: I
Question
I cannot edit anything else. I have highlighted what can be edited.
Given: MyTree.java & TreeNode.java
public class MyTree{
private TreeNode root;
public MyTree(){
root=null;
}
public void remove(int data){
//implement this method to remove a node with the same data value
}
public void printReverse(){
//implement this method to print data in descending order
}
public void display(){
//implement to display the tree structure
}
public boolean isEmpty(){ return root==null;}
public int size(){
return sizeHelper(root);
}
private int sizeHelper(TreeNode node){
if(node==null) return 0;
else return 1+sizeHelper(node.getLeft())+sizeHelper(node.getRight());
}
public boolean search(int data){
return searchHelper(root, data);
}
private boolean searchHelper(TreeNode node, int data){
if(node==null) return false;
if(node.getData()==data) return true;
else if(node.getData()<data)
return searchHelper(node.getRight(),data);
else
return searchHelper(node.getLeft(), data);
}
public void add(int data){
root=addHelper(root, data);
}
private TreeNode addHelper(TreeNode node, int data){
if(node==null) node=new TreeNode(data);
else if(data<=node.getData()) //or call compareTo method
node.setLeft(addHelper(node.getLeft(), data));
else
node.setRight(addHelper(node.getRight(), data));
return node;
}
public void printInorder(){
printHelper(root);
}
private void printHelper(TreeNode node){
if(node!=null){
printHelper(node.getLeft());
System.out.println(node.getData());
printHelper(node.getRight());
}
}
}
public class TreeNode implements Comparable<TreeNode>{
private int data;
private TreeNode left;
private TreeNode right;
public TreeNode(int data){
this.data=data;
left=right=null;
}
public int getData(){
return data;
}
public TreeNode getLeft(){
return left;
}
public TreeNode getRight(){
return right;
}
public void setData(int data){
this.data = data;
}
public void setLeft(TreeNode left){
this.left = left;
}
public void setRight(TreeNode right){
this.right = right;
}
public int compareTo(TreeNode node){
return data-node.getData();
}
}
Explanation / Answer
public class MyTree{
private TreeNode root;
public MyTree(){
root=null;
}
public void remove(int value){
//implement this method to remove a node with the same data value
if (!isEmpty())
{
// Removal of root?
if (value == root.data)
root = replacement(root);
else
{
// Find the node to be removed and replace it
treeNode parent = root, current;
boolean finished = false;
// Starting from a child of the root node
if (value < root.data)
current = root.left;
else
current = root.right;
// Loop until node is found or tree exhausted
while (current != null && !finished)
{
if (current.data == value)
{
// Node to be removed found, remove and replace
if (current == parent.left)
parent.left = replacement(current);
else
parent.right = replacement(current);
finished = true;
}
else
{
// Move on down the tree
parent = current;
if (value < current.data)
current = current.left;
else
current = current.right;
}
}
}
}
}
private treeNode replacement(treeNode t)
{
// Case 1: Removing leaf node
if (t.left == null && t.right == null)
return null;
// Case 2: One non-empty subtree
else if (t.left != null && t.right == null)
return t.left;
else if (t.left == null && t.right != null)
return t.right;
// Case 3: Two non-empty subtrees.
// Replacing with rightmost node in left subtre
else
{
// Special case, t.left has no right subtree
if (t.left.right == null)
{
t.left.right = t.right;
return t.left;
}
// Finding rightmost node in left subtree,
// also holding track of parent node
treeNode current = t.left, parent = t;
while (current.right != null)
{
parent = current;
current = current.right;
}
// Replacing t with rightmost node
parent.right = current.left;
current.left = t.left;
current.right = t.right;
return current;
}
}
public void printReverse(){
//implement this method to print data in descending order
postorder(root);
System.out.println(" ");
}
public void display()
{
//System.out.print("Inorder: ");
preorder(root);
System.out.println(" ");
}
public void preorder(treeNode t)
{
if (t != null)
{
System.out.print(t.data+" ");
preorder(t.left);
// System.out.print(t.data+" ");
preorder(t.right);
}
}
public void postorder(treeNode t)
{
if (t != null)
{
postorder(t.left);
postorder(t.right);
System.out.print(t.data+" ");
}
}
public boolean isEmpty(){ return root==null;}
public int size(){
return sizeHelper(root);
}
private int sizeHelper(TreeNode node){
if(node==null) return 0;
else return 1+sizeHelper(node.getLeft())+sizeHelper(node.getRight());
}
public boolean search(int data){
return searchHelper(root, data);
}
private boolean searchHelper(TreeNode node, int data){
if(node==null) return false;
if(node.getData()==data) return true;
else if(node.getData()<data)
return searchHelper(node.getRight(),data);
else
return searchHelper(node.getLeft(), data);
}
public void add(int data){
root=addHelper(root, data);
}
private TreeNode addHelper(TreeNode node, int data){
if(node==null) node=new TreeNode(data);
else if(data<=node.getData()) //or call compareTo method
node.setLeft(addHelper(node.getLeft(), data));
else
node.setRight(addHelper(node.getRight(), data));
return node;
}
public void printInorder(){
printHelper(root);
}
private void printHelper(TreeNode node){
if(node!=null){
printHelper(node.getLeft());
System.out.println(node.getData());
printHelper(node.getRight());
}
}
}
public class TreeNode implements Comparable<TreeNode>{
private int data;
private TreeNode left;
private TreeNode right;
public TreeNode(int data){
this.data=data;
left=right=null;
}
public int getData(){
return data;
}
public TreeNode getLeft(){
return left;
}
public TreeNode getRight(){
return right;
}
public void setData(int data){
this.data = data;
}
public void setLeft(TreeNode left){
this.left = left;
}
public void setRight(TreeNode right){
this.right = right;
}
public int compareTo(TreeNode node){
return data-node.getData();
}
}
// Note that names may be differ go through it ... Thanks in advance....
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.