이분목 탐색

13630 단어 C

탐색 대상의 이분목





탐색 로직



이진 트리는 숫자가 작은 노드가 왼쪽 노드로 저장되고 숫자가 큰 노드가 오른쪽 노드로 저장됩니다. 이 논리를 바탕으로 탐색 프로그램을 구성합니다.

탐색 이미지



■ 탐색 결과가 있는 경우


■ 탐색 결과가 없는 경우


코드



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


코드 실행 결과



좋은 웹페이지 즐겨찾기