3

我知道要进行中序遍历，但我不知道如何区分左孩子和右孩子。我什至应该基于何时在叶子上加上括号，还是应该做其他事情。我很讨厌递归。我已经让树完美地工作了，所以我可以输入一个像 (1 + 2) * (3 - 4) 这样的表达式，将其转换为后缀并将其添加到树中。我只需要找到一种方法来为每个表达式赋予其自己的一组括号。

这是使它工作的代码，感谢算法dreamcrash！

private void printInfix(Node n)
{   
    if (n != null)
    {
        if (n.isLeaf())//if n is a leaf, therefore a number
            System.out.print(n.element);
        else//n is not a leaf
        {
            System.out.print("(");
            printInfix(n.left);
            System.out.print(n.element);
            printInfix(n.right);
            System.out.print(")");
        }//end else
    }//end if   
}
4

2 回答 2

4

我做了一些研究，我发现了这个：

Algorithm infix (tree)
/*Print the infix expression for an expression tree.
 Pre : tree is a pointer to an expression tree
 Post: the infix expression has been printed*/
 if (tree not empty)
    if (tree token is operand)
       print (tree token)
    else
       print (open parenthesis)
       infix (tree left subtree)
       print (tree token)
       infix (tree right subtree)
       print (close parenthesis)
    end if
 end if
end infix

在http://en.wikipedia.org/wiki/Binary_expression_tree上。

我还找到了一个很好的解释和一些代码实现（但在 python 中）。尽管如此，这个想法仍然是一样的，只是语法问题：http: //interactivepython.org/courselib/static/pythonds/Trees/bintreeapps.html

于 2012-10-31T23:20:20.523 回答
0

您应该在父节点中添加括号，而不是在子节点中。正如您所说，您很难区分右孩子和左孩子。这是因为子节点不知道它是哪个。但是，父节点手头有此信息。

于 2012-10-31T22:52:57.820 回答