From: Introduction to Java Programming 9th edition: Redefine TreeNode by adding

Question

From: Introduction to Java Programming 9th edition:

Redefine TreeNode by adding a reference to a node's parent, as shown below:

BinaryTree.TreeNode

Add the following two new methods in BST:

// Returns the parent for the specified node.
public TreeNode getParent(TreeNode node)

// Returns the path from the specified node to the root in an array list
public ArrayList> getPath(TreeNode node)

Write a test program that adds numbers 1, 2, ..., 100 to the tree and displays the path for all leaf nodes

Explanation / Answer

import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Queue; import java.util.Stack; /** * Implements an unbalanced binary search tree. */ public class MyTree { Node root; /** * Construct the tree. */ public MyTree(T elem) { root = new Node(elem,null,null); } /** * Insert into the tree. * @param elem is the item to insert. * @throws IllegalArgumentException if elem is already present. */ public void add(T elem) { Node node = new Node(elem,null,null); insertNode(root,node); } /** * Internal method to insert into a subtree. * @param subTree is the subtree. * @param newNode is the new node to be inserted. * @return the new subtree. * @throws IllegalArgumentException if newNode is already present. */ private Node insertNode(Node subTree, Node newNode) { if (subTree == null) { subTree = newNode; } else if ((subTree.elem).compareTo(newNode.elem) < 0){ subTree.rightChild = insertNode(subTree.rightChild, newNode); } else if ((subTree.elem).compareTo(newNode.elem) > 0){ subTree.leftChild = insertNode(subTree.leftChild, newNode); } else { throw new IllegalArgumentException("Duplicate Element " + newNode.elem); } return subTree; } /** * Remove from the tree. * @param item is the item to remove. * @throws IllegalArgumentException if item is not found. */ public void delete(T item) { this.deleteNode(root,item); } /** * Internal method to delete a node. * @param subTree is the subtree. * @param item is the item to be deleted. * @return the new subtree. * @throws IllegalArgumentException if the item is not present. */ private Node deleteNode(Node subtree, T item) { //Search for the node first if (subtree != null) { if ((subtree.elem).compareTo(item) < 0) { subtree.rightChild = deleteNode(subtree.rightChild, item); } else if ((subtree.elem).compareTo(item) > 0) { subtree.leftChild = deleteNode(subtree.leftChild, item); } else { /* Found a match. * There are 3 possibilities: * Node is leaf: * Easy, Just delete the node but this is implicitly * handled as part of node has 1 child (see below) * Node has 1 child: * Delete the node and put the child node in its place * Node has 2 children: * Find the leftmost child in the right subtree, * replace the node to be deleted with this child. * Then delete that child node. */ if ((subtree.leftChild != null) && (subtree.rightChild != null)) { //Node has 2 children //Find the leftmost child of the right subtree and //make it the current node, then delete the //leftmost child of the right subtree Node node = findLeftmostChild(subtree.rightChild); subtree.elem = node.elem; subtree.rightChild = deleteNode(subtree.rightChild,node.elem); } else if (subtree.leftChild != null) { //Node has only 1 child i.e. left child subtree = subtree.leftChild; } else { //Node can either have no children or just have 1 right child subtree = subtree.rightChild; } } } else{ //No match throw new IllegalArgumentException("No such element"); } return subtree; } /** * Internal method to find the leftmost child. * @param subtree is the subtree. * @return the leftmost child. */ private Node findLeftmostChild(Node subtree){ assert (subtree != null); while (subtree.leftChild != null) { subtree = subtree.leftChild; } return subtree; } /** * Method to traverse the tree in depth first order. * @return the List of elements in the tree in depth first order. */ public List depthFirstTraversal() { List l = new ArrayList(); Stack s = new Stack(); s.push(root); while (!s.isEmpty()){ Node node = s.pop(); l.add(node.elem); if (node.rightChild != null) { s.push(node.rightChild); } if (node.leftChild != null) { s.push(node.leftChild); } } return l; } /** * Method to traverse the tree in breadth first order * @return the List of elements in the tree in breadth first order. */ public List breadthFirstTraversal() { List l = new ArrayList(); Queue q = new LinkedList(); q.add(root); while (!q.isEmpty()) { Node node = q.poll(); l.add(node.elem); if (node.leftChild != null) { q.add(node.leftChild); } if (node.rightChild != null) { q.add(node.rightChild); } } return l; } /** * Method to find an item in a subtree. * @param item is item to search for. * @return node containing the matched item. */ public Node findNode(T item) { if (item == null) return null; Node current = root; while ((current.elem).compareTo(item) != 0) { if ((current.elem).compareTo(item) > 0) { current = current.leftChild; } else if ((current.elem).compareTo(item) < 0) { current = current.rightChild; } if (current == null) return null; } return current; } //Test it public static void main(String[] args) { MyTree tree = new MyTree(20); tree.add(30); tree.add(10); tree.add(15); tree.add(24); tree.add(36); //tree.add(30); List l = tree.depthFirstTraversal(); System.out.println("Depth First Order"); printTree(l); l = tree.breadthFirstTraversal(); System.out.println("Breadth First Order"); printTree(l); tree.delete(30); System.out.println("Tree after deleting a node"); l = tree.depthFirstTraversal(); printTree(l); } //Method to print tree public static void printTree(List l) { for(T i: l) { System.out.println(i); } } } /** * Basic node stored in binary search trees */ class Node{ T elem; Node leftChild; Node rightChild; Node(T elem, Node left, Node right){ this.elem = elem; leftChild = left; rightChild = right; } }

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

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