Probleme beim Entfernen von BST

Question

Dies ist ein relativ großes Projekt, aber ich werde versuchen, alle notwendigen Dinge hier zu setzen.

/** 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()); 
     } 
    } 

Diese Methode hat einen Null-Zeiger-Fehler für das Elternmaterial. Ich bin mir nicht sicher, wie ich damit umgehen soll.

Dies ist ein geordnetes Wörterbuch, das in einem BST gespeichert ist. Knoten bestehen aus Datensätzen, die aus (Schlüssel, Daten) bestehen, wobei Schlüssel (Name, Typ) ist. Im Wesentlichen ist ein Record ((Name, Typ), Daten).

Ich kann bei Bedarf weitere Informationen zur Verfügung stellen. Ich bin hier für eine Weile festgefahren, jede Hilfe wird geschätzt!

Answer 1

TreeBstNode: Datenstruktur

löschen: löschen Methode

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