Cómo encontrar un elemento en un árbol de búsqueda binario

Su consulta ” detiene la recursión de la cola una vez que la encuentra ” .

¡Ahora no está claro si desea recuperar el nodo del árbol de búsqueda binario o simplemente desea que se levante una bandera booleana!

Código 1: para recuperar el nodo de BST

Búsqueda de nodo público estático (raíz de nodo, int toSearch)
{
// ¡devuelve root si está vacío o coincide!
if (root == null || root.data == toSearch)
volver root;

// atraviesa el subárbol izquierdo de los datos de la raíz> elemento de búsqueda
if (root.data> toSearch)
búsqueda de retorno (root.left, toSearch);

// atraviesa el subárbol derecho de los datos de la raíz búsqueda de retorno (root.right, toSearch);
}

Código 2: ¡No recuperar el nodo cuando coincide (implementación similar)!

búsqueda estática pública booleana2 (raíz de nodo, clave int)
{
if (raíz == nulo)
falso retorno;
if (root.data == clave)
volver verdadero;

if (raíz.datos> clave)
return search2 (root.left, key);

// recursión del subárbol derecho
return search2 (root.right, key);
}

Para responder a su pregunta sobre la detención de la recursión de la cola, consulte las líneas 10 y 13.

Solo voy a suponer que está utilizando Java y tiene una clase BST genérica que tiene una variable de instancia para el nodo raíz y la clase de nodo privado tiene los métodos BST estándar de getRight (), getLeft () y getData () .

Nodo público búsqueda (datos T) {
if (datos == nulo) {
lanzar nueva IllegalArgumentException (“El argumento de datos no puede ser nulo”);
}

if (this.root == null) {
lanzar una nueva NoSuchElementException (“No existen elementos en este BST”);
}
return searchHelper (datos, this.root);
}

Nodo privado searchHelper (datos T, nodo actual) {
if (data.compareTo (current.getData ())> 0) {
return (current.getRight () == null)? nulo: searchHelper (data, current.getRight ());
} else if (data.compareTo (current.getData ()) <0) {
return (current.getLeft () == null)? nulo: searchHelper (data, current.getLeft ());
}
corriente de retorno; //encontró
}

¡Espero que esto ayude!

1. Comience en el nodo raíz del árbol
2. Compare el valor del nodo actual con el valor que se busca

1. Si los valores son iguales, ya está
2. Si el valor que se busca es menor que el valor del nodo actual …

1. Si existe un niño izquierdo, vaya al niño izquierdo y comience el paso 2 nuevamente
2. Si no existe un elemento secundario izquierdo, el valor no está en el árbol

1. Si existe un niño correcto, vaya al niño correcto y comience el paso 2 nuevamente
2. Si no existe un hijo correcto, el valor no está en el árbol

El punto clave es que simplemente está verificando el valor actual y luego decidiendo si atravesar o no a un niño (y cuál).

Para cualquier BST, los elementos en el lado derecho de la raíz serán mayores que la raíz y los elementos en el lado izquierdo serán más pequeños que la raíz. Por lo tanto, puede seguir comparando los datos con los datos de cada nodo y ver si hay una coincidencia. Puedes hacer esto usando recursividad

public static boolean isElementPresent (raíz del nodo, int num)

{

if (root == null) devuelve falso;

if (root.data == num)

volver verdadero;

if (root.data

return isElementPresent (root.right, num);

más

return isElementPresent (root.left, num);

}

Escribí un método de búsqueda recursivo en Python para un BST a continuación. También tengo una versión completa de un BST si tiene curiosidad sobre cualquier otro detalle de implementación.

Nodo de clase:
def __init __ (self, val):
self.val = val
self.left = Ninguno
self.right = Ninguno

clase BST:
” ‘… __init__, insertar, eliminar, …’ ”

def find (self, val):
si self.root es None:
falso retorno
return self .__ find (self.root, val)

def __find (self, nodo, val):
si el nodo es Ninguno:
devuelva False # cambie False con None si desea el nodo real)
elif node.val == val:
devuelva True # cambie True con el nodo si desea el nodo real)
elif node.val> val:
return self .__ find (node.left, val)
más:
return self .__ find (node.right, val)