二叉搜索树中的元素被自动删除

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

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

二叉搜索树中的元素被自动删除

Elements getting automatically deleted in a Binary Search Tree

java

binary-search-tree

data-structures