Кратчайший Путь от Корня к Листу

Question

Какой самый простой способ, предпочтительно используя рекурсию, найти кратчайший путь от корня к листу в BST (двоичном дереве поиска)?Предпочитаемая Java, псевдокод в порядке.

Спасибо!

Answer 1

Общее описание:

Используйте Поиск в ширину (BFS) в отличие от Поиск в глубину (DFS).Найдите первый узел, у которого нет дочерних элементов.

Используя DFS, вам может повезти с некоторыми входными деревьями (но нет способа узнать, что вам повезло, поэтому вам все равно нужно выполнить поиск по всему дереву), но использование метода BFS намного быстрее, и вы можете найти решение, не касаясь всех узлов.

Чтобы найти путь от корня к листу, вы могли бы пройти по первому найденному бездетному узлу вплоть до корня, используя родительскую ссылку.Если у вас нет родительской ссылки, сохраненной в каждом узле, вы можете отслеживать родительские узлы при рекурсии вниз.Если у вас есть свой список в обратном порядке, вы могли бы поместить все это в стопку, а затем удалить.

Псевдокод:

Проблема очень проста;вот псевдокод для нахождения наименьшей длины:

1. Поместите корневой узел в очередь.

Повторяйте, пока очередь не станет пустой, и результат не будет найден:

2. Извлеките узел из начала очереди и проверьте, нет ли у него дочерних элементов.Если у него нет дочерних элементов, вы закончили, вы нашли кратчайший путь.
3. В противном случае поместите всех дочерних элементов (слева, справа) в очередь.

Поиск всех кратчайших путей:

Чтобы найти все кратчайшие пути, вы можете сохранить глубину узла вместе с узлом внутри очереди.Затем вы продолжили бы алгоритм для всех узлов в очереди с одинаковой глубиной.

Альтернатива:

Если бы вместо этого вы решили использовать DFS, вам пришлось бы обыскать все дерево, чтобы найти кратчайший путь.Но это можно было бы оптимизировать, сохранив значение для самого короткого на данный момент и проверяя глубину будущих узлов только до тех пор, пока вы не найдете новый самый короткий или пока не достигнете самого короткого на данный момент.Однако BFS - гораздо лучшее решение.

Answer 2

Это на C ++, но это настолько просто, что вы можете легко преобразовать его.Просто измените min на max, чтобы получить максимальную глубину дерева.

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

Просто чтобы объяснить, что это делает, он ведет отсчет от конечного узла (он возвращает 0, когда находит лист) и ведет обратный отсчет до корня.Выполнив это для левой и правой сторон дерева и взяв минимум, вы получите кратчайший путь.

Answer 3

Поиск по ширине в точности оптимален с точки зрения количества посещенных вершин.Вы должны посетить каждую из вершин, которые вы бы посетили при поиске в ширину, просто для того, чтобы доказать, что у вас есть ближайший лист!

Однако, если у вас есть мандат на использование рекурсии, подход Майка Томпсона таков почти правильный в использовании - и немного проще.

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 4

статический int findCheapestPathSimple(корневой код дерева){

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

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

}