탐색이진트리를 구현 해 보았습니다
#include<stdio.h>
#include<stdlib.h>
typedef struct Node{
int data;
struct Node * L;
struct Node * R;
}Node;
// 노드를 생성하는 함수
// 중복되는 값은 오른쪽으로 보낸다.
Node * Node_add(Node * root, int data){
if(root==NULL){
root=(Node*)malloc(sizeof(Node));
root->data=data;
root->L=NULL;
root->R=NULL;
}
else if(root->data>data){
root->L=Node_add(root->L,data);
}
else{
root->R=Node_add(root->R,data);
}
return root;
}
//노드들을 출력해주는 함수
void Node_display(Node * root){
if(root!=NULL){
if(root->L!=NULL){
Node_display(root->L);
}
printf("%d\n",root->data);
if(root->R!=NULL){
Node_display(root->R);
}
}
}
// 해당하는 값을 가진 노드를 하나 제거하는 함수
// 중복되는 값이 있을경우도 마찬가지로 하나만 제거한다.
Node * Node_delete(Node * root, int data){
Node * remove=NULL; //free함수를 사용하여 실제로 제거할 노드를 가르키는 포인터.
if(root!=NULL){
if(root->data==data){
remove=root;
if(remove->L!=NULL&&remove->R==NULL){ // 제거해야하는 노드의 오른쪽이 없을경우.
root=root->L;
free(remove);
remove=NULL;
return root;
}
else if(remove->L==NULL&&remove->R!=NULL){ //제거해야하는 노드의 왼쪽이 없을경우.
root=root->R;
free(remove);
remove=NULL;
return root;
}
else if(remove->L!=NULL&&remove->R!=NULL){ //제거해야하는 노드의 양쪽 전부 노드가 있을경우.
Node * add=remove->R; //오른쪽 값들중에서 최소값을 가르키기위한 포인터.
Node * connect=add; //최소값을 가저갈때 남은 자리를 이어주기위한 포인터.
if(add->L!=NULL){ //제거해야하는 노드중에 오른쪽중에서 최소값을 찾아주고 제거하는 부분.
while(add->L->L!=NULL){
connect=add;
add=add->L;
}
add=add->L;
connect->L=connect->L->R;
root=add;
add->L=remove->L;
add->R=remove->R;
free(remove);
remove=NULL;
return root;
}
else{
root=add;
add->L=remove->L;
free(remove);
remove=NULL;
return root;
}
}
else{ //제거해야하는 노드의 양쪽 전부 노드가 없을경우.
root=NULL;
free(remove);
remove=NULL;
return root;
}
}
if(root->L!=NULL){ //해당 노드가 제거해야하는 값이 아닌경우 왼쪽 검색.
root->L=Node_delete(root->L,data);
}
if(root->R!=NULL){ //해당 노드가 제거해야하는 값이 아닌경우 오른쪽 검색.
root->R=Node_delete(root->R,data);
}
}
return root;
}
int main(){
Node * root=NULL;
int choice,value;
while(1){
printf("1번 노드 추가 2번 노드 출력 3삭제");
scanf("%d",&choice);
switch(choice){
case 1: printf("값 입력 :");
scanf("%d",&value);
root=Node_add(root,value);
break;
case 2: Node_display(root);
break;
case 3: printf("값 입력 :");
scanf("%d",&value);
root=Node_delete(root,value);
break;
}
}
}
이진트리의 특성인 중위순회를 하였을때 정렬이되는 특징을 살려 만들어 보았습니다.
사실 노드를 만드는부분에서 재귀함수를 사용하는부분은 원래 다른사람의 코드를 참고하려하지 않으려했으나
(저는 다른사람의 코드를 보고 비슷하게나 또는 똑같이 만드는것이 아닌 제가 직접 만들수있게되는 실력을 원하기때문에)
개념을 공부하던도중 순간적으로 보게되어 재귀함수를 사용하게 되었습니다 아마도 재귀함수를 보지않았다면 여러번에 걸처 반복문과 조건문이 난무하는 지저분한 코드가 되었을 것입니다 ( 첫날 개념을 공부하기전 상상만으로 코드를 얼추 생각했을대 머릿속에서는 반복문과 조건문을 반복하여 사용하는 법을 생각했습니다)
하지만 노드를 생성하는 부분을 제외하고는 개념만 따로 공부하고직접 코드를 구현하였기에 그나마 다행이라고 생각하고있습니다.