[자료구조] 이진트리탐색 알고리즘

이진트리와 비슷하지만 삽입 탐색 삭제가 있는 형태이다.

이진트리+스택or큐가 합쳐진 것같은 느낌이다.

이진트리 알고리즘을 정확히 이해해야한다.

main.c

#include <stdio.h>

#include "tree.h"

int main(){

struct data *node;

struct data *s;

init(&node); 

 // 노드를 NULL로 초기화

insert(&node, 5);  

insert(&node, 1);

insert(&node, 3);

insert(&node, 4);

// 노드 삽입

inorder(node);

printf("\n");

s = remove1(&node, 4);

free(s);

inorder(node);

printf("\n");

// 노드의 삭제 후 출력

return 0;

}

tree.c

#include <stdio.h>

#include <stdlib.h>

#include "tree.h"

void init(struct data **a){

*a = NULL;  // *a는 main문의 node를 가리키고 있다. 초기화한다.

}

void insert(struct data **a, int num){

struct data *c = *a;  // 처음에 c에는 null이 담긴 node가 들어온다.

struct data *p = NULL;  // p는 c의 부모노드이다. 노드의 위치를 형성하는 중요한 역할을 한다.

struct data *n = NULL;  // n은 newnode의 약자로 새로운 노드를 뜻한다. 삽입한다.

while (c != NULL){  // c가 null이 일때까지 노드를 탐색하지만 결과적으로 아래에 쓰일 p의 위치선정이다.

if (getdata(c) == num){  // 노드의 키값은 중복되며 안되므로 삽입할 수가 같다면 걸러준다.

return;

}

p = c;  // c를 p에 넣는 이유는 while문을 벗어나면 p가 부모노드고 c가 자식노드가 되기 위해

if (getdata(c) > num){  // c가 삽입할 수보다 크면 왼쪽 노드를 가리킨다.

c = getleftsub(c);  // 왼쪽 노드가 null이라면 벗어나고 아니라면 계속 while문을 진행한다.

}

else{

c = getrightsub(c);

}

}

n = make();

setdata(n, num);  // 새로운 노드를 n에 삽입한다.

if (p != NULL){  // p로써 n의 위치를 지정한다.

if (getdata(p) > num){  // p가 크다면 num이 들어있는 n은 p의 왼쪽에 위치한다.

makeleftsub(p, n);

}

else{

makerightsub(p, n);

}

}

else{

*a = n;  // 초기에 p와 n이 null일때 루트노드가 *a에 위치하게 된다.

}

}

