Loading article…
二分式木は、式を表すために使用される特定の種類の二分木です。二分式木が表現できる一般的な式の種類は、代数式[ 1 ]とブール式です。これらの木は、単項演算子と二項演算子の両方を含む式を表すことができます。[ 1 ]
他の二分木と同様に、二分式木の各ノードは、0個、1個、または2個の子ノードを持ちます。この制限された構造により、式木の処理が簡素化されます。
後置記法での入力は、ab + cde + * * です。最初の 2 つのシンボルはオペランドであるため、1 つのノードを持つツリーが作成され、それらへのポインタがスタックにプッシュされます。便宜上、スタックは左から右に成長します。
次の記号は「+」です。これは、ツリーへの2つのポインタをポップし、新しいツリーを形成し、そのツリーへのポインタをスタックにプッシュします。
次に、c、d、eが読み込まれる。それぞれについて1ノードの木が作成され、対応する木へのポインタがスタックにプッシュされる。
続いて「+」が読み込まれ、最後の2つのツリーがマージされます。
次に、「*」が読み込まれます。最後の2つのツリーポインタがポップされ、「*」をルートとする新しいツリーが形成されます。
最後に、最後のシンボルが読み取られます。2 つのツリーがマージされ、最終的なツリーへのポインタがスタック上に残ります。[ 2 ]
代数式ツリーは、数値、変数、単項演算子および二項演算子を含む式を表します。一般的な演算子には、×（乗算）、÷（除算）、+（加算）、−（減算）、^（べき乗）、-（否定）などがあります。演算子はツリーの内部ノードに含まれ、数値と変数はリーフノードに含まれます。[ 1 ]二項演算子のノードには2つの子ノードがあり、単項演算子には1つの子ノードがあります。
ブール式は代数式と非常によく似た形で表現されますが、唯一の違いは使用される具体的な値と演算子です。ブール式では、定数値として真と偽が使用され、演算子には以下が含まれます。（そして）、（または）、（ない）。
