在二进制搜索树中自动删除的元素

Question

我在JAVA中编写了以下用于实现二进制搜索树的代码.除搜索方法外,一切似乎都运行正常.每个节点都有一个键(Item),一个String类型的Object和一个左右节点的引用.

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

与left相同,这不需要任何临时变量.

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