[자료구조] 이진 트리

 

1. 자료구조
   1. 연결 리스트
   2. 이진 트리
   3. 스택
   4. 큐
   5. 해시
2. 정렬
   1. 버블 정렬
   2. 선택 정렬
   3. 삽입 정렬
   4. 퀵 정렬
   5. 힙 정렬
3. 알고리즘
   1. 재귀 함수
   2. 너비 우선탐색(BFS)
   3. 깊이 우선탐색(DFS)
   4. 다익스트라

---

 

이진트리(Binary Tree)

 

각 노드의 구조

 

 

이전에 배웠던 연결 리스트는 각 노드에 Data와 다음 노드를 가리키는 포인터변수가 있었다.

하지만 이진트리는 각 노드에 Data와 왼쪽, 오른쪽 노드를 가리키는 포인터변수가 있는 구조로 되어있다.

또한 같은 깊이에 있는 노드들을 Level이라고 한다.

 

---

 

이진트리 삽입

 

이진트리 삽입 방법

 

1. 첫 노드는 그냥 입력한다.
2. 첫 노드(Root)를 시작으로 각 노드와 비교하여 작으면 왼쪽, 크면 오른쪽 노드로 간다.
3. 노드가 NULL이면 입력한다. NULL이 아니면 "2번"으로 간다.
4. 2번과 3번을 반복한다.

 

---

 

이진트리 삭제

 

자식 노드가 없는 경우

 

1. 삭제할 노드를 가리키는 포인트 변수에 NULL값을 넣는다.
2. 노드를 삭제한다.

 

 

오른쪽 노드 or 왼쪽 노드만 있는 경우

오른쪽 노드만 있는 경우

 

왼쪽 노드만 있는 경우

 

1. 삭제할 노드를 가리키는 포인트 변수에 삭제할 노드의 자식 노드의 포인트는 넣어준다.
2. 노드를 삭제한다.

 

 

둘 다 있는 경우

 

1. 삭제할 노드의 왼쪽 자식 노드를 기준으로 가장 큰 값을 찾는다.
2. 찾은 노드의 값을 삭제할 노드의 값에 넣어준다.
3. 찾은 노드를 삭제한다.

 

---

 

소스 코드

#define __main

#ifdef __main

#include <stdio.h>

typedef struct __node {
	struct __node* right;
	struct __node* left;

	int data;
} Node;

void SetNode(Node* n, Node* right, Node* left, int data) {
	n->data = data;
	n->right = right;
	n->left = left;
}

void Insert(Node* n, int data) {
	if (n->data > data) {
		if (n->left == NULL) {
			Node* node = malloc(sizeof(Node));

			SetNode(node, NULL, NULL, data);
			n->left = node;
		}
		else Insert(n->left, data);
	}
	else if (n->data < data) {
		if (n->right == NULL) {
			Node* node = malloc(sizeof(Node));

			SetNode(node, NULL, NULL, data);
			n->right = node;
		}
		else Insert(n->right, data);
	}
	else printf("%d is registered\n", data);
}

void Remove(Node* n, int data) {
	if (n == NULL) printf("Error : No data\n"); return 0;

	Node* node = n;
	Node* before_node = n;

	int dir = 0;

	while (1) {
		if (node == NULL) {
			// 일치하는 값 없음
			printf("Error : No data\n");
			return 0;
		}
		else if (node->data > data) {
			// 작으면 왼쪽 노드로
			before_node = node;
			node = node->left;
			dir = 0;
		}
		else if (node->data < data) {
			// 크면 오른쪽 노드로
			before_node = node;
			node = node->right;
			dir = 1;
		}
		else if (node->data == data) break; // 일치한 값을 찾음
	}

	if (node->right == NULL && node->left == NULL) {
		// 자식 노드가 모두 없는 경우
		dir ? (before_node->left = NULL) : (before_node->right = NULL);
		free(node);
	}
	else if (node->right == NULL) {
		// 왼쪽 노드만 없는 경우
		dir ? (before_node->left = node->right) : (before_node->right = node->right);
		free(node);
	}
	else if (node->left == NULL) {
		// 오른쪽 노드만 없는 경우
		dir ? (before_node->left = node->left) : (before_node->right = node->left);
		free(node);
	}
	else {
		// 자식노드가 모두 있는 경우
		Node* tmp = node->left;
		before_node = node;

		// 왼쪽 노드중 가장 큰 값을 찾기
		while (tmp->right != NULL) {
			before_node = tmp;
			tmp = tmp->right;
		}

		node->data = tmp->data;
		Remove(node->left, node->data);
	}
}

void clear(Node* node) {
	// 모든 노드 삭제
	if (node != NULL) {
		clear(node->left);
		clear(node->right);
		free(node);
	}
}

int main() {
	Node* node = malloc(sizeof(Node));

	SetNode(node, NULL, NULL, 9);

	Insert(node, 5);
	Insert(node, 10);
	Insert(node, 1);
	Insert(node, 7);
	Insert(node, 11);
	Insert(node, 0);
	Insert(node, 6);
	Insert(node, 8);

	clear(node);

	return 0;
}

#endif