二分木の探索

探索対象の二分木

探索のロジック

二分木は数値が小さいものが左のノードとして格納され、数値が大きいものが右のノードとして格納されます。このロジックを元で探索のプログラムを組みます。

探索のイメージ

■探索結果がある場合

■探索結果がない場合

コード

search.c

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

//declaration of node for tree
struct tree{
  struct tree *left;
  struct tree *right;
  int data;
};

//function declaration
void inorder(struct tree *);
void insert(struct tree **, int);
void search(struct tree *, int, int *);

void main(){
  //declare pointer to tree
  struct tree *bt;
  
  //declare variable for inserting value to tree
  int i=0, a[]={11,9,13,8,10,12,14,15,7};
  
  //declare variable for finding number in tree
  int found = 0;
  
  //set pointer to empty tree
  bt = NULL;
  
  //insert value to tree
  while(i<=8){
    insert(&bt,a[i]);
    i++;
  }
  
  //show nodes in tree in inorder traversal
  printf("Binary tree in inorder traversal:\n");
  inorder(bt);
  
  //search the tree for number 8 (change the value 8 for another number if needed)
  search(bt,8,&found);
  
  printf("Search result: ");
  //check if number is found
  if(found){
  ![result.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/797320/6d5bea14-e451-7d91-927f-1ed628d85bc7.png)
  printf("Value is found\n");
  }else{
    printf("Value is not found\n");
  }
}

//function for searching number in tree
void search(struct tree *q, int num, int *found){
  //if tree is empty, print messsage and return to main
  if(q == NULL){
    printf("Tree is empty. Nothing to search.\n");
    return;
  }

  //loop through tree
  while(q!=NULL){
    //if value is found, set found variable
    if(q->data == num){
      *found = 1;
      //return to main
      return;
    }
    
    //if the number is smaller than value of current node
    if(q->data > num){
      //go to left child
      q = q->left;
    }else if(q->data < num){ //if number is bigger than value of current node
      //go to right child
      q = q->right;
    }
  }
}

//function for inserting node to tree
void insert(struct tree **q, int num){
  //if node is not created
  if(*q == NULL){
    //create new node
    *q = malloc(sizeof(struct tree));
    //set left child to null
    (*q)->left = NULL;
    //set right child to null
    (*q)->right = NULL;
    //set value of node
    (*q)->data = num;
    return;
  }else{
    //if given value is smaller than current node
    if((*q)->data >= num){
      //insert as left child
      insert(&((*q)->left), num);
    }else{ //if given value is bigger than current node
      //insert as right child
      insert(&((*q)->right), num);
    }
  }
  
  return;
}

//function to display tree in inorder traversal
void inorder(struct tree *q){
  //if node is not empty
  if(q!=NULL){
    //go to left child
    inorder(q->left);
    //print value of node
    printf("%d\n",q->data);
    //go to right child
    inorder(q->right);
  }
  
  return;
}

コードの実行結果