2分木を使った式の表現の説明。

2分木を使わない場合

式といっても、演算子の優先順位や結合方向などの問題がある事を説明した後、 逆ポーランド記法などがあることを説明し、 逆ポーランド記法のなら、値を計算する事はスタックを使えば簡単であることを説明。

2分木を使った式の表現

今までの知識だけで2分木を使って式を表現すると、 木の枝のポインタは『値』の場合と『木』の場合があるので、どうするか？ といった話題から、木を表現するデータ構造の宣言を考えさせる。

struct Exp {
int  type ;         /* 節が数値か演算子か？ */
char op ;           /* 数値の場合 */
int  value ;        /* 値の場合 */
struct Exp* left ;  /* 左右の枝 */
struct Exp* right ;
} ;

このデータ構造の場合の『無駄』をどう対処すべきかを答えてもらう。 授業で提案された方式は、以下の３つであった。
# 案1,案3を組み合わせて、共用体を使ったデータ構造の宣言例を示す。
# あわせてtypeのbit数を減らすために、ビットフィールドを使う場合もあることを紹介

1. op と value は同時に使わないから、 value に演算子コードを保存すれば op は不要！
2. 数値の場合には、op に数値を表すコードを割り当てれば、type は不要！
3. 数値の場合は left , right も NULL なので、type は不要！

最後に、上記データ構造での、式の値を求める eval を説明する。