二叉搜索樹刪除方法

Question

我正在製作一個二叉搜索樹，它按字符串鍵排序。每個節點由與密鑰關聯的無序鏈接信息列表組成。樹是inorder（按字母順序排列）。

我已完成大部分程序，但在刪除方法時遇到問題。

本質上它必須是遞歸的。該方法必須移除具有給定密鑰的節點，以便如果「架構」是給定的字符串，則必須遍歷樹並移除具有「架構」作爲其關鍵字的對應節點。

我有麻煩，因爲我必須刪除一個字符串。其他任務使用整數，我必須刪除最高或最低值。但是，我不會刪除具有最高或最低字符串值的節點，而是刪除等於指定字符串的節點。

我在問的是如何去做這個方法。如果您不想提供任何實際的代碼，您不必提供任何實際的代碼，但是一些指針或建議會很好。

謝謝。

//My attempt: 
//Removes node with corresponding k 
public void remove(String k) { 
    rootNode = remove(rootNode, k); 
} 

//Recursive method: 
private KeyNode remove(KeyNode x, String k) { 
    if (x == null) { 
     return x; 
    } 
    //int comparison with compareTo 
    //if less than 0, left node = remove(left node, k) 
    //if greater than 0, right node = remove(right node, k) 
    //if left node and right node are both null, return null 
    //if left node is null, return left node 
    //if right node is null, return right node 
    //return 
} 

Answer 1

你可以做這樣的事情

public rootNode remove (String k, rootNode n) { 
    if (n == null) 
     return null; 

    if (k.compareTo(n.key)<0) 
     remove (k, n.leftChild); 
    else if (k.compareTo(n.key)>0) 
     remove (k, n.rightChild); 
    else { 
     if (n.leftChild != null && n.rightChild != null) { 
      /* n has two children, find max from left then 
      * switch it with n and remove n */ 

     } 
     else if(n.leftChild != null) { 
      /* n has a left child only then left child replaces n 
      * and n is deleted */ 


     } 
     else if(n.rightChild != null) { 
      /* n has a right child only then right child replaces n 
      * and n is deleted*/ 

     } 
     else { 
      n = null; 
     } 
    } 

}