时间戳

首页 > 解决方案 > 二叉搜索树搜索疑难解答

java - 二叉搜索树搜索疑难解答

问题描述

我花了大约两天的时间来解决这个问题，但我不知道缺少什么。最初我的BST使用可比较对象，然后我将其切换为 int 以在它不起作用时对其进行简化。

我将几个项目添加到树中，它成功地按顺序打印出来。然后，当我第一次调用search()方法时，它会返回 true，因为它应该如此。此后的所有其他搜索调用都返回 false，无论它是真还是假。

我在这里包含了我的大部分代码，以防问题与搜索方法本身无关。

输出应该是：4 12 23 27 30 42 60 84 true true false true true

但相反，我得到：4 12 23 27 30 42 60 84 true false false false false

public class BSTree {

    TreeNode root;
    static int comparison;

    public void insert(int value) {
        if (root == null) {
            root = new TreeNode(value);
        }
        else {
            root.insert(value);
        }
    }

    public boolean search(int chicken) {
        if (root != null ) {
            return root.search(chicken);
        }

        return false;
    }
    public static int height(TreeNode b) {
        return TreeNode.height(b);
    }

    public static void CompareSet() {
         comparison++;
    }

    public int getCompare() {
        return comparison;
    }

    public void ResetCompare() {
        comparison = 0;
    }

    public static void traverseInOrder (TreeNode node) {
        if (node != null) {
            traverseInOrder(node.left);
            System.out.print(" " + node.data);
            traverseInOrder (node.right);
        }
    }

    public static void main(String args[]) {
        BSTree tree = new BSTree();

        tree.insert(30);
        tree.insert(42);
        tree.insert(84);
        tree.insert(12);
        tree.insert(4);
        tree.insert(23);
        tree.insert(27);
        tree.insert(60);

        traverseInOrder(tree.root);
        System.out.println("\n" + tree.search(30));
        System.out.println("\n" + tree.search(4));
        System.out.println("" + tree.search(50));
        System.out.println("" + tree.search(27));
        System.out.println("" + tree.search(42));
        System.out.println(height(tree.root));

    }
}

这是treeNode类：

public class TreeNode<T> {

    int data;
    TreeNode left;
    TreeNode right;


    TreeNode(int value){
        this.data = value;
        //right = null;
        //left = null;
    }

    public void insert(int value) {
        if (value == data) {
            return;
        }

        if (value < data) {
            if (left == null) {
                left = new TreeNode(value);
            }
            else {
                left.insert(value);
            }
        }
        else {
            if (right == null) {
                right = new TreeNode(value);
        }
        else {
            right.insert(value);
        }
    }

    public boolean search(int value) {

        BSTree.CompareSet();

        if (data == value) return true;

        if (data < value && left!=null)
            return left.search(value);
        else if(data > value && right != null) 
            return right.search(value);
        return false;   
    }

    public static int height(TreeNode b) {
        if (b == null) return -1;
        return 1 + Math.max(height(b.left), height(b.right));
    }

    public int getData(){
        return data;
    }
    public TreeNode getLeftChild() {
        return left;
    }

    public void setLeftChild(TreeNode leftChild) {
        this.left = leftChild;
    }

    public TreeNode getRightChild() {
        return right;
    }

    public void setRightChild(TreeNode rightChild) {
        this.right = rightChild;
    }   
}

标签： javasearchbinary-search-tree

解决方案

您的比较是相反的:))) 这是更正后的 TreeNode::search 方法：

public boolean search(int value) {

    BSTree.CompareSet();

    if (data == value) return true;

    if (data > value && left!=null)
        return left.search(value);
    else if(data < value && right != null) 
        return right.search(value);
    return false;   
}

我认为您交换了data和value变量。

推荐阅读