Necesito crear un algoritmo recursivo para ver si un árbol binario es un árbol de búsqueda binario, así como contar cuántas ramas completas hay (un nodo primario con nodos secundarios izquierdo y derecho) con una variable de conteo global asumida. Esta es una tarea para mi clase de estructuras de datos.
Hasta ahora tengo
void BST(tree T) {
if (T == null) return
if ( T.left and T.right) {
if (T.left.data < T.data or T.right.data > T.data) {
count = count + 1
BST(T.left)
BST(T.right)
}
}
}
Pero realmente no puedo entender esto. Sé que este algoritmo no resolverá el problema porque la cuenta será cero si la segunda declaración if no es verdadera.
¿Alguien podría ayudarme con esto?
algorithms
recursion
trees
OghmaOsiris
fuente
fuente
<
define el operador de comparación en los nodos?true
ofalse
?Respuestas:
Como otros ya han indicado en los comentarios, realmente tiene dos funciones no relacionadas aquí: probar si el árbol es un árbol de búsqueda y contar las ramas completas. A menos que la tarea lo requiera específicamente, escribiría dos funciones separadas.
Veamos primero contar las ramas completas primero. Eso significa contar los nodos que tienen un hijo izquierdo y un hijo derecho. Entonces necesita incrementar el contador (
count = count + 1
) cuando ambosT.left
yT.right
no son nulos (noT.left.data
yT.right.data
: los datos no importan para esta tarea).Además, debe explorar el subárbol izquierdo, incluso si el subárbol derecho está vacío, y debe explorar el subárbol derecho, incluso si el subárbol izquierdo está vacío. Así que mira dónde pones las llamadas recursivas.
Para probar si el árbol es un árbol de búsqueda, debe inspeccionar los valores de los datos. Ya tienes algo parecido a la comparación correcta; no del todo bien. Escriba algunos árboles de ejemplo con varias formas (no muy grandes, de 2 a 5 nodos) y ejecute su algoritmo para ver qué sucede.
Aún necesita encontrar un lugar para colocar el resultado de la verificación de validez. Nuevamente, observe dónde coloca las llamadas recursivas (si solo hace esta parte, hay varias soluciones, pero en esta etapa no se preocupe si solo ve una).
Finalmente, una vez que haya logrado escribir ambas funciones por separado, y las haya probado en algunos ejemplos, póngalas juntas cuidadosamente (si la tarea lo requiere).
fuente
En cosas como esta, a menudo es más fácil pensar hacia atrás, así que primero considera lo que necesitas. De su descripción, enumeremoslos:
OK, esa es una lista bastante corta, esto debería ser manejable. Comencemos con un método vacío y agregaré una descripción de lo que debería estar sucediendo.
Ahora validez. ¿Cómo se verifica la validez? En el chat dijiste que un árbol es válido "si ... todos los niños restantes son menores que los padres, y los hijos correctos son mayores que los padres". Estoy seguro de que querías permitir la igualdad también. Eso seria
t.left.value <= t.value <= t.right.value
.¿Pero qué pasa si falta uno de los niños? Por lo que ha dicho, creo que sabe que el nodo todavía es válido si falta uno (o ambos). Agreguemos esto, reestructurando ligeramente:
Bien, ahora sabemos si este nodo es válido. ¿Cómo verificamos si todo el árbol es válido? No está en una matriz, por lo que probablemente no podemos / no queremos recorrerlo linealmente. Su tarea da la respuesta: recursividad. Pero, ¿cómo acumulamos una respuesta usando la recursividad? Tenemos acceso a tres piezas de información, si este nodo es válido y el resultado de las llamadas que preguntan si los nodos izquierdo y derecho son válidos. Obviamente, el árbol solo es válido si los tres son verdaderos.
Si está prestando atención, eso incluso nos dice qué debe devolver nuestra función.
Ahora, ¿cómo integramos el conteo? Usted dice lo que cuenta ("un nodo primario con nodos secundarios izquierdo y derecho"), y eso no debería ser difícil de traducir al código real. Compruebe si se cumple esa condición e incremente el contador de forma adecuada. Solo recuerde que esto tiene que estar en algún lugar donde se alcance cada vez que sea cierto.
Y, por supuesto, he omitido algunos detalles, como la condición de detención de recursión y las comprobaciones de nulo.
fuente
Mis tres comentarios anteriores son tres pistas para problemas con su código.
node1.value < node2.value
if
es cierto, ¿está seguro de que eso es lo que quería hacer? Por cierto, es posible que desee verificar que la declaración if haga lo que desea.fuente