2012-12-21 32 views
1

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

+0

Это звучит как ошибка реализации, так что, возможно, вы можете опубликовать код? –

+0

Вы хотите найти самый короткий путь? Возможно, отредактируйте свой титул. –

+0

Дерево не «толкает» узлы в «стек»; он вставляет их. Это похоже на реализацию, а не на дизайн; вы могли бы поделиться каким-то кодом? – Makoto

ответ

0

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

Надеюсь, это может вам помочь ...

+0

Моя идея состояла в том, чтобы найти путь от корня к корню, используя один из поиска dfs. Но каждый раз, когда я использую один из обходов, если узел находится в правом поддереве корня, путь сначала находит те, что находятся в левом поддереве корня, чем справа, поэтому путь выходит неправильно. Кстати, у меня есть только доступ к корню. – Alek

Смежные вопросы