2分木の応用として、式の表現の説明を行う。

まず、式の表現にあたって、演算子の優先順位の話として、 "1+2+3"が、"((1+2)+3)"として扱われる左結合で、 "x=y=z=0"は、"x=(y=(z=0))"で扱われる右結合といった話を説明する。 これらの優先順位情報は、分かり難いのでプログラムと処理しやすいように扱う必要がある。 "2+3*4"といった式は、前置記法では"+,2,*,3,4"と表現される。 一方、後置記法(逆ポーランド記法)では、"2,3,4,*,+"となる。 特に逆ポーランド記法は、計算の機械語生成に結びつくので、よく利用される。

でも、2項演算子は2分木として表現できるため、以下のようなプログラムで 式を扱うこともできる。

struct Exp {
int type ;
int data ;
struct Exp* left ;
struct Exp* right ;
} ;
struct Exp* Integer( int x ) {
struct Exp* n ;
n = (struct Exp*)malloc( sizeof( struct Exp ) ) ;
if ( n != NULL ) {
n->type = 0 ;
n->data = x ;
n->left = n->right = NULL ;
}
return n ;
}
struct Exp* Operator( int op , struct Exp*l , struct Exp*r ) {
struct Exp* n ;
n = (struct Exp*)malloc( sizeof( struct Exp ) ) ;
if ( n != NULL ) {
n->type = 1 ;
n->data = op ;
n->left = l ;
n->right = r ;
}
return n ;
}
int eval( struct Exp* x ) {
if ( x->type == 0 ) {
return x->data ;
} else {
int l = eval( x->left ) ;
int r = eval( x->right ) ;
switch( x->data ) {
case '+' : return l + r ;
case '*' : return l * r ;
}
}
}
void main() {
struct Exp* x =
Operator( '+' , Integer( 2 ) ,
Operator( '*' , Integer( 3 ) ,
Integer( 4 ) ) ) ;
printf( "%d" , eval( x ) ) ;
}

次に、演算子といっても単項演算子、2項演算子、3項演算子などがあり、 これらのデータを表現することを考えると、2分木は3分木といった拡張の イメージもでてくるであろう。これをもっと一般的にすれば、n分木も 考えられる。これをデータベース用にしたものはB木となる。 この方式は、n件のデータと(n+1)件のポインタで実装される。 詳しくは、B木にて。

この話のおまけとして、データベースシステムについて簡単に話す。 特に、データベースが使われるような巨大なシステムになると、 3段スキーマ構成といった事例や、SQLによるアクセスといった、 一般的な話の導入について紹介する。