Порядок обхода дерева в скобках

Question

Я решил попытаться научить себя программировать и прорабатываю версию Python "Как думать, как ученый". Пытались не задавать вопросы об упражнениях (поскольку все дело в том, чтобы решить их самостоятельно), но это поставило меня в тупик.

В главе 20 после введения обхода Inorder (работа с выражением 1+2*3) и функции для обхода дерева и печати каждого узла, он затем спрашивает: "изменить printTreeInorder так, чтобы он помещал скобки вокруг каждого оператора и пары операндов ". Таким образом, я предполагаю, что результат должен выглядеть следующим образом (1+(2)*3).

Я борюсь с рекурсивными функциями в целом и борюсь с этим. Я попытался вставить скобки до и после вызовов влево и вправо, но это не сработало, и теперь я думаю, что стек функций будет иметь пять глубин - не понимаю, как из этого получится получить две пары скобок.

Чувствую себя отговорщиком, но кто-нибудь может поставить меня на правильный путь с этим?

Спасибо,

Билли.

Answer 1

puts parentheses round every operator and pair of operands". I'm thus assuming the output should look like (1+(2)*3),

I don't think this should be the output. I think output should be: (1+(2*3))

For me the easiest way to view this is through object oriented approach.

Let abstract class Node have abstract method GetExpressionString() and field Token,

Let class Operand наследовать от Node и реализовать GetExpressionString() so that it returns Token, (например '1' или же '2' или же '3').

Let class Operator наследовать от Node, has fields Left а также Right типа Node и реализовать GetExpressionString() so that it returns '(' + Left.GetExpressionString() + Token + Right.GetExpressionString() + ')', Например, если Left = '2', Right = '3' а также Token = '*', then result is '(2*3)',

Тогда для

expression = new Operator(
               Token='+',
               Left=new Operand(Token='1'),
               Right=new Operator(
                       Token='*',
                       Left=new Operand(Token='2'),
                       Right=new Operand(Token='3')))

a call of expression.GetExpressionString() возвращается '(1+(2*3))',

Answer 2

Этот код на C++ должен работать для вас:

void inorder(node1 *start)
{
    if(!(start->left==NULL && start->right==NULL))
    cout<<"(";
    if(start->left!=NULL)
    inorder(start->left);
    cout<<start->value;
    if(start->right!=NULL)
    inorder(start->right);
    if(!(start->left==NULL && start->right==NULL))
    cout<<")";
}

Answer 3

void inorder(TreeNode* p)
{
    if(p)
    {
        if(p->left && p->right)
            cout<<"(";

        inorder(p->left);
        cout<<p->data<<" ";
        inorder(p->right);

        if(p->left && p->right)
            cout<<")";
    }
}