(Parent reference for BST) Redefine TreeNode by adding a reference to a node’s p
ID: 3861113 • Letter: #
Question
(Parent reference for BST) Redefine TreeNode by adding a reference to a node’s parent, as shown below:
BST.TreeNode<E>
#element: E
#left: TreeNode<E>
#right: TreeNode<E>
#parent: TreeNode<E>
Reimplement the insert and delete methods in the BST class to update the parent for each node in the tree. Add the following new method in BST:
/** Returns the node for the specified element.
* Returns 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 leaf */
private boolean isLeaf(E element)
/** Returns the path of elements from the specified 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
package bstparent;
import java.util.*;
class element {
element left, right, parent;
int data;
// constructor with no parameter
public element () {
left = null;
right = null;
parent = null;
data = 0;
} // end no param constructor
// constructor with data as parameter
public element(int d1) {
data = d1;
}
public element(int d1, element leftNode, element rightNode, element parentNode) {
left = leftNode;
right = rightNode;
parent = parentNode;
data = d1;
} // end one param constructor
// function to display the left node
public void dispLeft() {
if ( left != null)
System.out.print(left.data + " , ");
} // end func disp left
// function to display the right node
public void dispRight() {
if ( right != null )
System.out.print(right.data + " , ");
} // end func disp right
} // end class element
class tree {
public element rootNode;
public tree() {
rootNode = null;
} // end constructor
public void addData(int d1) {
rootNode = addData(rootNode, d1);
} // end func one param addData
public element addData(element presentNode , int d1) { // recursive node addition into the tree
if ( presentNode == null )
presentNode = new element(d1);
else {
if ( d1 <= presentNode.data) presentNode.left = addData(presentNode.left, d1);
else presentNode.right = addData(presentNode.right, d1);
} // end else
return presentNode;
} // end func addData
} // end class tree
public class BSTParent {
public static void main(String[] args) {
tree objTree = new tree();
element objElem = new element();
objTree.addData(45);
objTree.addData(objElem, 54);
objTree.addData(objElem, 67);
objTree.addData(objElem, 56);
objTree.addData(objElem, 50);
objTree.addData(objElem, 45);
objTree.addData(objElem, 23);
objTree.addData(objElem, 59);
objTree.addData(objElem, 23);
objTree.addData(objElem, 67);
objElem.dispLeft();
objElem.dispRight();
} // end main
} // end public class
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.