struct data *remove1(struct data **a, int num){

struct data *v = make();  // v의 역할은 루트노드의 주소를 저장할 가상노드이다.

struct data *p = v;   

struct data *c = *a;  

struct data *del;  // 삭제할 노드

changerightsub(v, *a);  // 가상 노드의 오른쪽에 루트노드를 위치시킨다.

while (c != NULL && getdata(c) != num){  

// 일반적인 경우는 c의 값과 num이 일치하여 종료

// 비정상인 경우는 c가 탐색하지 못하여 null 반환하여 종료

p = c;

if (getdata(c) > num){  // c는 num보다 크면 왼쪽노드를 탐색

c = getleftsub(c);

}

else{

c = getrightsub(c);

}

}

if (c == NULL){  // 찾는 수가 없었기에 종료한다.

return NULL;

}

del = c;  // 이때 삭제할 노드는 c에 있으며 c의 부모노드는 p이다.

// 삭제할 노드가 단말노드일 경우

if (getleftsub(del) == NULL && getrightsub(del) == NULL){  // 삭제할 노드에 왼쪽 오른쪽 노드가 없을 때

if (getleftsub(p) == del){  // 부모 노드의 왼쪽이 삭제할 노드라면

removeleftsub(p);  // 부모 노드의 왼쪽 노드를 삭제한다.

}

else{  // 아니라면 오른쪽 노드를 삭제한다.

removerightsub(p);

}

}

// 삭제할 노드가 1개의 자식 노드를 가질 때

else if (getleftsub(del) == NULL || getrightsub(del) == NULL){  // 둘 중 하나가 null이란 것은 하나는 노드가 있다는 뜻

struct data *delc;  // 삭제할 노드의 자식노드

if (getleftsub(del) != NULL){  // 삭제할 노드의 왼쪽노드가 null이 아니라는건 노드가 있다는 뜻이다.

delc = getleftsub(del);  // 그 노드를 delc에 저장한다.

}

else{  // 삭제할 노드의 오른쪽에 노드가 있다면 그것을 delc에 저장한다.

delc = getrightsub(del);

}

if (getleftsub(p) == del){  // 부모 노드의 왼쪽에 삭제할 노드가 있다면

changeleftsub(p, delc);  // 삭제할 노드는 무시해버리고 부모 노드의 왼쪽에 삭제할 노드의 자식 노드를 연결한다.

}

else{

changerightsub(p, delc);

}

}

// 삭제할 노드가 2개의 자식 노드를 가질 때

else{

struct data *mp = del;  // mp는 m의 부모노드이다. 그리고 삭제할 노드이다.

struct data *m = getrightsub(del);  // 삭제할 노드의 오른쪽 자식이 m이다.

int delnum; // 삭제할 노드의 키값을 담을 변수

// 자식 노드가 2개일 때의 핵심은 del의 오른쪽 노드를 중심으로 왼쪽에서 가장 작은 값과 del 노드를 바꿔줄 것인가

// del의 오른쪽 노드의 왼쪽에 노드가 없다면 오른쪽에서 가장 첫번째 만나는 노드와 del 노드를 바꿔줄 것인가 이다.

while (getleftsub(m) != NULL){    // del의 오른쪽 자식노드를 중심으로 왼쪽 노드에서 가장 작은 수를 찾는다.

mp = m;

m = getleftsub(m);

}

// 이 while문이 끝나면 mp는 가장 작은 수의 부모노드가 되고 m은 가장 작은 수를 가진 노드가 된다.

delnum = getdata(del);  // del이 바뀌기전에 미리 del의 값을 저장해둔다.

setdata(del, getdata(m));  // del에 m의 키값을 저장한다?

// del의 오른쪽 자식노드의 왼쪽에 가장 작은수 or del의 오른쪽 노드의 키값을 del에 저장한다.

if (getleftsub(mp) == m){  // 결국 mp의 왼쪽에 m이 있단 뜻은 del의 오른쪽 자식노드의 왼편에 있냐는 뜻이다.

changeleftsub(mp, getrightsub(m));  // 그렇다면 가장 작은수의 부모노드의 왼쪽에 null을 연결해준다.

}

else{  // mp의 왼쪽에 아무것도 없다는건 오른쪽 노드란거다.

changerightsub(mp, getrightsub(m));  // mp는 del이므로 여기다가 del의 오른쪽 자식노드의 오른쪽 자식노드를 연결. 

}

del = m;  // m은 del의 오른쪽노드의 왼쪽의 가장 작은노드 or del의 오른쪽 노드이다. 그걸 삭제해주는거다.

setdata(del, delnum);  // 삭제할 노드에 delnum은 애초에 삭제할 노드였던 del의 키값을 넣는다.

}

// 결국 처음에 지우려던 del은 지우지 않고 키값만 바꾼 것이다.

// del 노드의 오른쪽 노드의 왼쪽에서 가장 작은 노드의 키값 or del 노드의 오른쪽 노드의 키값으로.

// 그 후에 가장 작은 노드 or del 노드의 오른쪽 노드는 del에 넣고 해제한다.

// 가장 작은 노드에는 null을 넣고 다시 부모노드와 연결함 or

// del의 오른쪽 노드였던 경우는 del노드의 오른쪽에 원래있던 오른쪽 노드를 해제하고 del의 오른쪽 노드의 오른쪽 노드를 연결한다.

if (*a != getrightsub(v)){  // 다르다는 뜻은 루트노드가 삭제됐을 경우이므로 이를 대비하여 가상노드와 연결하도록 만들었다.

*a = getrightsub(v);

}

free(v);

return del;  // del을 반환해서 free로 해제한다.

}

