意志決定木

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))