LinkBack URL
About LinkBacks
Finding predecessor and successor
Program description:
Your program should read from the standard input a sequence of integer values, with each value
separated by a space. Your task is to:
• Build a binary search tree using these values in the order they are entered.
• Print 3 traversals: pre-, in-, and post-order.
• Allow the user to insert/delete a value. Once a new tree is generated, print it in-order.
• Find predecessor of a given value. The predecessor is the node that appears right before
the given value in an in-order traversal.
• Find successor of a given value. The successor is the node that appears right after the given
value in an in-order traversal.
• In your BST implementation, the add and delete methods must be implemented using
recursion. You will lose major points for using a non-recursive implementation.
• Note that no duplicates are allowed in this BST.
• Sample output in the following format:
Please enter the initial sequence of values:
51 29 68 90 36 40 22 59 44 99 77 60 27 83 15 75 3
Pre-order: X X X ... X
In-order: X X X ... X
Post-order: X X X ... X
Command? H
I Insert a value
D Delete a value
P Find predecessor
S Find successor
E Exit the program
H Display this message
Command? I 88
In-order: X X X ... X
Command? I 42
In-order: X X X ... X
Command? I 22
22 already exists, ignore.
Command? D 44
In-order: X X X ... X
Command? D 90
In-order: X X X ... X
Command? D 70
70 doesn't exist!
Command? D 68
In-order: X X X ... X
Command? S 75
77
Command? P 99
88
Command? E
Thank you for using my program!
import java.util.Scanner; public class Homework2 { private class Node { int value; Node childl, childr; private Node(int v) { value = v; childl = null; childr = null; } } Node root; private Homework2() { root = null; } private void addNode(int value) { if(search(value)!= null) { System.out.println("\n" + value + " already exists, ignored input."); return; } root = addingNode(root, value); } private Node addingNode(Node root, int value) { if (root == null) { root = new Node(value); return root; } if (value < root.value) root.childl = addingNode(root.childl, value); else if (value > root.value) root.childr = addingNode(root.childr, value); return root; } private void deleteNode(int value) { if(search(value) == null) { System.out.println("\n" + value + " does not exist, ignored input."); return; } root = deletingNode(root, value); } private Node deletingNode(Node root, int value) { if (root == null) return root; if (value < root.value) root.childl = deletingNode(root.childl, value); else if (value > root.value) root.childr = deletingNode(root.childr, value); else { if (root.childl == null) return root.childr; else if (root.childr == null) return root.childl; root.value = findSuccessor(root); root.childr = deletingNode(root.childr, root.value); } return root; } private Node search(int value) { Node node = root; while (node != null && node.value!=value) { if (value < node.value) node = node.childl; else if (value > node.value) node = node.childr; } return node; } private int findNext(int value) { Node no = search(value); return findSuccessor(no); } private int findSuccessor(Node root) { root = root.childr; int succ = root.value; while (root.childl != null) { succ = root.childl.value; root = root.childl; } return succ; } private int findPrecursor(int value) { Node no = search(value); return findPredecessor(no); } private int findPredecessor(Node root) { root = root.childl; int pre = root.value; while (root.childr != null) { pre = root.childr.value; root = root.childr; } return pre; } private void inOrder() { inOrderTraverse(root); } private void inOrderTraverse(Node root) { if (root != null) { inOrderTraverse(root.childl); System.out.print(root.value + " "); inOrderTraverse(root.childr); } } private void preOrder() { preOrderTraverse(root); } private void preOrderTraverse(Node root) { if (root != null) { System.out.print(root.value + " "); inOrderTraverse(root.childl); inOrderTraverse(root.childr); } } private void postOrder() { postOrderTraverse(root); } private void postOrderTraverse(Node root) { if (root != null) { inOrderTraverse(root.childl); inOrderTraverse(root.childr); System.out.print(root.value + " "); } } public static void main(String[] args) { Scanner key = new Scanner(System.in); String str; System.out.println("Please enter the initial sequence of values:"); str = key.nextLine(); Homework2 hw = new Homework2(); String[] s = str.split(" "); int[] arr = new int[s.length]; int i; for(i = 0; i < s.length; i++) arr[i] = Integer.parseInt(s[i]); for(int k = 0; k < i; k++) hw.addNode(arr[k]); System.out.print("Pre-Order: "); hw.preOrder(); System.out.println(); System.out.print("In-Order: "); hw.inOrder(); System.out.println(); System.out.print("Post-Order: "); hw.postOrder(); System.out.println(); String[] ar; int value; String command = "H"; while(!command.equals("E")) { char com = command.charAt(0); switch(com) { case 'I': ar = command.split(" "); value = Integer.parseInt(ar[1]); hw.addNode(value); System.out.print("In-Order: "); hw.inOrder(); System.out.println(); break; case 'D': ar = command.split(" "); value = Integer.parseInt(ar[1]); hw.deleteNode(value); System.out.print("In-Order: "); hw.inOrder(); System.out.println(); break; case 'P': ar = command.split(" "); value = Integer.parseInt(ar[1]); hw.findPrecursor(value); System.out.println(value); break; case 'S': ar = command.split(" "); value = Integer.parseInt(ar[1]); hw.findNext(value); System.out.println(value); break; case 'E': System.out.println("Thank you for using my program!"); break; case 'H': System.out.println("\n---MENU---\n"); System.out.println("I Insert a value"); System.out.println("D Delete a value"); System.out.println("P Find predecessor"); System.out.println("S Find successor"); System.out.println("E Exit the program"); System.out.println("H Display the menu"); break; default: System.out.println("Invalid input, please try again"); break; } System.out.print("\nCommand? "); command = key.nextLine(); } } }
I need help with the commands predecessor and successor, I keep getting an error:
Exception in thread "main" java.lang.NullPointerException
at Homework2.findPredecessor(Homework2.java:120)
at Homework2.findPrecursor(Homework2.java:114)
at Homework2.main(Homework2.java:236)
and
Exception in thread "main" java.lang.NullPointerException
at Homework2.findSuccessor(Homework2.java:102)
at Homework2.findNext(Homework2.java:96)
at Homework2.main(Homework2.java:243)
Can someone help?
Reply With Quote