クラスのバイナリ検索ツリーに取り組んでおり、コードのほとんどを正しく実装しています (と思います) が、ルート ノードを削除しようとしても何も起こりません。
私のコードに問題がある人はいますか?
public class BinarySearchTree {
private Node root;
private int size = 0;
public BinarySearchTree(){
root = null;
}
public BinarySearchTree create(){
BinarySearchTree tree = new BinarySearchTree();
return tree;
}
public int size(){
return size;
}
public Node getRoot(){
System.out.println("root: " + root.getData());
return root;
}
public void insert(String s){
root = insertHelper(root, s.toLowerCase());
size++;
}
private Node insertHelper(Node n, String s){
if(n == null){
//root is null, make it a new node
n = new Node(s);
} else if(s.compareTo(n.getData()) < 0){
//string is alphabetically less than root
n.setLeft(insertHelper(n.getLeft(), s));
n.getLeft().setParent(n);
} else{
//string is alphabetically greater than root
n.setRight(insertHelper(n.getRight(), s));
n.getRight().setParent(n);
}
return n;
}
public void delete(String s){
deleteHelper(root, s.toLowerCase());
}
private void deleteHelper(Node n, String s){
if(n == null){
//nothing to delete
return;
}
//found node to delete
else if(s.equals(n.getData())){
System.out.println("DELETED: " + n.getData());
//check for left subtree
//if null, replace node-to-be-deleted with
//right subtree
if(n.getLeft() == null){
replace(n, n.getRight());
}
//check for right subtree
//if null, replace node-to-be-deleted with
//left subtree
else if(n.getRight() == null){
replace(n, n.getLeft());
}
//if it has two subtrees, find minimum value of the
//right tree and swap the node-to-be-deleted's data with
//the minimum node's data
else{
Node min = n.getRight();
while(min.getLeft() != null){
min = min.getLeft();
}
//replace with right and reset pointers
if(min.getParent() != n){
replace(min, min.getRight());
min.setRight(n.getRight());
min.getRight().setParent(min);
}
//replace with left and reset pointers
else{
replace(n, min);
min.setLeft(n.getLeft());
min.getLeft().setParent(min);
}
}
}
//if it hasn't been found, recurse left
else if(s.compareTo(n.getData()) < 0){
deleteHelper(n.getLeft(), s);
}
//then, recurse right
else{
deleteHelper(n.getRight(), s);
}
}
private void replace(Node x, Node y){
//if x is the root, set root to y
if(x.getParent() == null){
root = y;
}
//if x is a left child, set it's parent's left child to y
else if(x == x.getParent().getLeft()){
x.getParent().setLeft(y);
}
//if x is a right child, set it's parent's right child to y
else{
x.getParent().setRight(y);
}
//if y is not null, set y's parent to be x's parent
if(y != null){
y.setParent(x.getParent());
}
}
public void destroy(){
//wipe out the tree
root = null;
size = 0;
}
public boolean find(String s){
return findHelper(root, s.toLowerCase());
}
public boolean findHelper(Node n, String s){
if(n == null){
System.out.println("Sorry, " + s + " is not in here.");
return false;
}
if(s.equals(n.getData())){
System.out.println(s + " is in the tree.");
return true;
} else if(s.compareTo(n.getData()) < 0){
return findHelper(n.getLeft(), s);
} else{
return findHelper(n.getRight(), s);
}
}
}
public class SearchDriver {
/**
* @param args
*/
public static void main(String[] args) {
SearchDriver me = new SearchDriver();
me.doIt();
}
public void doIt(){
BinarySearchTree tree = new BinarySearchTree();
tree.insert("marry");
tree.insert("alpha");
tree.insert("gamma");
tree.insert("delta");
tree.insert("epsilon");
tree.insert("zeta");
tree.insert("eta");
tree.insert("theta");
tree.insert("iota");
tree.insert("kappa");
tree.insert("lambda");
tree.insert("beta");
tree.insert("nu");
tree.insert("xi");
tree.insert("omicron");
tree.insert("pi");
tree.insert("rho");
tree.insert("sigma");
tree.insert("tau");
tree.insert("upsilon");
tree.insert("phi");
tree.insert("chi");
tree.insert("psi");
tree.insert("omega");
tree.printInOrder();
tree.delete("psi");
tree.printInOrder();
tree.delete("marry");
tree.printInOrder();
tree.printPostOrder();
}
}