12

我正在尝试在二叉树中搜索一个节点并在它存在的情况下返回，否则返回 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;
}

它是否正确？？

4

13 回答 13

29

如果结果不为空，您需要确保您对搜索的递归调用返回。

像这样的东西应该工作......

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;
    }
}
于 2011-05-09T14:47:40.427 回答
3 
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;

}
于 2015-08-11T09:30:00.087 回答
1

由于语言对于这个问题并不重要，下面是它在 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);
}
于 2016-06-22T13:57:05.060 回答
0

这可能会更好：

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;
于 2011-05-09T14:45:46.587 回答
0

如果在 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;
  }
于 2011-05-09T14:46:07.027 回答
0

你不会对递归调用的结果做任何事情

Node res = search(name, node.left);
if(res!=null)return res;
res = search(name, node.right);
if(res!=null)return res;
于 2011-05-09T14:47:09.750 回答
0 
Boolean FindInBinaryTreeWithRecursion(TreeNode root, int data)
{
    Boolean temp;
    // base case == emptytree
    if (root == null) return false;
    else {
        if (data == root.getData())  return true;
        else { // otherwise recur down tree
            temp = FindInBinaryTreeWithRecursion(root.getLeft(), data);
            if (temp != true) 
                return temp;
            else
                return (FindInBinaryTreeWithRecursion(root.getRight(), data));  
        }
    }
}
于 2014-10-03T07:14:00.050 回答
0 
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;
}
于 2015-06-25T21:33:53.133 回答
0

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

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;
}
于 2016-01-05T13:57:40.253 回答
0 
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;
}
于 2018-05-02T15:19:24.490 回答
0 
    public TreeNode searchBST(TreeNode root, int val) {
        if(root==null || root.val==val) return root;
        TreeNode found = (val < root.val) ? searchBST(root.left,val) : searchBST(root.right,val);
        return found;
    }

在 GitHub 上查看代码

于 2019-07-27T19:53:13.750 回答
0 
private TreeNode findX(TreeNode root, int x) {
    if(root == null) return null;
    if(root.val == x) return root;

    TreeNode left = findX(root.left,x);
    TreeNode right = findX(root.right,x);

    if(left == null) return right;
    return left;

}
于 2020-03-04T02:36:27.540 回答
0 
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);
}
于 2020-07-18T12:33:23.660 回答