データ構造/二分木

二分木(binary tree)

1. 空の木は二分木である
2. 次のいずれかを満足する節のみからなる木は二分木である

• 子を持たない
• 左の子のみをもつ
• 右の子のみをもつ
• 左右２つの子をもつ

⇒二分木の節は高々２つの子しかもたない

• 左部分木
  左の子を根とする部分木

• 右部分木
  右の子を根とする部分木

二分木の表現

struct node{
	struct node *left;
	struct node *right;
	mydata label;
};

木のなぞり(traverse)

木の節を系統的に１つ残らず調べて、各節に１回だけ立ち寄るようにする操作

• 行きがけ順
  1. 根に立ち寄る
  2. 左部分木をなぞる
  3. 右部分木をなぞる
• 通りがけ順
  1. 左部分木をなぞる
  2. 根に立ち寄る
  3. 右部分木をなぞる
• 帰りがけ順
  1. 左部分木をなぞる
  2. 右部分木をなぞる
  3. 根に立ち寄る

行きがけ順

1. 節に立ち寄る
2. 左から順番にすべての部分木をなぞる

   void preorder(struct node *p)
   {
   	if(p == NULL){
   		return;
   	}
   	printf("節%cに立ち寄りました\n",p->label);
   	preorder(p->left);
   	preorder(p->right);
   }

   a→b→c→d　の順になる

通りがけ順

1. 最も左の部分木をなぞる
2. 節に立ち寄る
3. 左から２番目以降の部分木を順番にすべてなぞる

   void inorder(struct node *p)
   {
   	if(p == NULL){
   		return;
   	}
   	inorder(p->left);
   	printf("節%cに立ち寄りました\n",p->label);
   	inorder(p->right);
   }

   　c→b→a→d の順になる

帰りがけ順

1. 左から順番にすべての部分木をなぞる
2. 節に立ち寄る

   void postorder(struct node *p)
   {
   	if(p == NULL){
   		return;
   	}
   	postorder(p->left);
   	postorder(p->right);
   	printf("節%cに立ち寄りました\n",p->label);
   }

   　c→b→d→a の順になる
    

参考文献

• 定本 Cプログラマのためのアルゴリズムとデータ構造(近藤嘉雪,ソフトバンククリエイティブ,1998)