在二叉搜索樹中自動刪除元素

Question

我編寫了以下代碼來實現JAVA中的二叉搜索樹。除了搜索方法外，一切看起來都很好。每個節點都有一個鍵（Item），一個字符串類型的對象以及對左右節點的引用。

class BinarySearchTree1 
    { 
    class Node // Node for BST 
    { 
    private int item; 
    private String obj; 
    private Node left; 
    private Node right; 
    Node(int Item,String Obj) 
    { 
     item = Item; 
     obj = Obj; 
     left = null; 
     right = null; 
    } 
    } 

    Node root; //Root of the BST 

    BinarySearchTree1() // Constructor 
    { 
    root = null; 
    } 

    void insert(int key,String obj) // Insertion 
    { 
    root = insertItem(root,key,obj); 
    } 
    Node insertItem(Node root,int key,String obj) 
    { 
    if(root == null) 
    { 
     root = new Node(key,obj); 
     return root; 
    } 
    else if(key>root.item) 
    root.right = insertItem(root.right,key,obj); 
    else 
    root.left = insertItem(root.left,key,obj); 
    return root; 

    } 

    void inOrder() // View Records in order 
    { 
     System.out.println("List: "); 
     inOrderRec(root); 
    } 

    void inOrderRec(Node root) 
    { 
    if(root != null) 
    { 
     inOrderRec(root.left); 
     System.out.println(root.item + " "+ root.obj); 
     inOrderRec(root.right); 
    } 
    } 

    void search(int key) // Search 
    { 
    Node Temp; 
    Temp = root; 
    Temp = searchRec(Temp,key); 
    if(Temp == null) // Element Not Found 
    { 
     System.out.println("Object for "+key+" NOT FOUND"); 
     return; 
    } 
     System.out.println("Object for "+ Temp.item+" is "+ Temp.obj); //  Element Found 
    } 

Node searchRec(Node Temp,int key) 
{ 

    if(Temp != null) 
    { 
    if(key>Temp.item) 
    { 
     Temp.right = searchRec(Temp.right,key); 
     return Temp.right; 
    } 
    if(key<Temp.item) 
    { 
     Temp.left = searchRec(Temp.left,key); 
     return Temp.left; 
    } 
    if(key==Temp.item) 
    return Temp; 
    } 
    return Temp; 
} 



public static void main(String[] args) 
    { 
     BinarySearchTree1 b1 = new BinarySearchTree1(); 
     b1.insert(6,"a"); 
     b1.insert(7,"aa"); 
     b1.insert(4,"aaa"); 
     b1.insert(1,"aaaa"); 
     b1.insert(9,"b"); 
     b1.insert(8,"bb"); 

     b1.inOrder(); 
     b1.search(9); 
     b1.search(1); 
     b1.inOrder(); 
     b1.search(8); 
     b1.search(4); 
     //System.out.println(b1.root.obj); 
    } 

} 

下面的代碼輸出：

List: 
1 aaaa 
4 aaa 
6 a 
7 aa 
8 bb 
9 b 
Object for 9 is b 
Object for 1 is aaaa 
List: 
1 aaaa 
6 a 
8 bb 
9 b 
Object for 8 is bb 
Object for 4 NOT FOUND\ 

其清楚地表明用鍵4和7的元素是不存在了。任何人都可以解釋嗎？

Answer 1

它應該是：

Node searchRec(Node Temp, int key) { 

      if (Temp != null) { 
       Node t = null; 
       if (key > Temp.item) { 
        t = searchRec(Temp.right, key); 
        return t; 
       } 
       if (key < Temp.item) { 
        t = searchRec(Temp.left, key); 
        return t; 
       } 
       if (key == Temp.item) 
        return Temp; 
      } 
      return Temp; 
     } 

你在這個方法將斷節點鏈接更新節點。

Temp.right = searchRec(Temp.right, key); // wrong 
Temp.left = searchRec(Temp.left, key); // wrong 

更新：

您可以更換：

t = searchRec(Temp.right, key); 
return t; 

與此也

return searchRec(Temp.right,key); 

左同樣的方式，這將不需要任何臨時變量。

Node searchRec(Node Temp,int key) 
    { 
     if(Temp != null) 
     { 
      if(key>Temp.item) 
      { 
       return searchRec(Temp.right,key); 
      } 
      if(key<Temp.item) 
      { 
       return searchRec(Temp.left,key); 
      } 
      if(key==Temp.item) 
       return Temp; 
     } 
     return Temp; 
    }