Assignment 9 Parent reference for BST Redefine TreeNode by a

Assignment 9 (Parent reference for BST) Redefine TreeNode by adding a reference to a node’s parent, as shown below:

BST.TreeNode

#element

#left : TreeNode

#right: TreeNode

#parent: TreeNode

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 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 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]

Solution

import java.util.NoSuchElementException; public class TreeSet> implements Set { private TreeNode root; private int size; // Constructs an empty set. public TreeSet() { root = null; size = 0; } // Adds the given value to this set, if it was not already in the set. // If the element is already a member of this set, adding it again has no effect. public void add(E value) { root = add(root, value); } // private recursive helper for add // uses the \"x = change(x)\" pattern: // pass in current state of root // return out desired new state of root private TreeNode add(TreeNode node, E value) { if (node == null) { node = new TreeNode(value); // reached dead end; put new node here size++; } else if (value.compareTo(node.data) > 0) { node.right = add(node.right, value); } else if (value.compareTo(node.data) < 0) { node.left = add(node.left, value); } // else a duplicate; do nothing return node; } // Returns true if this set contains the given element value. public boolean contains(E value) { return contains(root, value); } // private recursive helper for contains private boolean contains(TreeNode node, E value) { if (node == null) { return false; } else if (value.compareTo(node.data) > 0) { return contains(node.right, value); } else if (value.compareTo(node.data) < 0) { return contains(node.left, value); } else { // value.equals(root.data); found it! return true; } } // Returns the minimum value in this set. // Throws a NoSuchElementException if this set is empty. public E getMin() { if (root == null) { throw new NoSuchElementException(\"empty tree\"); } return getMin(root); } // private recursive helper for getMin private E getMin(TreeNode node) { if (node.left == null) { return node.data; } else { return getMin(node.left); } } // Returns true if this set does not contain any elements. public boolean isEmpty() { return size == 0; } // Prints all elements of this tree in a left-to-right order (in-order) traversal. public void print() { print(root); } // private recursive helper for print private void print(TreeNode node) { if (node != null) { print(node.left); System.out.print(node.data + \" \"); print(node.right); } // implicit base case: else do nothing } // Removes the given value from this set, if it is found in this set. // If the element is not found, calling this method has no effect. public void remove(E value) { root = remove(root, value); } // private recursive helper for remove private TreeNode remove(TreeNode node, E value) { if (node == null) { // nothing here; do nothing? } else if (value.compareTo(node.data) < 0) { node.left = remove(node.left, value); } else if (value.compareTo(node.data) > 0) { node.right = remove(node.right, value); } else { // (value == root.data) // found it! remove now. size--; if (node.left == null && node.right == null) { // leaf node = null; } else if (node.right == null) { // only left child node = node.left; } else if (node.left == null) { // only right child node = node.right; } else { // hard case: two children; replace me with min from my right E rightMin = getMin(node.right); node.right = remove(node.right, rightMin); node.data = rightMin; } } return node; } // Returns the number of elements in this set. public int size() { return size; } // Each TreeNode object stores a single node of a binary tree. // The class has just public data fields and constructors. // This version of our code places the node as an inner class. private class TreeNode { public E data; // data stored at this node public TreeNode left; // reference to left subtree public TreeNode right; // reference to right subtree // Constructs a leaf node with the given data. public TreeNode(E data) { this(data, null, null); } // Constructs a leaf or branch node with the given data and links. public TreeNode(E data, TreeNode left, TreeNode right) { this.data = data; this.left = left; this.right = right; } } }