無法從BST中刪除

Question

這是一個相對較大的項目，但我會盡力在這裏提供所有必要的東西。

/** Removes the record with Key k from the dictionary. It throws a 
    DictionaryException if the record is not in the dictionary. */ 

public void remove(Key k) throws DictionaryException{ 

     deleteNode = findNode(k); 
     if (deleteNode == null) throw new DictionaryException("Error: Record doesn't exist in the dictionary!"); 
     else{ 
      //check if children are leafs 
      if(deleteNode.getLeftChild() == null || deleteNode.getRightChild() == null) 
       //set it to itself 
       replace = deleteNode; 
      else 
       //otherwise replace with successorNode 
       replace = successorNode(deleteNode); 
      //store left child if it exists 
      if (replace.getLeftChild() != null) 
       child = replace.getLeftChild(); 
      //else, store right 
      else 
       child = replace.getRightChild(); 
      //check if both nodes are null 
      if (child != null) 
       child.setParent(replace.getParent()); 
      //else replace the node that needs to be deleted 
      else{ 
       //replace left child of parent 
       if(replace == replace.getParent().getLeftChild()) 
        replace.getParent().setLeftChild(child); 
       //else replace right 
       else 
        replace.getParent().setRightChild(child); 
      } 
      //store information of the replacing node, within the deleteNode 
      if (replace != deleteNode) 
       deleteNode.setRoot(replace.getRecord()); 
     } 
    } 

此方法在父項目上有一個空指針錯誤。 我不知道如何去處理它。

這是存儲在BST中的有序字典。節點由包含（密鑰，數據）的記錄組成，其中密鑰是（名稱，類型）。本質上記錄是（（姓名，類型），數據）。

如有必要，我可以提供更多信息。我一直在這裏呆了一段時間，任何幫助表示讚賞！

Answer 1

TreeBstNode：數據結構

刪除：刪除方法

public class TreeBst { 

/** 
* The Class TreeBstNode. 
*/ 
private class TreeBstNode { 

    /** The data. */ 
    int data; 

    /** The l child. */ 
    TreeBstNode lChild; 

    /** The r child. */ 
    TreeBstNode rChild; 

    /** The parent. */ 
    TreeBstNode parent; 

    /** 
    * Instantiates a new tree node. 
    */ 
    TreeBstNode() { 
     this(0, null, null, null); 
    } 

    /** 
    * Instantiates a new tree node. 
    * 
    * @param data 
    *   the data 
    * @param rChild 
    *   the r child 
    * @param lChild 
    *   the l child 
    * @param parent 
    *   the parent 
    */ 
    /** 
    * @param data 
    * @param rChild 
    * @param lChild 
    * @param parent 
    */ 
    TreeBstNode(int data, TreeBstNode rChild, TreeBstNode lChild, 
      TreeBstNode parent) { 

     this.data = data; 
     this.rChild = rChild; 
     this.lChild = lChild; 
     this.parent = parent; 
    } 

} 

/** The root. */ 
private TreeBstNode root; 

/** 
* Instantiates a new tree bst. 
*/ 
public TreeBst() { 
    root = null; 
} 

/** 
* Instantiates a new tree bst. 
* 
* @param x 
*   the x 
*/ 
public TreeBst(int x) { 
    root = new TreeBstNode(x, null, null, null); 
} 
/** 
* Delete. 
* 
* @param x 
*   the x 
* @return the tree node 
*/ 
public TreeBstNode delete(int x) { 
    return BST_Delete(root, x); 
} 
    /** 
* BS t_ delete. 
* 
* @param t 
*   the t 
* @param x 
*   the x 
* @return the tree node 
*/ 
private TreeBstNode BST_Delete(TreeBstNode t, int x) { 
    // TODO Auto-generated method stub 
    if (t == null) { 
     return null; 
    } else if (x < t.data) { 
     BST_Delete(t.lChild, x); 
    } else if (x > t.data) { 
     BST_Delete(t.rChild, x); 
    } else { 
     return BST_DeleteItem(t); 
    } 
    return null; 
} 

/** 
* BS t_ delete item. 
* 
* @param t 
*   the t 
* @return the tree node 
*/ 
private TreeBstNode BST_DeleteItem(TreeBstNode t) { 
    // TODO Auto-generated method stub 
    TreeBstNode temp = t; 
    TreeBstNode returnTree = null; 
    if (t.lChild == null && t.rChild == null) { 

     if (t.parent != null) { 

      if (t.parent.lChild == t) { 
       returnTree = t.parent.lChild; 
       t.parent.lChild = null; 
      } else { 
       returnTree = t.parent.rChild; 
       t.parent.rChild = null; 
      } 
     } else { 
      returnTree = root; 
      root = null; 

     } 

    } else if (t.lChild == null) { 
     t = t.rChild; 
    } else if (t.rChild == null) { 
     t = t.lChild; 
    } else { 
     temp = t.lChild; 
     while (t.rChild != null) { 
      temp = temp.rChild; 
     } 
     t.data = temp.data; 
     BST_Delete(t.lChild, temp.data); 
    } 
    return returnTree; 
}