¿Cómo buscar un nodo en un árbol y devolverlo?

Question

Estoy tratando de buscar un nodo en un árbol binario y regresar en caso de que esté allí, de lo contrario, devolverá nulo. Por cierto, la clase nodo tiene un nombre de método() que devuelva una cadena con su nombre ... Lo que tengo hasta ahora es:

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; 
} 

¿Es esto correcto ??

Answer 1

Debes asegurarte de que tus llamadas recursivas a la búsqueda regresen si el resultado no es nulo.

Algo como esto debería funcionar ...

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; 
    } 
} 

Answer 2

Esto podría ser mejor:

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; 

Answer 3

debe devolver algo si se encuentra en node.left o node.right por lo que el bloque else debe ser algo así:

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

Answer 4

usted no hace nada con el resultado de las llamadas recursivas

Node res = search(name, node.left); 
if(res!=null)return res; 
res = search(name, node.right); 
if(res!=null)return res; 

Answer 5

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)); 
     } 
    } 
} 

Answer 6

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; 
} 

Answer 7

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; 

} 

Answer 8

En realidad, tratan de evitar la recursividad. En caso de que tenga una gran estructura de árbol, obtendrá un error de desbordamiento de pila. En lugar de ello se puede utilizar una lista:

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; 
} 

Answer 9

Puesto que el lenguaje no importa mucho para esta pregunta, esto es lo que se ve en C# con pre-orden de recorrido:

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); 
}