3

順不同のトラバーサルを行うことは知っていますが、左の子と右の子を区別する方法がわかりません。いつ葉に括弧を入れるか、それとも何か他のことをするべきかを基にすべきでしょうか。私は再帰がひどいです。ツリーはすでに完全に機能しているので、(1 + 2) * (3 - 4) のような式を入れて、postfix に変換してツリーに追加できます。各式に独自の括弧のセットを与える方法を見つける必要があるだけです。

これは、それを機能させるコードです。アルゴリズムのドリームクラッシュに感謝します!

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 に答える