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

이진트리 알고리즘이다. 그림을 잘 못그려서 대충 그렸다.

            [1]

       [2]        [3]

     

  [4]      [5]

[1]은 루트노드이다. [1]의 왼쪽에는 [2]노드, 오른쪽에는 [3]노드가 있다.

[2]는 [4] [5]의 부모노드이며 [4] [5]는 [2] 노드의 자식노드이다.

노드의 모양은 아래와 같다.

            [2]                     [1]                    [3]

     [left][num][right] <- [left][num][right] -> [left][num][right]

           [4]                     [2]                    [5]

     [left][num][right] <- [left][num][right] -> [left][num][right]

main.c

#include <stdio.h>

#include "tree.h"

int main(){

struct data *p1 = make();

struct data *p2 = make();

struct data *p3 = make();

struct data *p4 = make();

struct data *p5 = make();

// 노드를 생성해주는 부분이다. 5개의 노드를 생성하자

setdata(p1, 1);

setdata(p2, 2);

setdata(p3, 3);

setdata(p4, 4);

setdata(p5, 5);

// 노드에 데이터를 넣어주는 부분이다.

makeleftsub(p1, p2);

makerightsub(p1, p3);

makeleftsub(p2, p4);

makerightsub(p2, p5);

//  노드와 노드를 연결해주는 부분이다.

printf("%d \n", getdata(getleftsub(p1)));

printf("%d \n", getdata(getleftsub(getleftsub(p1))));

printf("%d \n", getdata(getrightsub(getleftsub(p1))));

// 노드를 출력한다.

return 0;

}

tree.c

#include <stdio.h>

#include <stdlib.h>

#include "tree.h"

struct data *make(void){

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

node->left = NULL;  // 노드의 왼쪽에 NULL을 넣는다.

node->right = NULL;  // 노드의 오른쪽에 NULL을 넣는다.

return node;  // malloc 주소를 반환한다.

}

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;  // 비운 곳에 b를 넣는다.

}

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

if (a->right != NULL){  // 노드의 오른쪽이 비어있지 않다면 비운다.

a->right = NULL;

}

a->right = b;  // 비운 곳에 b를 넣는다.

}

int getdata(struct data *a){

return a->num;  // 받은 노드를 출력한다.

}

struct data *getleftsub(struct data *a){

return a->left;  // 노드의 왼쪽 노드를 반환한다.

}

struct data *getrightsub(struct data *a){

return a->right;  // 노드의 오른쪽 노드를 반환한다.

}

tree.h

struct data{

struct data *left;

struct data *right;

int num;

};

struct data *make(void);

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

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

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

int getdata(struct data *a);

struct data *getleftsub(struct data *a);

struct data *getrightsub(struct data *a);