探索/二分探索木 - nkym_memo @ ウィキ

二分探索木

任意の節xについて、左部分木に含まれる要素は節xよりも小さく、右部分木に含まれる要素は節xよりも大きい

&attachref

• 二分探索木の節

  typedef struct node{
  	int data;
  	struct node *left;
  	struct node *right;
  }NODE;
  
  NODE *root = NULL;

二分探索木の探索

• NODE *search(int key) 二分探索木を探索する 節へのポインタを返す 見つからない場合、NULLを返す

再帰呼び出しの場合

NODE *search(int key,NODE *p)
{
  if(p == NULL){
    return NULL;
  }else if(key == p->key){
    return p;
  }else if(key < p->key){
    return (search(key,p->left));
  }else{
    return (search(key,p->right));
  }
}

ループの場合

NODE *search(int key,NODE *p)
{
	p = root;
	while(p != NULL){
		if(key == p->data)){
			return p;
		}else if(key < p->data)){
			p = p->left;
		}else{
			p = p->right;
		}
		return NULL;
	}
}

二分探索木への挿入

• NODE *insert(int key) 二分探索木に要素を挿入する すでに要素が登録されているのなら、何もしないでNULLを返す

NODE *insert(int key)
{
  NODE **p,*new;

  while(*p != NULL){

    if(key == (*p)->data){
      return NULL;
    }else if(key < (*p)->data)){
      p = &(*p)->left;
    }else{
      p = &(*p)->right;
    }
  }
  
  if((new = malloc(sizeof(NODE))) == NULL){
    fprintf(stderr,"out of memory!\n");
  }
  new->left = NULL;
  new->right = NULL;
  new->data = key;
  *p = new;
  return new;
}

サンプルプログラム

• 二分探索木サンプルプログラム

---

参考文献

• 定本 Cプログラマのためのアルゴリズムとデータ構造(近藤 嘉雪,ソフトバンククリエイティブ,1998)
• Cをさらに理解しながら学ぶデータ構造とアルゴリズム(森本 逞,共立出版,2007)