이분목 탐색
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;
}
코드 실행 결과
Reference
이 문제에 관하여(이분목 탐색), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://qiita.com/sabewe/items/686ae51a7a4d2c669335
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
이진 트리는 숫자가 작은 노드가 왼쪽 노드로 저장되고 숫자가 큰 노드가 오른쪽 노드로 저장됩니다. 이 논리를 바탕으로 탐색 프로그램을 구성합니다.
탐색 이미지
■ 탐색 결과가 있는 경우
■ 탐색 결과가 없는 경우
코드
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;
}
코드 실행 결과
Reference
이 문제에 관하여(이분목 탐색), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://qiita.com/sabewe/items/686ae51a7a4d2c669335
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
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;
}
코드 실행 결과
Reference
이 문제에 관하여(이분목 탐색), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://qiita.com/sabewe/items/686ae51a7a4d2c669335
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
Reference
이 문제에 관하여(이분목 탐색), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://qiita.com/sabewe/items/686ae51a7a4d2c669335텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)