algorithm - example - Raíz más corta al camino de la hoja

inorder traversal of a binary search tree

Question

¿Cuál es la forma más fácil, de preferencia utilizando la recursión, para encontrar el camino más corto de raíz a hoja en un BST (árbol de búsqueda binaria). Java preferido, pseudocódigo está bien.

¡Gracias!

Answer 1

Esto está en C ++, pero es tan simple que puedes convertirlo fácilmente. Simplemente cambie de mínimo a máximo para obtener la profundidad máxima de árbol.

int TreeDepth(Node* p)
{
    return (p == NULL) ? 0 : min(TreeDepth(p->LeftChild), TreeDepth(p->RightChild)) + 1;
}

Solo para explicar lo que está haciendo, está contando desde el nodo hoja (devuelve 0 cuando encuentra una hoja) y vuelve a contar hasta la raíz. Hacer esto para los lados izquierdo y derecho del árbol y tomar el mínimo le dará el camino más corto.

Answer 2

La primera búsqueda de amplitud es exactamente óptima en términos de la cantidad de vértices visitados. ¡Tienes que visitar cada uno de los vértices que visitarías en una primera búsqueda para demostrar que tienes la hoja más cercana!

Sin embargo, si tiene el mandato de utilizar la recursividad, el enfoque de Mike Thompson es casi el correcto, y es un poco más simple.

TD(p) is
  0 if p is NULL (empty tree special case)
  1 if p is a leaf (p->left == NULL and p->right == NULL)
  min(TD(p->left), TD(p->right)) if p is not a leaf 

Answer 3

static int findCheapestPathSimple (raíz de TreeNode) {

if(root==null){
    return 0; 
}

return root.data+Math.min(findCheapestPathSimple(root.left), findCheapestPathSimple(root.right));

}

Answer 4

Descripción general:

Utilice una búsqueda de primer orden (BFS) en lugar de una búsqueda de profundidad (DFS) . Encuentra el primer nodo sin hijos.

Usando un DFS puede tener suerte en algunos árboles de entrada (pero no hay manera de saber que tuvo suerte, así que todavía necesita buscar todo el árbol), pero usar el método BFS es mucho más rápido y puede encontrar una solución sin tocar todo nodos.

Para buscar la ruta de raíz a hoja, puede seguir el primer nodo sin datos encontrado hasta la raíz con la referencia principal. Si no tiene una referencia principal almacenada en cada nodo, puede realizar un seguimiento de los nodos principales a medida que recurre hacia abajo. Si tiene su lista en el orden inverso, puede colocarla en una pila y luego abrirla.

Pseudo-código:

El problema es muy simple; aquí está el pseudo código para encontrar la longitud más pequeña:

1. Coloque el nodo raíz en la cola.

Repita mientras la cola no está vacía, y no se encontró ningún resultado:

2. Tire de un nodo desde el principio de la cola y verifique si no tiene hijos. Si no tiene hijos, ha terminado y ha encontrado el camino más corto.
3. De lo contrario, empuje a todos los niños (izquierda, derecha) en la cola.

Encontrar todos los caminos más cortos:

Para encontrar todas las rutas más cortas, puede almacenar la profundidad del nodo junto con el nodo dentro de la cola. Luego, continuaría el algoritmo para todos los nodos en la cola con la misma profundidad.

Alternativa:

Si, en cambio, decidiera usar un DFS, tendría que buscar todo el árbol para encontrar el camino más corto. Pero esto podría optimizarse manteniendo un valor para el más corto hasta el momento, y solo comprobando la profundidad de los nodos futuros hasta que encuentre uno nuevo más corto, o hasta llegar al más corto hasta el momento. Sin embargo, el BFS es una solución mucho mejor.