Пройдите ветку сверху вниз.[указан корневой и целевой узлы]

Question

Как пройти по ветви n-арного дерева, если у вас просто есть узел источника и узел назначения. Остальное все можно предположить. Учитывая, что исходный узел является предком этого узла назначения.

Answer 1

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

Answer 2

BFS? http://en.wikipedia.org/wiki/Breadth-first_search

Answer 3

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

Answer 4

да, dfs - это один из способов, которым мы можем пройти узлы, сравнить каждый с узлом назначения, пока не найдем один n возврат ... в случае, если вы не найдете (оставьте флаг для отслеживания), вы можете выбросить исключение или сделать все, что вы хотите сделать, чтобы справиться с этим.