Using the Java Programming Language please. Redefine TreeNode by adding a refere
ID: 3767746 • Letter: U
Question
Using the Java Programming Language please.
Redefine TreeNode by adding a reference to a node’s parent, as shown below:
Implement the insert and delete methods in BST class to update the parent for each node in the tree. Add the following new method in BST:
/** Return the node for the specific element.
* Return null if the element is not in the tree. */
private TreeNode<E> getNode(E element)
/** Returns true if the node for the element is a lead */
private boolean isLeaf(E element)
/** Returns the path of the element from the specific element to the root in an array list */
public ArrayList<E> getPath(E e)
Write a test program that prompts the user to enter 10 integers, adds them to the tree, deletes the first integer from the tree, and displays the paths for all leaf nodes.
Sample run
Enter 10 integers : 45 54 67 56 50 45 23 59 23 67
[50, 54, 23]
[59, 56, 67, 54, 23]
Explanation / Answer
Given below is the code for the question
TreeNode.java
public class TreeNode<E> {
private E element;
private TreeNode<E> left;
private TreeNode<E> right;
private TreeNode<E> parent;
public TreeNode(E element, TreeNode<E> parent)
{
this(element, parent, null, null);
}
public TreeNode(E element, TreeNode<E> left, TreeNode<E> right, TreeNode<E> parent)
{
this.element = element;
this.setParent(parent);
this.setLeft(left);
this.setRight(right);
}
public void setParent(TreeNode<E> parent)
{
this.parent = parent;
}
public void setLeft(TreeNode<E> left)
{
this.left = left;
if(left != null)
this.left.setParent(this);
}
public void setRight(TreeNode<E> right)
{
this.right = right;
if(right != null)
this.right.setParent(this);
}
public void setElement(E element)
{
this.element = element;
}
public E getElement()
{
return element;
}
public TreeNode<E> getLeft()
{
return left;
}
public TreeNode<E> getRight()
{
return right;
}
public TreeNode<E> getParent()
{
return parent;
}
}
BST.java
import java.util.ArrayList;
public class BST<E extends Comparable<E>> {
private TreeNode<E> root;
public BST()
{
}
public void insert(E element)
{
if(element == null) return;
TreeNode<E> n = new TreeNode<E>(element, null);
if(root == null)
root = n;
else
{
TreeNode<E> curr = root;
while(curr != null)
{
if(element.compareTo(curr.getElement()) == 0)
return; // not inserting duplicates
else if(element.compareTo(curr.getElement()) < 0)
{
if(curr.getLeft() == null)
{
curr.setLeft(n);
break;
}
else
curr = curr.getLeft();
}
else
{
if(curr.getRight() == null)
{
curr.setRight(n);
break;
}
else
curr = curr.getRight();
}
}
}
}
/** Return the node for the specific element.
* Return null if the element is not in the tree. */
private TreeNode<E> getNode(E element)
{
if(root == null || element == null)
return null;
TreeNode<E> curr = root;
while(curr != null)
{
if(curr.getElement().compareTo(element) == 0)
break;
else if(curr.getElement().compareTo(element) > 0)
curr = curr.getLeft();
else
curr = curr.getRight();
}
return curr;
}
/** Returns true if the node for the element is a leaf */
private boolean isLeaf(E element)
{
TreeNode<E> n = getNode(element);
if(n == null || n.getLeft() != null || n.getRight() != null)
return false;
else
return true;
}
/** Returns the path of the element from the specific element to the root in an array list */
public ArrayList<E> getPath(E e)
{
ArrayList<E> path = new ArrayList<E>();
TreeNode<E> n = getNode(e);
while(n != null)
{
path.add(n.getElement());
n = n.getParent();
}
return path;
}
public void remove(E element)
{
TreeNode<E> n = getNode(element);
if(n == null)
return;
else
remove(n);
}
private void remove(TreeNode<E> n)
{
TreeNode<E> parent = n.getParent();
if(n.getLeft() == null && n.getRight() == null) //only child
{
if(parent == null) //deleting root
{
root = null;
}
else
{
if(parent.getLeft().equals(n))
parent.setLeft(null);
else
parent.setRight(null);
}
}
else if(n.getLeft() != null && n.getRight() == null) //only leftchild
{
if(parent == null) //deleting root
{
root = n.getLeft();
}
else
{
if(parent.getLeft().equals(n))
parent.setLeft(n.getLeft());
else
parent.setRight(n.getLeft());
}
}
else if(n.getLeft() == null && n.getRight() != null) //only right child
{
if(parent == null) //deleting root
{
root = n.getRight();
}
else
{
if(parent.getLeft().equals(n))
parent.setLeft(n.getRight());
else
parent.setRight(n.getRight());
}
}
else //has both the children
{
TreeNode<E> successor = successor(n);
n.setElement(successor.getElement());
remove(successor);
}
}
private TreeNode<E> successor(TreeNode<E> n)
{
if(n == null || n.getRight() == null)
return null;
TreeNode<E> succ = n.getRight();
while(succ.getLeft() != null)
succ = succ.getLeft();
return succ;
}
private void inorder(TreeNode<E> n)
{
if(n == null) return;
inorder(n.getLeft());
System.out.print(n.getElement() + " ");
inorder(n.getRight());
}
public void inorder()
{
System.out.println(" ");
inorder(root);
System.out.println();
}
public ArrayList<E> getLeaves()
{
ArrayList<E> leaves = new ArrayList<E>();
getLeaves(root, leaves);
return leaves;
}
private void getLeaves(TreeNode<E> n, ArrayList<E> leaves)
{
if(n != null)
{
if(n.getLeft() == null && n.getRight() == null)
leaves.add(n.getElement());
else
{
getLeaves(n.getLeft(), leaves);
getLeaves(n.getRight(), leaves);
}
}
}
}
BSTTest.java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class BSTTest {
public static void main(String[] args) {
Scanner keybd = new Scanner(System.in);
BST<Integer> tree = new BST<Integer>();
System.out.println("Enter 10 integers: ");
for(int i = 1; i <= 10; i++)
tree.insert(keybd.nextInt());
System.out.println("Inorder traversal of tree ");
tree.inorder();
tree.remove(45);
System.out.println("Removed 45 from tree");
System.out.println("Leaf nodes in the tree");
ArrayList<Integer> leaves = tree.getLeaves();
System.out.println(Arrays.toString(leaves.toArray()));
System.out.println("Paths to leaf nodes in the tree");
for(Integer i : leaves)
{
System.out.println("Path of " + i + ": " + Arrays.toString(tree.getPath(i).toArray()));
}
}
}
output
Enter 10 integers:
45 54 67 56 50 45 23 59 23 67
Inorder traversal of tree
23 45 50 54 56 59 67
Removed 45 from tree
Leaf nodes in the tree
[23, 59]
Paths to leaf nodes in the tree
Path of 23: [23, 50]
Path of 59: [59, 56, 67, 54, 50]
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.