> 探索 > 二分探索木

探索/二分探索木

Last-modified: 2010-07-17 (土) 14:56:29

二分探索木

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

二分探索木の節

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;
}