2分木データ構造の応用として、意思決定木と2項演算子による式の表現を説明する。

意思決定木

質問を繰り返した後に、その結果を示すような意思決定木を、 2分木で表現する事例を紹介する。進路決定の時期の4年生というのもあって、 勉強好き？もっと勉強したい？といったようなネタで、例を示す。

プログラム例として、以下のようなものを示す。

char input[ 10 ] ;
struct DTree* p = 何らかの木の生成 ;
// 質問を繰り返す。
while( p->yes != NULL || p->no != NULL ) {
printf( "%s¥n" , p->mes ) ;
scanf( "%s" , input ) ; // 質問への回答を入力
if ( strcmp( input , "yes" ) == 0 )
p = p->yes ;
else
p = p->no ;
}
// 枝の末端であれば、結論を表示する。
printf( "あなたは... %s¥n" , p->mes ) ;

2分木を用いた式の表現

式を表現する手法として、演算子の優先順位を()で表現しないのであれば、 式を逆ポーランド記法に変換しておけば、スタックなどを用いてその処理は容易。 しかしながら、木を用いれば演算式を表現することもできる。 これに合わせて、演算子には単項演算子、2項演算子、3項演算子(?:演算子)が あることを説明する。また、"1+2+3"は"(1+2)+3" , "a=b=c=0" は "a=(b=(c=0))" として扱われ、左結合演算子や右結合演算子の2種類がある。 "1+2"中置記法、"+,1,2"前置記法、"1,2,+"後置記法といった、表現法を説明する。

struct Expr {
int  value ;
char op ; // 演算子は1文字だけを考慮
struct Expr* left ;
struct Expr* right ;
} ;
// 整数値の木の生成関数
struct Expr* Integer( int x ) {
struct Expr* ans=(struct Expr*)malloc(sizeof(struct Expr)) ;
if ( ans != NULL ) {
ans->value = x ;
ans->left = ans->right = NULL ;
}
return ans ;
}
// 演算子の木の生成関数
struct Expr* Operator(char op,struct Expr*l,struct Expr*r) {
struct Expr* ans=(struct Expr*)malloc(sizeof(struct Expr)) ;
if ( ans != NULL ) {
ans->op = op ;
ans->left = l ;
ans->right = r ;
}
return ans ;
}
void main() {
struct Expr* e   // 2分木の式 1+2*3
= Operator( '+' , Integer( 1 ) ,
Operator('*' , Integer( 2 ) , Integer( 3 ) ) ) ;
// 式の値を評価したい
printf( "%d" , eval( e ) ) ;
}
int eval( struct Expr* p ) {
if ( p->left == NULL && p->right == NULL ) {
return p->value ;  // 枝の末端なら定数値
} else {
switch( p->op ) {  // 再帰呼び出しで右辺左辺を計算
case '+' : return eval(p->left)+eval(p->right) ;
case '*' : return eval(p->left)*eval(p->right) ;
}
}
}