binary-tree - 式の二分木

Question

この式の二分木を描く必要がありますA*(B-C+D)*P/Q

これは正しいですか？

                        *

             *                    /

          A     +              P     Q

              -   D 

            B   C

Answer 1

あなたのツリーは次の式に対応しています:

   (A*(B-C+D))*(P/Q)

技術的には正しいですが、次のようになります (乗算と除算の優先順位が等しいと仮定した場合)。

   ((A*(B-C+D))*P)/Q

Answer 2

あなたの答えは正しいです。以下は、このツリーを取得する手順です。

A*(B-C+D)*P/Q

ステップ 1 : 括弧の優先順位が最大であるため、最初に評価されます。

B-C+D

ただし、+ と - の実行優先度は同じであるため、結合性が考慮されます。演算子は、左から右へ同じ結合性を持ちます。つまり、左側には、演算子に対するオペランドが 1 つだけある必要があります。- 演算子のみが左側に 1 つのオペランドを持っているため、最初に実行され、次に + 式が次のように変更されます。

( (BC) + D )

A*Z*P/Q ここで、z=( (BC) + D )

ステップ 2: * と / は評価の優先順位が同じであるため、* と / のタイ結合性を破ることが考慮されます。両方の演算子は左から右に同じ結合性を持ちます。つまり、左側は明確でなければなりません。これは、演算子 (* OR /) の左側にオペランドが 1 つしかないことを意味します。

したがって、最初の * のみが 1 つのオペランド、つまり A を持つため、次に A*Z が実行されます。

(A*Z)*P/Q

に名前を変更しましょう

AZ*P/Q

ステップ 3: 残りのオペランドの優先度が同じであるため、結合規則に従います * 左の AZ にオペランドが 1 つしかないため、最初に実行されます。

AZP/Q

ステップ 4:最後に / 演算子が実行されます

AZPQ

Answer 3

式を書いているときに間違いを犯したと思います..私によれば、それはA*B-(C+D)*P/Qであり、この場合、バイナリツリーは次のようになります..

                -
        *                    *
      A   B             +          /
                      C   D      P   Q

Answer 4

明確にするために、式ツリーでは各二項演算を括弧で囲むことができます。そのため、 (B- C) +D と B - (C + D) の異なるツリーになりますが、加算の連想規則により結果は同じになります。

人間の読み手にとってはあまり明確ではありませんが、一貫したブラケットの利点は、(((A*(B-(C+D))) P)/Q) と ((A (B-(C+D)))を明確に区別できることです。 )*(P/Q))。