意志決定木
2分木の応用で最も単純な物として、意志決定木がある。
yes/no の答えを回答すると、最終的に「あなたの性格は✕✕です」と表示するようなヤツ。
struct Tree {
char* q_a ;
struct Tree* yes ;
struct Tree* no ;
} ;
top
＼
あなたは勉強が好き？
／yes ＼no
ものづくりは好き？ 人と話すのが好き？
／yes ＼no ／yes ＼no
技術者タイプ ◯◯◯ 営業タイプ ◯◯◯
このような場合、プログラムは…
struct Tree* tcons( char*s, struct Tree*y, struct Tree*n )
{ struct Tree* ans ;
ans = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
if ( ans != NULL ) {
ans->q_a = s ;
ans->yes = y ;
ans->no = n ;
}
return ans ;
}
void main() {
struct Tree* top =
tcons( "あなたは勉強が好き?" ,
tcons( "ものづくりは好き?" ,
tcons( "技術者タイプ , NULL , NULL ) ,
tcons( "...." , NULL , NULL ) ) ,
tcons( "人と話すのが好き?" ,
tcons( "営業タイプ" , NULL , NULL ) ,
tcons( "...." , NULL , NULL ) ) ) ;
struct Tree* p = top ;
while( p->yes != NULL && p->no != NULL ) {
char a[10] ;
printf( "%s" , p->q_a ) ;
scanf( "%s" , a ) ;
if ( strcmp( a , "yes" ) == 0 )
p = p->yes ;
else
p = p->no ;
}
printf( "%s¥n" , p->q_a ) ;
}
※ このプログラムの問題点は？
演算子と2分木
2分木の応用の例としては、式の表現などがある。
例えば、”1+2*3″という式があった場合、”(1+2)*3=9″なのか”1+(2*3)=7″なのか。(数学では演算子の優先順位から後者)、こういう演算子の優先順位をカッコで表さないためには、どうするか？
中置記法 1+2*3 = 1 + (2 * 3) ＋
／ ＼
前置記法 +,1,*,2,3 １ ＊
／ ＼
後置記法 1,2,3,*,+ ２ ３
後置記法は、コンピュータで計算をする場合に都合が良く、ポーランド記法としてよく知られている。
コンピュータで式を表すデータを、2分木に表現することもできる。こういった文法や処理を表す木は、構文木とも呼ばれる。
演算子では、演算子の優先順位以外にも、左結合・右結合といったものも重要となる。
左結合演算子 1+2+3+4 → ((1+2)+3)+4 右結合演算子 x=y=z=0 → x = (y = (z=0))