java - 树搜索功能没有给出预期的结果

Question

我想知道为什么我在这段代码中使用方法 containsData 和 containsData2 得到相同的结果。

package rr.fe.op.lab.proc;

class TreeNode {
    TreeNode left;
    TreeNode right;
    String data;
}

class TreeProgram {
    public static void main(String[] args) {
        TreeNode node = null;
        node = insert(node, "Han");
        node = insert(node, "Luke");
        node = insert(node, "Leia");
        node = insert(node, "Padme");
        node = insert(node, "Vader");
        node = insert(node, "Yoda");

        System.out.println("Writing tree inorder:");
        writeTree(node);

        node = reverseTreeOrder(node);
        System.out.println("Writing reversed tree inorder:");

        writeTree(node);
        int size = sizeOfTree(node);
        System.out.println("Number of nodes in tree is "+size+".");

        boolean found = containsData(node, "Padme");
        System.out.println("Searched element is found: "+found);

        boolean found1 = containsData2(node, "Padme");
        System.out.println("Searched element is found: "+found);
    }

    static boolean containsData(TreeNode treeRoot, String data) {
        if(treeRoot == null)
            return false;
        else if(data.compareTo(treeRoot.data) == 0)
        return true;
        else if(data.compareTo(treeRoot.data) < 1)
            return containsData(treeRoot.left,data);
        else 
            return containsData(treeRoot.right,data);
    }

    static int sizeOfTree(TreeNode treeRoot) {
        if(treeRoot == null)
            return 0;
        else 
            return 1 + sizeOfTree(treeRoot.right) + sizeOfTree(treeRoot.left);
    }

    static TreeNode insert(TreeNode treeRoot, String data) {
        if(treeRoot == null){
            TreeNode newnode = new TreeNode();
            newnode.data = data;
            newnode.left = null;
            newnode.right = null;
            return newnode;
        }
        else if (data.compareTo(treeRoot.data) < 1)
            treeRoot.left = insert(treeRoot.left,data);
        else 
            treeRoot.right = insert(treeRoot.right,data);
        return treeRoot;
    }

    static void writeTree(TreeNode treeRoot) {
        if(treeRoot != null){
            writeTree(treeRoot.left);
            System.out.println(treeRoot.data);
            writeTree(treeRoot.right);
        }
    }

    static TreeNode reverseTreeOrder(TreeNode treeRoot) {
        if(treeRoot == null)
            return null;

        TreeNode node = new TreeNode();
        node = treeRoot.left;
        treeRoot.left = treeRoot.right;
        treeRoot.right = node;

        reverseTreeOrder(treeRoot.left);
        reverseTreeOrder(treeRoot.right);
        return treeRoot;
    }

    static boolean containsData2(TreeNode treeRoot,String data){
        if (treeRoot == null) {
            return false;
        }

        if (treeRoot.data == data){
            return true;
        } else {
            return containsData2(treeRoot.left,data) || containsData2(treeRoot.right,data);
        }

    }  
}

我知道在反转树之前，方法 containsData 工作正常。当我倒转树时，它不起作用，这没关系。我写了一个方法 containsData2 的想法是无论树是否反转，该方法都可以找到元素。当然，复杂度会更高。但是，对于 containsData2，我得到与 containsData 相同的结果，即 false。我做错了什么？

Answer 1

主要问题是您在打印语句中放置了错误的变量:

boolean found1 = containsData2(node, "Padme");
System.out.println("Searched element is found: "+found);

这应该是:

boolean found1 = containsData2(node, "Padme");
System.out.println("Searched element is found: "+found1);

另一个重要的问题是您尝试使用 == 比较字符串，这通常不会给出您想要的结果。在这种特殊情况下它有效，因为您只使用文字字符串。比较在这里完成:

if (treeRoot.data == data){
    return true;
} else {
    return containsData2(treeRoot.left,data) || containsData2(treeRoot.right,data);
}

相反，使用 equals 方法比较您的字符串，如下所示:

if (treeRoot.data.equals(data)){
    return true;
} else {
    return containsData2(treeRoot.left,data) || containsData2(treeRoot.right,data);
}

或者，如果您想进一步简化代码:

return treeRoot.data.equals(data) ||
       containsData2(treeRoot.left,data) || containsData2(treeRoot.right,data);

有关比较字符串的更多信息，请参阅 this question .