BST find()方法仅在找到节点时才返回true

Question

我目前正在尝试实现一个二进制搜索树，到目前为止，我唯一的大问题是find()方法，因为我有一个问题，当我寻找一个不在我的树中的键时，我得不到任何答案……这是我到目前为止的代码：

public class Bst {

Node root;
Node head;
Node tail;


public Bst(){
    root = null;
}

public void insert (Node root, int key){
    Node newNode=new Node(key);

    if(root==null){
        root=newNode;
    }

    if(key<=root.getKey()){
        if (root.getLeft()!=null){
            insert(root.getLeft(), key);
        }
        else{
            root.setLeft(newNode);
        }
    }

    if (key>=root.getKey()){
        if (root.getRight()!=null){
            insert(root.getRight(),key);
        }

        else{
            root.setRight(newNode);
        }

    }


    }

public void printTree(Node root){
    if (root==null) return;
    printTree(root.getLeft());
    System.out.print(root.getKey() + " ");
    printTree(root.getRight());
}

public Node treeToCDLL(Node root){
    if (root == null){
        return null;
    }

    Node leftTree=treeToCDLL(root.getLeft());
    Node rightTree=treeToCDLL(root.getRight());


    if (leftTree == null){
        head=root;
    }

    else {
        head=leftTree;
        leftTree.getLeft().setRight(root);
        root.setLeft(leftTree.getLeft());
    }

    if (rightTree==null){
        head.setLeft(root);
        root.setRight(head);
        tail=root;
    }

    else{
        tail=rightTree.getLeft();
        head.setLeft(tail);
        tail.setRight(head);
        root.setRight(rightTree);
        rightTree.setLeft(root);
    }

    return head;
}

public boolean find(Node root, int key){
    Node current=root;

    while(current!=null){

        if(current.getKey()==key){
            return true;
        }
        else if(current.getKey()>key){
            current=current.getLeft();
        }

        else
            current=current.getRight();
        }
    return false;
}

public void printList(Node head){
    Node current = head;

    while(current!=null){
        System.out.print(current.getKey() + " ");
        current=current.getRight();
        if(current==head) break;
    }
}
public static void main (String[]args){

    Bst bst=new Bst();

    Node root=new Node(4);
    bst.insert(root, 2);
    bst.insert(root, 1);
    bst.insert(root, 3);
    bst.insert(root, 5);
    bst.insert(root, 6);

    System.out.print("in-order traversal: ");
    bst.printTree(root);
    System.out.println();



    System.out.print("circular doubly linked list: ");
    Node head= bst.treeToCDLL(root);
    bst.printList(head);
    System.out.println();
    System.out.print("Der gesuchte Knoten : " + bst.find(root,6));







}

}

我真的很高兴，如果你能帮助我，因为我尝试了很多方法，看起来我只有在寻找树中存在的密钥时才能得到答案

Answer 1

在调用find()之前，您正在将BST转换为循环双向链表。根据定义，这将永远进行搜索(如果节点不存在)，除非您标记您访问过的节点。

Answer 2

您的find()方法看起来不错。我看到的一个问题是，您正在通过调用以下方法将BST转换为循环链表

 Node head= bst.treeToCDLL(root);

在调用find()之前，这就是为什么你的程序会进入无限循环。

在调用bst.treeTOCDLL(root)之前尝试find(7)，它会给出false。