バイナリ式ツリー

二分式ツリーは、式を表すために使用される特定の種類の二分木です。二分式ツリーが表すことができる一般的な式の2つのタイプは、代数式^[1]とブール式です。これらのツリーは、単項演算子と二項演算子の両方を含む式を表すことができます。^[1]

他のバイナリ ツリーと同様に、バイナリ式ツリーの各ノードには 0、1、または 2 個の子があります。この制限された構造により、式ツリーの処理が簡素化されます。

ポストフィックス表記の入力は次のようになります: ab + cde + * * 最初の 2 つのシンボルはオペランドなので、1 ノードのツリーが作成され、それらへのポインタがスタックにプッシュされます。便宜上、スタックは左から右に大きくなります。

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

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

続けて、「+」が読み取られ、最後の 2 つのツリーが結合されます。

ここで、「*」が読み取られます。最後の 2 つのツリー ポインターがポップされ、「*」をルートとして新しいツリーが形成されます。

最後に最後のシンボルが読み取られ、2つのツリーがマージされ、最終ツリーへのポインタがスタック上に残ります。^[2]

代数式ツリーは、数値、変数、単項演算子、二項演算子を含む式を表します。一般的な演算子には、×（乗算）、÷（除算）、+（加算）、−（減算）、^（累乗）、-（否定）などがあります。演算子はツリーの内部ノードに含まれ、数値と変数はリーフノードに含まれます。^[1]二項演算子のノードには2つの子ノードがあり、単項演算子には1つの子ノードがあります。

ブール式は代数式と非常によく似ていますが、唯一の違いは使用される特定の値と演算子です。ブール式では、trueとfalse を定数値として使用し、演算子には( AND )、( OR )、( NOT ) が含まれます。 ${\displaystyle \land}$${\displaystyle \lor}$${\displaystyle \neg}$

• 表現（数学）
• 用語（ロジック）
• 文脈自由文法
• 解析ツリー
• 抽象構文木