如何在二叉树中搜索节点并返回它？

Question

我正在尝试在二叉树中搜索节点，如果找到，就返回该节点，否则返回 null。此外，该节点类有一个名为name()的方法，返回节点名称的字符串……目前我的代码如下：

private Node search(String name, Node node){

     if(node != null){
         if(node.name().equals(name)){
            return node;
         }

      else{
         search(name, node.left);
         search(name, node.right);
      }
    }
    return null;
}

这样正确吗？？

- besnico

---

你试过运行它来检查结果是否正确吗？你为什么认为它可能是不正确的？ - FrustratedWithFormsDesigner

你试过了吗？编写测试用例是编程中最重要的部分之一。 - josh.trow

Answer 1

你需要确保递归调用search如果结果不为null就返回。

像这样的做法应该可以解决问题...

private Node search(String name, Node node){
    if(node != null){
        if(node.name().equals(name)){
           return node;
        } else {
            Node foundNode = search(name, node.left);
            if(foundNode == null) {
                foundNode = search(name, node.right);
            }
            return foundNode;
         }
    } else {
        return null;
    }
}

- Tom Jefferys

---

你在 return foundNode 后面忘记加分号了。 - Jason Chen

太棒了，这个方法非常好用，但我发现这个线程是因为我自己的递归方法出了问题...确保如果结果不为空则返回null的提示救了我的一天。 - ViaTech

不错！这有点让人费解，但它确实很有效！ - AFM-Horizon

Answer 2

public Node findNode(Node root, Node nodeToFind) {
    Node foundNode = null;
    Node traversingNode = root;

    if (traversingNode.data == nodeToFind.data) {
        foundNode = traversingNode;
        return foundNode;
    }

    if (nodeToFind.data < traversingNode.data
            && null != traversingNode.leftChild) {
        findNode(traversingNode.leftChild, nodeToFind);
    } else if (nodeToFind.data > traversingNode.data
            && null != traversingNode.rightChild) {
        findNode(traversingNode, nodeToFind);
    }

    return foundNode;

}

- Puneet

Answer 3

既然语言不是这个问题的关键，下面是使用C#进行前序遍历的代码：

public static Node FindNode(Node n, int nodeValue)
{
    if (n == null) return null;
    if (n.Value == nodeValue) return n;
    return FindNode(n.Left, nodeValue) ?? FindNode(n.Right, nodeValue);
}

- Stan Bashtavenko

Answer 4

public static TreeNode findNodeInTree(TreeNode root, TreeNode nodeToFind) {
  if (root == null) {
    return null;
  }

  if (root.data == nodeToFind.data) {
    return root;
  }

  TreeNode found = null;
  if (root.left != null) {
    found = findNodeInTree(root.left, nodeToFind);
    if (found != null) {
      return found;
    }
  }

  if (root.right != null) {
    found = findNodeInTree(root.right, nodeToFind);
    if (found != null) {
      return found;
    }
  }
  return null;
}

- Pratik Khadloya

Answer 5

Node* search(Node* root,int key){
   
   // If key is found or is NULL     
   if (root == NULL || root->key == key) 
      return root;

   if (root->key < key) 
      return search(root->right, key); 
   
   return search(root->left, key);
} 

- Dhruv Patel

Answer 6

public static boolean findElement(Node root, int value) {
    if (root != null) {
        if (root.data == value) {
            return true;
        } else {
            return findElement(root.left, value) || findElement(root.right, value);
        }
    }
    return false;
}

- Spartan

Answer 7

实际上，尽量避免使用递归。 如果你有一个大的树形结构，你会得到堆栈溢出错误。 相反，你可以使用列表：

private Node search(String name, Node node){
    List<Node> l = new ArrayList<Node>();
    l.add(node);
    While(!l.isEmpty()){
        if (l.get(0).name().equals(name))   
            return l.get(0);
        else {
            l.add(l.get(0).left);
            l.add(l.get(0).right);
            l.remove(0);
        }           
    }   
    return null;
}

- iviorel

Answer 8

针对C++程序员：

//search in a binary tree | O(n)
TreeNode* searchBST(TreeNode* root, int val) {
    if(!root) return root;
    if(root->val == val) return root;

    TreeNode* temp = searchBST(root->left, val);
    if(!temp){
        temp = searchBST(root->right, val);
    }
    return temp;
}

//search in a BST | O(logn)
TreeNode* searchBST(TreeNode* root, int val) {
    if(!root) return root;
    if(root->val == val) return root;
    if(val < root->val) return searchBST(root->left, val);
    return searchBST(root->right, val);
}

- Siddharth Saini

Answer 9

这样可能会更好：

if(node != null){
    if(node.name().equals(name)){
        return node;
    }
    else {
        Node tmp = search(name, node.left);
        if (tmp != null) { // if we find it at left
            return tmp; // we return it
        }
        // else we return the result of the search in the right node
        return search(name, node.right);
    }
}
return null;

- bfontaine

---

在编程中，如果使用“return null;”语句，则可能会出现无法访问的代码警告（取决于配置）。 - amit

你是对的，我错过了顶部的大if语句。是我的错误。 - amit

Answer 10

如果在node.left或node.right中找到了某个东西，你应该返回它。因此else块应该像这样：

 else{
     Node temp = search(name, node.left);
     if (temp != null) return temp;
     temp = search(name, node.right);
     if (temp != null) return temp;
  }

- amit

---

需要在else体的结尾加上return null语句，以处理未找到关键字的情况。 - haccks