当前位置: 动力学知识库 > 问答 > 编程问答 >

java - Fetch method for BST returning null

问题描述:

I have gone over my code for most of the day, and I cannot figure out why my BST isn't populating. I have included all of the code below, however, the specific issue lies with the fetch method returning null in all cases except Will and Ted. When I invoke fetch for any list other than Will or Ted, a null is returned. I do not know if the issue lies in fetch or findNode().

package binarysearchtree;

public class SearchTree

{ TreeNode root;

public Listing compare;

public int i = 1;

public SearchTree()

{ root = null;

}

public boolean insert(Listing newListing)

{ TreeNodeWrapper p = new TreeNodeWrapper();

TreeNodeWrapper c = new TreeNodeWrapper();

TreeNode n = new TreeNode();

compare = newListing;

if(n == null)// out of memory

return false;

else // insert the node

{ n.node = newListing.deepCopy(); // fill in the TreeNode's fields

n.lc = null;

n.rc = null;

if(root == null) // tree is empty

{ root = n; }

else

{ findNode(newListing.getKey(), p, c); // find the node's parent

if(newListing.getKey().compareTo(p.get().node.getKey()) < 0)

p.get().lc = n; // insert new node as a left child

else

p.get().rc = n; // insert new node as a right child

}

return true;

}

} // end insert method

public Listing fetch(String targetKey)

{ boolean found;

TreeNodeWrapper p = new TreeNodeWrapper();

TreeNodeWrapper c = new TreeNodeWrapper();

found = findNode(targetKey, p, c); // locate the node

if(found == true)

return c.get().node.deepCopy();

else

return null;

} // end of fetch method

public boolean delete(String targetKey)

{ boolean found;

TreeNodeWrapper p = new TreeNodeWrapper();

TreeNodeWrapper c = new TreeNodeWrapper();

TreeNode largest;

TreeNode nextLargest;

found = findNode(targetKey, p, c);

if(found == false) // node not found

return false;

else // identify the case number

{ if(c.get().lc == null && c.get().rc == null) // case 1: deleted

// node has no

// children

{ if(p.get().lc == c.get()) // deleted node is a left child

p.get().lc = null;

else // deleted node is a right child

p.get().rc = null;

} // end case 1

else if(c.get().lc == null || c.get().rc == null) // case 2:

// 1 child

{ if(p.get().lc == c.get()) // deleted node is a left child

{ if(c.get().lc != null) // deleted node has a left child

p.get().lc = c.get().lc;

else

p.get().lc = c.get().rc;

}

else // deleted node is a right child

{ if(c.get().lc != null) // deleted node has a left child

p.get().rc = c.get().lc;

else

p.get().rc = c.get().rc;

}

} // end case 2

else // case 3: deleted node has two children

{ nextLargest = c.get().lc;

largest = nextLargest.rc;

if(largest != null) // left child has a right subtree

{ while(largest.rc != null) // move down right subtree

{ nextLargest = largest;

largest = largest.rc;

}

c.get().node = largest.node; // overwrite deleted node

nextLargest.rc = largest.lc; // save the left subtree

}

else // left child does not have a right subtree

{ nextLargest.rc = c.get().rc; // save the right subtree

if(p.get().lc == c.get()) // deleted node is a left child

p.get().lc = nextLargest; // jump around deleted node

else // deleted node is a right child

p.get().rc = nextLargest; // jump around deleted node

}

} // end of case 3

return true;

}

} // end of delete method

public boolean update(String targetKey, Listing newListing)

{ if(delete(targetKey) == false)

return false;

else if(insert(newListing) == false)

return false;

return true;

} // end of update

public class TreeNode

{ private Listing node;

private TreeNode lc;

private TreeNode rc;

public TreeNode()

{

}

} // end of class TreeNode

private boolean findNode(String targetKey, TreeNodeWrapper parent,

TreeNodeWrapper child)

{ parent.set(root);

child.set(root);

if(root == null) // tree is empty

return true;

while(child.get() != null)

{

if(child.get().node.compareTo(targetKey) == 0){ // node found

System.out.print("We finally found one!!!!!\n");

return true;

}

else

{ parent.set(child.get());

if(targetKey.compareTo(child.get().node.getKey()) > 0) {

System.out.print(child.get().node.getKey() + "\n");

child.set(child.get().lc);

}

else {

System.out.print(child.get().node.getKey() + "\n");

child.set(child.get().rc);

}

}

} // end while

return false;

} // end of findNode

public class TreeNodeWrapper

{ TreeNode treeRef = null;

public TreeNodeWrapper()

{

}

public TreeNode get()

{ return treeRef;

}

public void set(TreeNode t)

{ treeRef = t;

}

} // end of class TreeNodeWrapper

} // end class BinaryTree

The class "Listing"

package binarysearchtree;

public class Listing

{ private String name; // key field

private String address;

private String number;

public Listing(String n, String a, String num)

{ name = n;

address = a;

number = num;

}

public String toString()

{ return("Name is " + name +

"\nAddress is " + address +

"\nNumber is " + number + "\n");

}

public Listing deepCopy()

{ Listing clone = new Listing(name, address, number);

return clone;

}

public int compareTo(String targetKey)

{ return(name.compareTo(targetKey));

}

public void setAddress(String a) // coded to demonstrate

// encapsulation

{ address = a;

} // end of setAddress method

public String getKey()

{

return name;

}

} // end of class Listing

and finally my main method:

package binarysearchtree;

import binarysearchtree.BinaryTree.TreeNode;

public class BinarySearchTree {

public static void main(String[] args) {

SearchTree t = new SearchTree();

Listing l;

Listing l1 = new Listing("Ann", "1st Avenue", "111 1111");

Listing l2 = new Listing("Bill", "2nd Avenue", "222 2222");

Listing l3 = new Listing("Carol", "3rd Avenue", "333 3333");

Listing l4 = new Listing("Mike", "4th Avenue", "444 4444");

Listing l5 = new Listing("Pat", "5th Avenue", "555 5555");

Listing l6 = new Listing("Sally", "6th Avenue", "666 6666");

Listing l7 = new Listing("Ted", "7th Avenue", "777 7777");

Listing l8 = new Listing("Vick", "8th Avenue", "888 8888");

Listing l9 = new Listing("Will", "9th Avenue", "999 9999");

Listing l10 = new Listing("Zack", "11th Avenue", "101 0101");

Listing l11 = new Listing("Zeek", "12th Avenue", "121 2121");

//insert nodes

t.insert(l9);

t.insert(l7);

t.insert(l10);

t.insert(l2);

t.insert(l8);

t.insert(l1);

t.insert(l4);

t.insert(l3);

t.insert(l6);

t.insert(l5);

//fetch nodes

System.out.println(t.fetch("Carol"));

System.out.println(t.fetch("Sally"));

System.out.println(t.fetch("Ted"));

// delete nodes

t.delete("Carol"); // a node with NO children

System.out.println(t.fetch("Carol"));

t.delete("Sally"); // a node with ONE child

System.out.println(t.fetch("Sally"));

t.delete("Ted"); // a node with TWO children

System.out.println(t.fetch("Ted"));

// update nodes

t.update("Bill", l3);

System.out.println(t.fetch("Carol"));

System.out.println(t.fetch("Bill"));

System.out.print(l1.getKey());

System.exit(0);

}

}

分享给朋友:
您可能感兴趣的文章:
随机阅读: