バイナリ表現木 - 百科事典

バイナリ表現木は、表現を表すために使用される特定の種類のバイナリ木です。バイナリ表現木が表す一般的な表現の種類には、代数的および論理的表現があります。これらの木は、一項および二項演算子を含む表現を表すことができます。

どのバイナリ木と同様に、バイナリ表現木の各ノードは、0、1、または2つの子供を持っています。この制限された構造は、表現木の処理を単純化します。

表現木の構築


= 例 =
ポストフィクス記法の入力は以下の通りです：a b + c d e + * *

最初の2つのシンボルは操作数であるため、1ノードの木が作成され、それらへのポインタがスタックにプッシュされます。便利のために、スタックは左から右に成長します。

次のシンボルは'+'です。2つの木のポインタをポップし、新しい木が形成され、それへのポインタがスタックにプッシュされます。

次に、c、d、およびeを読み取ります。それぞれに対して1ノードの木が作成され、対応する木へのポインタがスタックにプッシュされます。

続いて、'+'が読み取られ、最後の2つの木が統合されます。

次に'*'が読み取られ、最後の2つの木のポインタがポップされ、'*'をルートに持つ新しい木が形成されます。

最後に、最後のシンボルが読み取られ、2つの木が統合され、最終的な木へのポインタがスタックに残ります。


代数的表現

代数的表現木は、数値、変数、一項および二項演算子を含む表現を表します。一般的な演算子には、×（乗法）、÷（除法）、+（加法）、−（減法）、^（指数）、および−（否定）があります。演算子は木の内部ノードに含まれ、数値および変数は葉ノードに含まれます。二項演算子のノードには2つの子供ノードがあり、一項演算子のノードには1つの子供ノードがあります。


論理的表現

論理的表現は、代数的表現と非常に似ていますが、使用される特定の値および演算子が異なります。論理的表現は、trueおよびfalseを定数値として使用し、演算子には以下のものがあります。



∧


（AND），

∨


（OR），

¬


（NOT）。



参考文献
Expression (mathematics)
Term (logic)
Context-free grammar
Parse tree
Abstract syntax tree