java - 在未排序的二叉树中搜索字符串

Question

我不确定需要做什么来搜索存储在二叉树中的字符串。我已经写了搜索方法，但我不太明白要传递什么。我需要先搜索该字符串，然后再将其添加到树中。如果找到，我只需要增加节点对象内的计数器，而不是添加新的计数器。顺便说一下，这棵树没有排序。

我的问题是在添加之前如何搜索它？

System.out.println("Enter string to be stored");
stringValue = k.nextLine();
if (theString.isEmpty() == true) {
    node.add(stringValue, count);
} else {
    // I am not sure what to do here
    // How do I send the string to my search method?
    stringValue.treeSearch();
}

<小时/>

public Node treeSearch(String s, TreeNode root){

    if(root.toString().equals(s)){

        return root;
    }
    if(left != null){

        left.treeSearch(s, root.left);
        if(root.toString().equals(s)){
            return root;
        }
    }
    if(right != null){

        right.treeSearch(s, root.right);
        if(root.toString().equals(s)){
            return root;
        }
    }else{
          return null;
            }
}

<小时/>

我将搜索方法更新为此。

 public Node treeSearch(String s, Node root){

 if(root.toString().equals(s)){

    return root;
    }
    if(left != null){

       left.treeSearch(s, root.left);
       return root;
    }
    if(right != null){

      right.treeSearch(s, root.right);
          return root;
    }else{
         return null;
    }
}

Answer 1

搜索左右子树的方式存在错误。例如:

if (left != null) {
    left.treeSearch(s, root.left);
    if (root.toString().equals(s)) {
        return root;
    }
}

所以...您搜索左子树，但忽略搜索结果并再次将 s 与 root ...进行比较。

右子树重复相同的模式。

(因为这听起来像是一个“学习练习”，所以我会让你自己找出解决办法。)

<小时/>

话虽如此，如果你不对二叉树的元素进行排序，那么它作为一种数据结构几乎毫无用处。最好将元素存储在列表或数组中。 (treeSearch 的复杂度是 O(N) ...就像搜索列表或数组一样。)