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; 
}