java - BST 中的搜索操作

Question

这是我使用 java 搜索元素的代码，即二叉搜索树。 当我执行搜索方法两次时，第二个元素的输出显示为 false。就像树中存在 10 一样，该元素也显示为 false。 代码太长，我不得不删除中序遍历和插入元素方法。

public class BinarySearchTree {
    class Node {
        int data;
        Node left, right;

        public Node(int item) {
            data = item;
            left = right = null;
        }
    }

    Node root;

    BinarySearchTree() {
        root = null;
    }

    // search data method

    boolean search(int data) {
        root = searchData(root, data);
        if (root != null) {
            return true;
        }
        return false;
    }

    Node searchData(Node root, int data) {
        if (root == null) {
            return null;
        }

        if (data == root.data) {
            return root;
        } else if (data < root.data) {
            return searchData(root.left, data);
        } else {
            return searchData(root.right, data);
        }
    }

    
    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        bst.insert(60);
        bst.insert(30);
        bst.insert(10);
        
        System.out.println("Number found : " + bst.search(60));
        System.out.println("Number found : " + bst.search(10));

    }
}

上述代码的控制台输出:- 发现数量:真实 找到的数量:错误

Answer 1

在方法search中，您重新分配行中的root值

root = searchData(root, data);

为了避免这种情况，请将此行更改为

Node root = searchData(this.root, data);

创建新变量，而不是更改对象字段。
或者将您的方法更改为

boolean search(int data) {
    return searchData(root, data) != null;
}