The following in the code for a binary tree in Java the add method works the fin
ID: 3558439 • Letter: T
Question
The following in the code for a binary tree in Java the add method works the find method is correct and so is the delete I bleive, but something is not working right because I am getting a java.lang.NullPointerException in main when I am trying to use the find method. If you could look over the code and tell me what I need to fix. Thank you.
public class TreeNode<g> implements Comparable<g> {
private g data = null;
private TreeNode<g> left = null;
private TreeNode<g> right = null;
private TreeNode<g> parent = null;
public TreeNode<g> getLeft() {
return (left);
}
public TreeNode<g> getRight() {
return (right);
}
public TreeNode<g> getParent() {
return (parent);
}
public g getData() {
return (data);
}
public void setLeft(TreeNode<g> x) {
left = x;
}
public void setRight(TreeNode<g> x) {
right = x;
}
public void setParent(TreeNode<g> x) {
parent = x;
}
public void setData(g x) {
data = x;
}
public int compareTo(g o) {
return 0;
}
public TreeNode<g> find (g key) {
if( ((Comparable<g>) key).compareTo( getData() ) < 0 && getLeft() != null)
return getLeft().find( key );
else if( (((Comparable<g>) key).compareTo( getData() ) > 0 && getRight() != null ))
return getRight().find(key);
else if(((Comparable<g>) key).compareTo(getData()) == 0)
return (TreeNode<g>) getData();
else
return null;
}
public boolean delete(g deleteValue) {
TreeNode<g> node2Remove, parentNode2Remove;
node2Remove = this.find(deleteValue);
// CASE1. value not in the tree
if (node2Remove == null)
return false;
// node was found! get its parent
parentNode2Remove = node2Remove.getParent();
// CASE2. node to remove is the only one in the tree
if ( node2Remove == parent
&& node2Remove.getLeft()==null
&& node2Remove.getRight()==null){
parent = null;
return true;
}
// CASE3. node to remove has no left subtree
if (node2Remove.getLeft() == null) {
// are we removing the root of the tree?
if ( node2Remove == parent) {
parent = node2Remove.getRight();
node2Remove.getRight().setParent(null);
return true;
}
// node to be deleted is NOT the root & has no left children
// must connect its parent to its right children
if (parentNode2Remove.getLeft() == node2Remove){
parentNode2Remove.setLeft(node2Remove.getRight());
}else {
parentNode2Remove.setRight(node2Remove.getRight());
}
// right child points to grandparent
node2Remove.getRight().setParent(parentNode2Remove);
return true;
} else {
// CASE4. node to be removed has a left subtree
// we must explore it and locate the nodes:
// right-most and parent-of-right-most
TreeNode<g> rightMost = node2Remove.getLeft();
TreeNode<g> rightMostParent = node2Remove;
return true;
}
}
} //END OF TREENODE CLASS
import java.util.*;
public class BinaryTree<g extends Comparable<g>> {
private TreeNode<g> root = null;
private int count = 0;
private int acount;
public void add(g newItem) {
TreeNode<g> newNode;
TreeNode<g> spot;
boolean found;
count = count + 1;
newNode = new TreeNode<g>();
newNode.setData(newItem);
if (root == null) {
root = newNode;
} else {
spot = root;
found = ((spot.getData().compareTo(newItem) > 0) && (spot.getLeft() == null))
|| ((spot.getData().compareTo(newItem) <= 0) && (spot
.getRight() == null));
while (!found) {
if (spot.getData().compareTo(newItem) > 0) {
spot = spot.getLeft();
} else {
spot = spot.getRight();
}
found = ((spot.getData().compareTo(newItem) > 0) && (spot
.getLeft() == null))
|| ((spot.getData().compareTo(newItem) <= 0) && (spot
.getRight() == null));
}
if (spot.getData().compareTo(newItem) > 0) {
spot.setLeft(newNode);
} else {
spot.setRight(newNode);
}
newNode.setParent(spot);
}
}
// these two methods are just for debugging
public void printTree() {
printme(root, 1);
}
public void printme(TreeNode<g> x, int level) {
if (x != null) {
printme(x.getLeft(), level + 1);
System.out.println("" + ((TreeNode<g>) x).getData());
printme(x.getRight(), level + 1);
} else {
}
}
// notice the toArray is not destructive like it was in the heap.
public Object[] toArray() {
Object[] ret = new Object[count];
acount = 0;
buildArray(root, ret);
return (ret);
}
public void buildArray(TreeNode<g> x, Object[] r) {
if (x != null) {
buildArray(x.getLeft(), r);
r[acount] = x.getData();
acount = acount + 1;
buildArray(x.getRight(), r);
} else {
}
}
public Object[] toArraynorecursion() {
Object[] ret = new Object[count];
Stack<TreeNode<g>> stk = new Stack<TreeNode<g>>();
TreeNode<g> x;
acount = 0;
if (root != null) {
x = root;
stk.push(x);
while (x.getLeft() != null) {
x = x.getLeft();
stk.push(x);
}
while (!stk.empty()) {
x = stk.pop();
ret[acount] = ((TreeNode<g>) x).getData();
acount = acount + 1;
if (x.getRight() != null) {
stk.push(x.getRight());
x = x.getRight();
while (x.getLeft() != null) {
x = x.getLeft();
stk.push(x);
}
} else {
}
}
} else {
}
return (ret);
}
public static <whatever extends Comparable<whatever>> void arrange() {
Object[] list = null;
int i, j, big;
Object temp;
for(i=0;i<list.length&& list[i]!=null;i++)
{
for(j=i+1;j<list.length && list[j]!=null ;j++)
{
big=i;
if (((Comparable) list[j]).compareTo (list[big])> 0){
temp = list[j];
list[j] = list[big];
list[big] = temp;
}
else {}
}
}
}
public TreeNode <g> getRoot(){
return root;
}
} //END OF BINARY TREE CLASS
import java.util.*;
public class programTest {
public static void main(String[] args) {
BinaryTree<Integer> test = new BinaryTree<Integer>();
TreeNode<Integer> node = new TreeNode<Integer>();
Random generate = new Random();
int i;
int x ;
Object[] ia;
for (i = 0; i < 11; i++) {
x = generate.nextInt(10);
test.add(x);
}
test.printTree();
System.out.print("Print out of Tree: ");
ia = test.toArray();
for (i=0;i<ia.length;i=i+1){
System.out.print(ia[i]);
}
System.out.println(" Print out is: " + node.find(6));
node.delete(6);
test.printTree();
System.out.print("Print out of Tree: ");
}
} //END OF PROGRAMTEST CLASS
Explanation / Answer
public void rotateLeft(int num){//driver
rotateLeft(root, num);
}
// Rotate the node containing val to the left -- do nothing if not possible,
private static IntNode rotateLeft(IntNode node, int number){
IntNode result = node;
if(node == null){
result = null;
}
//check if its on the left or right side
else if(number < node.getNum()){
node.setLeft(rotateLeft(node.getLeft(), number));//go left
}
else if(number > node.getNum()){
node.setRight(rotateLeft(node.getRight(), number)); //go right ERROR HERE
}
else{ //you found it
//have the result equal to number's right
result = node.getRight();
//results left point to nodes right
node.setRight(result.getLeft()); //ERROR HERE
//have result point to the number
result.setLeft(node);
}
return result;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.