tree - 带括号的中序树遍历

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 inherit from Node and implement GetExpressionString() so that it returns Token. (for example '1' or '2' or '3').

Let class Operator inherit from Node, has fields Left and Right of type Node and implement GetExpressionString() so that it returns '(' + Left.GetExpressionString() + Token + Right.GetExpressionString() + ')'. For example if Left = '2', Right = '3' and Token = '*', then result is '(2*3)'.

Then for

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() returns '(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<<")";
    }
}