struct data *search(struct data *a, int num){

struct data *node = a;

int cd;

while (node != NULL){  // node가 null이 나올때까지 진행한다.

cd = getdata(node); // cd는 루트노드부터 시작된다.

if (cd == num){  // 노드의 값과 찾고자 하는 값이 같다면 노드를 반환한다.

return node;

}

else if (cd > num){  // 노드의 값이 더 크다면 num은 그 노드의 왼쪽에 있다.

node = getleftsub(node);  // 왼쪽으로 이동하고 null이 아니라면 반복

}

else{

node = getrightsub(node);

}

}

return NULL;

}

void changeleftsub(struct data *a, struct data *b){

a->left = b;  // a의 왼쪽에 b 노드를 위치시킨다.

}

void changerightsub(struct data *a, struct data *b){

a->right = b;  // a의 오른쪽에 b 노드를 위치시킨다.

}

struct data *removeleftsub(struct data *a){

struct data *del;

if (a != NULL){  

del = a->left;  // 노드의 왼쪽을 비워준다.

a->left = NULL;

}

return del;

}

struct data *removerightsub(struct data *a){

struct data *del;

if (a != NULL){

del = a->right;  // 노드의 오른쪽을 비워준다.

a->right = NULL;

}

return del;

}

struct data *make(void){

struct data *node = (struct data*)malloc(sizeof(struct data));  // 동적할당한다.

node->left = NULL;

node->right = NULL;

return node;  // 동적할당한 노드를 반환한다.

}

int getdata(struct data *a){

return a->num;  // 노드의 num 반환

}

void setdata(struct data *a, int num){

a->num = num;  // 노드의 num 삽입

}

void makeleftsub(struct data *a, struct data *b){

if (a->left != NULL){

a->left = NULL;

}

a->left = b;  // a 노드의 왼쪽에 b 삽입

}

void makerightsub(struct data *a, struct data *b){

if (a->right != NULL){

a->right = NULL;

}

a->right = b;  // a 노드의 오른쪽에 b 삽입

}

struct data *getleftsub(struct data *a){

return a->left;  // a 노드의 왼쪽 노드 가리킴

}

struct data *getrightsub(struct data *a){

return a->right;  // a 노드의 오른쪽 노드 가리킴

}

void inorder(struct data *a){

if (a == NULL){

return;

}

inorder(a->left);  // 부모노드의 왼쪽 노드를 탐색한다.

printf("%d ", a->num); // 중위탐색 때문에 출력이 중앙에 위치함

inorder(a->right);  // 부모노드의 오른쪽 노드를 탐색한다.

}

tree.h

struct data{

int num;  // 노드가 가진 키값

struct data *left;  // 노드의 왼쪽

struct data *right;  // 노드의 오른쪽

};

void init(struct data **a);  // 노드의 초기화

void insert(struct data **a, int num);   // 노드 삽입

struct data *remove1(struct data **a, int num);  // 노드 삭제

struct data *search(struct data *a, int num);  // 노드 탐색

void changeleftsub(struct data *a, struct data *b);  // 노드의 왼쪽 이동

void changerightsub(struct data *a, struct data *b);  // 노드의 오른쪽 이동

struct data *removeleftsub(struct data *a);  // 왼쪽 노드 삭제

struct data *removerightsub(struct data *a);  // 오른쪽 노드 삭제

struct data *make(void);  // 노드 동적 할당

int getdata(struct data *a);  // 노드의 안에있는 num 출력

void setdata(struct data *a, int num);  // 노드에 num을 삽입

void makeleftsub(struct data *a, struct data *b);  // a 노드의 왼쪽에 b를 삽입

void makerightsub(struct data *a, struct data *b);  // a 노드의 오른쪽에 b를 삽입

struct data *getleftsub(struct data *a);  // a의 왼쪽 노드를 가리킴

struct data *getrightsub(struct data *a);  // a의 오른쪽 노드를 가리킴

void inorder(struct data *a);  // 중위 순서로 출력함