Нерекурсивный поиск в глубину:

Question

В в этом сообщении biziclop вставил псевдокод для нерекурсивного алгоритма поиска в глубину.

Если мы хотим использовать рекурсивный алгоритм DFS для проверки правильности узлов, мы можем использовать два варианта: предзаказ (когда узел проверяется ранее его дети) и после заказа (когда дети проверяются перед узлом), плюс третий вариант ( в порядке : левое поддерево, затем узел, затем правое поддерево) для только двоичное дерево.

Поскольку я заинтересован в наличии всех трех вариантов, если это возможно, я попытался изменить псевдокод biziclop, чтобы получить все три варианта алгоритма DFS. Проблема в том, что я застрял на том факте, что узел добавляется в стек (и, следовательно, проверяется) перед его дочерними элементами. Есть идеи?

Answer 1

почему "(и таким образом проверено)" ?? в рекурсивном подходе вы выбираете сначала проверять текущий узел или сначала видеть его дочерние элементы, здесь точно так же вы просто видите узлы, но когда проверять их - это на вас. например, если вы видите, что это дети и проверили их, просто используйте флаг to seen_its_children (не означает, что он отмечен), чтобы обработать его для post_order, а для in_order это то же самое, в pre_order вы делаете именно то, что сказали, и этого достаточно .