java - 字符串二叉搜索树

Question

我的二叉搜索树遇到问题。添加所有字符串值后，我可以搜索之前搜索过的内容。但是，它无法检索存储在tree.right(或tree.left)中的值。即使我的tree.right有值，但是当我搜索它时，它会返回“Record Not Found”。输出和代码如下所示:

  public void add(String value) {  
      if(value.toLowerCase().equals("red") || value.toLowerCase().equals("green")  || value.toLowerCase().equals("blue") || 
            value.toLowerCase().equals("yellow") || value.toLowerCase().equals("black")) {
         if (root == null) {
            root = new StringTreeNode(value.toLowerCase());
            size ++;
        }
        else
            addleaf(root, value.toLowerCase());
    }

}


public void addleaf(StringTreeNode branch, String value) {
    if(value.compareTo(branch.data) < 0) {
        if (branch.left == null) {
            branch.left = new StringTreeNode(value);
            size ++;
        } else
            addleaf(branch.left, value);
    } else if (value.compareTo(branch.data) > 0) {
        if (branch.right == null) {
            branch.right = new StringTreeNode(value);
            size ++;
        } else
            addleaf(branch.right, value);
    } else {

    } 
}

public void searchNode (String value) {
    found = false;
    if(root == null)
        System.out.println("Nothing here");
    else
        searchBranch(root, value.toLowerCase());
    if (!found)
        System.out.println("Records not found.");
}


public void searchBranch (StringTreeNode tmp, String value) {
        if(value.equals(tmp.data)) {
            System.out.println("Records found, " + value + " exist in search history!");
            found = true;
        } else if (tmp.left != null)
            searchBranch(tmp.left, value);
        else if (tmp.right != null)
            searchBranch(tmp.right, value);
}

输出

What do you want to search?(0 to exit) : red

What do you want to search?(0 to exit) : green

What do you want to search?(0 to exit) : blue

What do you want to search?(0 to exit) : yellow

What do you want to search?(0 to exit) : black

What do you want to search?(0 to exit) : 0

Tree Value : red green blue black yellow

Stack Value : 1. black 2. yellow 3. blue 4. green 5. red

What do you want to search for the existence history?(0 to exit) : red

Records found, red exist in search history!

What do you want to search for the existence history?(0 to exit) : green

Records found, green exist in search history!

What do you want to search for the existence history?(0 to exit) : blue

Records found, blue exist in search history!

**What do you want to search for the existence history?(0 to exit) : yellow

Records not found.**

What do you want to search for the existence history?(0 to exit) : black

Records found, black exist in search history!

我很好奇，虽然“yellow”被添加到树中，但“yellow”不在我的搜索结果中。

Answer 1

您的 searchBranch 方法使用错误的条件来决定要搜索的子分支。它应该比较 tmp.data 和 value 来决定左右分支，而不是仅仅沿着哪个分支恰好通向某个地方:

public void searchBranch (StringTreeNode tmp, String value) {    
    if(value.equals(tmp.data)) {
        System.out.println("Records found, " + value + " exist in search history!");
        found = true;
    } else if (value.compareTo(tmp.data) < 0)
        searchBranch(tmp.left, value);
    else 
        searchBranch(tmp.right, value);
}

请注意，这与 addLeaf 在确定给定值属于节点的左分支还是右分支时使用的逻辑基本相同。