Автоматизируйте преобразование выражений «inorder / infix» в соответствующие выражения «PostOrder» и «PreOrder», используя «Деревья выражений».

Question

Пожалуйста, я действительно борюсь с назначением деревьев и стеков в C. Мне действительно нужна помощь. Чтобы суммировать назначение, нас просят изменить выражение или выражение с выражений inOrder на выражения PostOrder и PreOrder с помощью деревьев выражений. Он также заявил, что после построения мы должны пройти по дереву выражений в одном из трех обходов: LNR, LRN, NLR. Наконец, для реализации профессор попросил нас сделать это, используя стеки в построении деревьев выражений

Answer 1

Когда вы посещаете дерево рекурсивно, вы контролируете, когда обрабатываете текущий узел относительно того, когда вы обрабатываете его дочерние элементы.

Рассмотрите разницу между следующими тремя посетителями для двоичного дерева:

void visit1(Node *node) {
   if (!node)
      return;

   do_something(node);
   visit1(node->left);
   visit1(node->right);
}

void visit2(Node *node) {
   if (!node)
      return;

   visit2(node->left);
   do_something(node);
   visit2(node->right);
}

void visit3(Node *node) {
   if (!node)
      return;

   visit3(node->left);
   visit3(node->right);
   do_something(node);
}

Не видите? Рассмотрим дерево, представляющее (1-2)+(3-4).

            op:+
       ____/   \____
      /             \
    op:-            op:-
   /   \           /   \
num:1  num:2    num:3  num:4

Для каждого из трех посетителей, каков порядок вызовов на do_something для дерева?