¿Cómo encontrar un bucle en un árbol binario? Estoy buscando una solución que no sea marcar los nodos visitados como visitados o hacer un hashing de dirección. ¿Algunas ideas?Encontrar un bucle en un árbol binario
Los árboles binarios no contienen bucles. Si lo hacen, no son árboles en primer lugar.
Como se mencionó anteriormente: Un árbol no contiene (por definición) ciclos (bucles).
Para comprobar si su gráfico dirigido contiene ciclos (referencias a nodos ya agregados al árbol) puede iterar a través del árbol y agregar cada nodo a una lista visitada (o el hash si prefiere) y verificar cada nuevo nodo si está en la lista. Muchos algoritmos para la detección de ciclos en gráficos están a solo una búsqueda de Google de distancia.
Supongamos que tiene un árbol binario pero no confía en él y cree que podría tratarse de un gráfico, en general, el caso dictará recordar los nodos visitados. De alguna manera, es el mismo algoritmo para construir un árbol de expansión mínimo a partir de un gráfico, lo que significa que la complejidad del espacio y el tiempo será un problema.
Otro enfoque sería considerar los datos que guarda en el árbol. Considera que tienes números de hash para que puedas comparar.
Un pseudocódigo sería probar de esta condiciones:
Si un nodo tiene dos hijos, entonces el hijo izquierdo tiene un valor menor que el padre y el hijo derecho tiene un valor mayor. Por lo tanto, teniendo en cuenta esto, si una hoja o un nodo interno tiene como hijo un nodo en un nivel superior (como el padre principal), puede determinar un ciclo basado en los valores. Si un niño es un nodo derecho, entonces su valor debe ser mayor que su padre, pero si ese niño forma un ciclo, significa que es de la parte izquierda o la parte derecha del padre.
3.a. Entonces, si es desde la parte izquierda, su valor es menor que su hermano. Entonces => no es un árbol binario. La idea es algo similar para la otra parte.
Dejando de lado las pruebas, ¿de qué forma es el árbol que desea probar? Recuerde que cada nodo tiene un puntero a su padre. Un puntero apunta a un único padre. Entonces, dependiendo del formato en el que se encuentre su árbol, puede aprovecharlo.
Si pudiera haber bucles, entonces es solo un gráfico habitual. Hay varias maneras de encontrar el bucle: Finding all cycles in a directed graph
Si bien esto podría responder teóricamente a la pregunta, [sería preferible] (// meta.stackoverflow.com/q/8259) incluir aquí las partes esenciales de la respuesta y proporcionar el enlace de referencia. –
¿Qué sucede si el último nodo apunta al nodo raíz ... es un bucle correcto ... n si se ha realizado por error ... entonces cómo detectará ¿eso? – novice
Los últimos nodos se llaman hojas y no apuntan a otros nodos. De lo que estás hablando son gráficos y no árboles. Si tiene un árbol (ya sea binario, rojo-negro, avl, etc.) no contendrá bucles. La construcción del árbol prohíbe los bucles. – amb
como dije lo que ocurre debido a un error ... n ok para su conveniencia deja caer el árbol de palabras d n asumir que es una estructura similar a un árbol con un bucle ... ahora ¿cómo harías el trabajo? – novice