0

我正在寻找搜索二叉树以查找存储在节点中的字符串。

public void traverse (BinaryTreeNode root){ 
    if (root.leftchild != null){
        traverse (root.leftchild);
    }
        System.out.println(root.character);
    if (root.rightchild != null){
        traverse (root.rightchild);
    }
}

这工作得很好，并显示了树中的所有节点。（该代码是从另一个旧的 stackoverflow 问题的代码中工作的！我的问题是如何将 root.character 与输入的字符串进行比较，以及它是否匹配中断递归。如果有人可以给出一些提示，我将不胜感激。

    public BinaryTreeNode traverse (BinaryTreeNode root, String inString){ // Each child of a tree is a root of its subtree.
    if (root.character != null) {
        if (root.character.equalsIgnoreCase(inString)) {
            System.out.println("root.charcter: " + root.character + " char " + inString);
            return root;
        }
    }
    if (root.leftchild != null){
        traverse (root.leftchild, inString);
    }

    if (root.rightchild != null){
        traverse (root.rightchild, inString);
    }

    return null;
}

上面的代码似乎有效，它返回正确的 BinaryTreeNode 但是，我还没有弄清楚如何在找到节点后停止递归，因此它最后也返回 null 。

4

1 回答 1

1

您在没有将字符串传递给搜索的情况下调用 traverse 函数......在很多情况下，您也缺少返回值。

您需要更多地考虑您的函数何时应该终止递归（在这种情况下，返回节点）以及函数在不终止但探索树的其余部分时应该做什么。

例如在伪代码中（您进行编程）：

findNode(root, query) {
  // nothing to search, not found
  if root==null return null  

  // Found it!
  if root.name==query return root

  // This is when we recurse left, stop if we found a result
  leftResult = findNode(root.left, query)
  if leftResult!=null return leftResult

  // else try to the right, stop if we found a result
  rightResult = findNode(root.right, query)
  if rightResult!=null return rightResult

  // Nothing else to try, not found
  return null
}
于 2012-11-21T21:10:19.930 回答