探索/二分探索木/二分探索木サンプルプログラム - nkym_memo @ ウィキ

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

• 初期化としてキー値を連番で10個挿入
• オプションで探索キー値をとる
• すんごい適当

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

typedef struct node{
  int key;
  int data;
  struct node *left;
  struct node *right;
}NODE;

NODE *root = NULL;

enum{
  RAND_min = 0,
  RAND_max = 1000
};

int Rand(int min,int max)
{
  static int flag;
  if(!flag){
    srand((unsigned int)time(NULL));
    flag = 1;
  }

  return (max - min + 1) * (float)rand()/RAND_MAX + min;
}

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

  p = &root;
  while(*p != NULL){
    if(key == (*p)->key){
      return NULL;
    }else if(key < (*p)->key){
      p = &(*p)->left;
    }else{
      p = &(*p)->right;
    }
  }
 
  if((new = malloc(sizeof(NODE))) == NULL){
      fprintf(stderr,"Error:Cannot allocate memory");
      exit(1);
  }
  new->left = NULL;
  new->right = NULL;
  new->key = key;
  new->data = Rand(RAND_min,RAND_max);
  *p = new;

  return new;
} 

void init()
{
  int i;
  NODE *p;
  for(i = 0;i < 10; i++){
    if((p = insert(i)) == NULL){
      fprintf(stderr,"Error:insert");
      exit(1);
    }
    printf("Node key:%d data:%d\n",p->key,p->data);
  }
}

NODE *search(int key)
{
  NODE *p;

  p = root;
  while(p != NULL){
    if(key == p->key){

      return p;
    }else if(key < p->key){
      p = p->left;
    }else{
      p = p->right;
    }
  }
  return NULL;
}

int main(int argc,char *argv[])
{  
  init();
 
  int key = atoi(argv[1]);
  fprintf(stdout,"check:key:%d\n",key);   

  NODE *p;
  p = search(key);

  if(p != NULL){
    printf("Data found : key %d data %d \n",p->key,p->data);
  }else{
    printf("Not found\n");
  }

  return 0;
}

---

参考文献

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