Алгоритм для трассировки дерева XOR

Question

У меня есть двоичное дерево, а его внутренние узлы состоят из «AND» или «XOR». У узлов листа также есть и данные. Мне нужно распечатать все возможные пути, используя стек (нерекурсивный). Я искал обход дерева с помощью стека, но его алгоритм не выполняется в моем случае, поскольку постобработка, предзаказ или порядок не могут применяться. Я просто не могу придумать какой-либо алгоритм, так что вы можете дать мне некоторые подсказки или некоторые ссылки, источник и т. Д.?

Пример дерева:

Пример вывода: Сыры (10), масло (20), Фило Кондитерские изделия (3), яйцо (1) - общая стоимость = 34

Answer 1

Полезно подумать с точки зрения древовидной структуры и рекурсии и признать, что предварительный порядок, порядок в порядке и послепорядок являются тремя экземплярами рекурсии на дереве. Поскольку это домашнее задание, ИМО - настоящий вопрос, который вы должны задать «Как вы можете имитировать рекурсию со стеком?» Позвольте мне попытаться ответить на это с иллюстрациями на дереве. Скажем, дерево выглядит так

       1 
          /\ 
          2 3 

И позволяет сказать, что у нас есть функция recurse, которая работает следующим образом:

Защиту рекурсии узла: рекурсии (ребенок) над всеми детьми узла йоЗотеЬЫпд (узел)

Допустим, мы называем recurse на 1. поток будет таким:

recurse 1 
    recurse 2 
    doSomething 2 
    recurse 3 
    doSomething 3 
doSomething 1 

Давайте попробуем написать это итеративно сейчас.

def iterate root: 
    //Let "stack" be the stack of nodes to process 
    stack.push(root) 
    while stack is not empty: 
    curr_node = stack.top() 
    if curr_node has a child that hasn't been processed: 
     stack.push(child) 
    else 
     doSomething(curr_node) 
     stack.pop() 

и позволяет исследовать поведение iterate 1:

iterate 1 
    stack 1 
    stack 2 1 
    doSomething 2 
    stack 1 
    stack 3 1 
    doSomething 3 
    stack 1 
    doSomething 1 

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

Answer 2

Рекурсивный подход должен состоять в том, чтобы использовать обычный обход (in, pre или post order) на , изменяя их немного, то есть печатать узел только тогда, когда у него нет левого дочернего и правого ребенка. Что касается общей стоимости, просто объявляйте глобальную или статическую переменную и добавляйте к ней значение каждый раз, когда вы нажимаете листовой узел.

Я оставлю нерекурсивную часть, чтобы вы могли себе представить.