printf("ho_tari\n");
C언어(9) 본문
2025.02.28
연결리스트의 응용 : 다항식
- 다항식을 컴퓨터로 처리하기 위한 자료구조
- 하나의 다항식을 하나의 연결리스트로 표현
다항식의 덧셈 구현
- 2개의 다항식을 더하는 덧셈 연산 구현
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct ListNode {
int coef; // 계수
int expon; // 지수
struct ListNode* link;
} ListNode;
// 연결 리스트 헤더
typedef struct ListType {
int size;
ListNode* head;
ListNode* tail;
} ListType;
// 오류 메시지를 출력하는 함수
void error(char* message) {
fprintf(stderr, "%d\n", message); // 메시지 출력
exit(1); // 프로그램 종료
}
// 리스트 헤더를 생성하는 함수
ListType* create() {
ListType* plist = (ListType*)malloc(sizeof(ListType));
plist->size = 0;
plist->head = plist->tail = NULL;
return plist;
}
void insert_last(ListType* plist, int coef, int expon) {
// 동적 메모리 할당
ListNode* temp = (ListNode*)malloc(sizeof(ListNode));
if (temp == NULL) error("메모리 할당 실패");
temp->coef = coef; // 계수 저장
temp->expon = expon; // 지수 저장
temp->link = NULL; // 다음 노드 링크 없음
if (plist->tail == NULL)
{
// 기존 노드가 없으면
plist->head = plist->tail = temp; // 헤드와 꼬리 모두 temp로 설정
}
else
{
// 기존 노드가 있으면
plist->tail->link = temp; // 꼬리의 링크를 temp로 설정
plist->tail = temp; // 꼬리를 temp로 설정
}
plist->size++; // 전체 카운트 1 증가
}
// list3 = list1 + list2
void poly_add(ListType* plist1, ListType* plist2, ListType* plist3) {
ListNode* a = plist1->head;
ListNode* b = plist2->head;
int sum;
while (a && b) // a, b 모두 NULL이 아니면
{
if (a->expon == b->expon) // a, b의 지수가 동일하면
{
sum = a->coef + b->coef; // a의 계수를 더하여 sum에 저장
if (sum != 0) insert_last(plist3, sum, a->expon); // plist3에 결과 노드 추가
a = a->link; // a 리스트의 다음 노드 선택
b = b->link; // b 리스트의 다음 노드 선택
}
else if (a->expon > b->expon) // 두개의 지수 중 a > b인 경우
{
insert_last(plist3, a->coef, a->expon); // plist3에 a의 값을 추가
a = a->link; // a 리스트의 다음 노드 선택
}
else // 두개의 지수 중 a < b인 경우
{
insert_last(plist3, b->coef, b->expon); // plist3에 b의 값을 추가
b = a->link; // b 리스트의 다음 노드 선택
}
}
// a, b 중에서 하나가 먼저 끝나면 남아있는 리스트의 나머지 항들을 모두 plist3에 복사
for (; a != NULL; a = a->link)
{
insert_last(plist3, a->coef, a->expon);
}
for (; b != NULL; b = b->link)
{
insert_last(plist3, b->coef, b->expon);
}
}
// 다항식 인쇄
void poly_print(ListType* plist) {
ListNode* p = plist->head;
printf("Polynomial = ");
for (; p; p = p->link)
{
printf("%d^%d + ", p->coef, p->expon);
}
/*while (p != NULL)
{
printf("%d^%d + ", p->coef, p->expon);
p = p->link;
}*/
printf("\n");
}
int main(void) {
ListType* list1, * list2, * list3;
// 연결 리스트 생성
list1 = create();
list2 = create();
list3 = create();
// 다항식 1을 생성
insert_last(list1, 3, 12);
insert_last(list1, 2, 8);
insert_last(list1, 1, 0);
// 다항식 2을 생성
insert_last(list2, 8, 12);
insert_last(list2, -3, 10);
insert_last(list2, 10, 6);
poly_print(list1);
poly_print(list2);
// 다항식3 = 다항식1 + 다항식2
poly_add(list1, list2, list3);
poly_print(list3);
// 메모리 해제
free(list1);
free(list2);
free(list3);
return 0;
}
원형 연결 리스트
- 마지막 노드의 링크가 첫 번째 노드를 가리키는 리스트
- 한 노드에서 다른 모든 노드로의 접근이 가능
- 보통 헤드포인터가 마지막 노드를 가리키게끔 구성하면 리스트의 처음이나 마지막에 노드를 삽입하는 연산이 단순 연결 리스트에 비해 용이
원형 연경 리스트 구현 (숫자 저장)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef int element;
typedef struct ListNode {
element data;
struct ListNode* link;
} ListNode;
// 리스트 항목 인쇄
void print_list(ListNode* head) {
ListNode* p;
if (head == NULL) return;
p = head->link;
do {
printf("%d->", p->data);
p = p->link;
} while (p != head);
printf("%d->", p->data); // 마지막 노드 인쇄
}
// 앞에 노드 추가
ListNode* insert_first(ListNode* head, element data) {
ListNode* node = (ListNode*)malloc(sizeof(ListNode)); // 노드 생성
node->data = data; // 생성된 노드에 데이터 할당
if (head == NULL) // 기존 노드가 없는 경우
{
head == node; // 헤드를 자신으로
node->link = head; // 자신의 링크를 자신으로
}
else // 기존 노드가 존재하는 경우
{
node->link = head->link; // 헤드가 가진 링크를 자신의 링크로 복사
head->link = node; // 헤드의 링크를 자신의 주소로 할당
}
return head;
}
// 뒤에 노드 추가
ListNode* insert_last(ListNode* head, element data) {
ListNode* node = (ListNode*)malloc(sizeof(ListNode)); // 노드 생성
node->data = data; // 생성된 노드에 데이터 할당
if (head == NULL) // 기존 노드가 없는 경우
{
head = node; // 헤드를 자신으로
node->link = head; // 자신의 링크를 자신으로
}
else // 기존 노드가 존재하는 경우
{
node->link = head->link; // 헤드가 가진 링크를 자신의 링크로 복사
head->link = node; // 헤드의 링크를 자신의 주소로 할당
head = node; // 노드를 헤드로 복사
}
return head;
}
int main(void) {
ListNode* head = NULL;
// list = 10->20->30->40
head = insert_last(head, 20);
head = insert_last(head, 30);
head = insert_last(head, 40);
head = insert_first(head, 10);
print_list(head);
return 0;
}
원형 연경 리스트 구현 (숫자 저장)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// typedef int element; // 정수 저장용 형식 정의
// 문자열 저장용 형식 정의
typedef char element[80];
typedef struct ListNode {
element data;
struct ListNode* link;
} ListNode;
// 리스트 항목 인쇄
void print_list(ListNode* head) {
ListNode* p;
if (head == NULL) return;
p = head->link;
do {
// printf("%d->", p->data);
printf("%s->", p->data);
p = p->link;
} while (p != head);
// printf("%d->", p->data); // 마지막 노드 인쇄
printf("%s->", p->data);
}
// 앞에 노드 추가
ListNode* insert_first(ListNode* head, element data) {
ListNode* node = (ListNode*)malloc(sizeof(ListNode)); // 노드 생성
// node->data = data; // 생성된 노드에 데이터 할당
strcpy(node->data, data);
if (head == NULL) // 기존 노드가 없는 경우
{
head == node; // 헤드를 자신으로
node->link = head; // 자신의 링크를 자신으로
}
else // 기존 노드가 존재하는 경우
{
node->link = head->link; // 헤드가 가진 링크를 자신의 링크로 복사
head->link = node; // 헤드의 링크를 자신의 주소로 할당
}
return head;
}
// 뒤에 노드 추가
ListNode* insert_last(ListNode* head, element data) {
ListNode* node = (ListNode*)malloc(sizeof(ListNode)); // 노드 생성
// node->data = data; // 생성된 노드에 데이터 할당
strcpy(node->data, data);
if (head == NULL) // 기존 노드가 없는 경우
{
head = node; // 헤드를 자신으로
node->link = head; // 자신의 링크를 자신으로
}
else // 기존 노드가 존재하는 경우
{
node->link = head->link; // 헤드가 가진 링크를 자신의 링크로 복사
head->link = node; // 헤드의 링크를 자신의 주소로 할당
head = node; // 노드를 헤드로 복사
}
return head;
}
int main(void) {
ListNode* head = NULL;
element data;
// list = 10->20->30->40
head = insert_last(head, "apple");
head = insert_last(head, "kiwi");
head = insert_last(head, "orange");
head = insert_first(head, "strawberry");
print_list(head);
return 0;
}
이중 연결 리스트
- 하나의 노드가 선행 노드와 후속 노드에 대한 두 개의 링크를 가지는 리스트
- 단점은 공간을 많이 차지하고 코드가 복잡
헤드 노드
- 데이터를 가지지 않고 단지 삽입, 삭제 코드를 간단하게 할 목적으로 만들어진 노드
- 헤드 포인터와 구별 필요
- 공백 상태에서는 헤드 노드만 존재
이중 연결 리스트 구현 예제
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef int element;
typedef struct DListNode {
element data;
struct DListNode* llink; // 선행 노드 링크
struct DListNode* rlink; // 후행 노드 링크
} DListNode;
// 이중 연결 리스트 초기화
void init(DListNode* phead) {
phead->llink = phead;
phead->rlink = phead;
}
// 이중 연결 리스트의 노드를 인쇄
void print_dlist(DListNode* phead) {
DListNode* p;
// p가 최초 위치인 phead에 도달할 때까지 반복
for (p = phead->rlink; p != phead; p = p->rlink)
{
printf("<-| |%d| |->", p->data);
}
printf("\n");
}
// 새로운 데이터를 노드 before의 오른쪽에 삽입
void dinsert(DListNode* before, element data) {
DListNode* newnode = (DListNode*)malloc(sizeof(DListNode));
newnode->data = data; // 새로운 노드에 값 저장
newnode->llink = before; // 새로운 노드의 선행 링크를 before의 주소로 할당
newnode->rlink = before->rlink; // 새로운 노드의 후행 링크를 before가 가진 후행 링크에서 복사
before->rlink->llink = newnode; // before의 후행 링크에서 보유한 선행 링크의 주소를 새로운 노드의 주소로 할당
before->rlink = newnode; // before의 후행 링크를 새로운 노드의 주소로 할당
}
// removed로 입력된 노드를 삭제
void ddelete(DListNode* head, DListNode* removed) {
if (removed == head) return; // 헤드는 삭제 불가
// 삭제될 노드가 가진 선행 링크의 후행 링크값을 삭제될 노드의 후행 링크값에서 복사
removed->llink->rlink = removed->rlink;
// 삭제될 노드가 가진 후행 링크의 선행 링크값을 삭제될 노드의 선행 링크값에서 복사
removed->rlink->llink = removed->llink;
free(removed);
}
// 이중 연결 리스트 테스트
int main(void) {
DListNode* head = (DListNode*)malloc(sizeof(DListNode));
init(head);
printf("노드 추가\n");
for (int i = 0; i < 5; i++)
{
dinsert(head, i);
print_dlist(head);
}
printf("노드 삭제\n");
for (int i = 0; i < 5; i++)
{
print_dlist(head);
ddelete(head, head->rlink);
}
free(head);
return 0;
}
음악 재생 목록 구현 예제
doubly_linked_list.h 헤더파일
#pragma once
#ifndef __doubly_linked_list_h__
#define __doubly_linked_list_h__
#define USE_STRING
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#ifdef USE_STRING
typedef char element[80];
#else
typedef int element;
#endif
typedef struct DListNode {
element data;
struct DListNode* llink; // 선행 노드 링크
struct DListNode* rlink; // 후행 노드 링크
} DListNode;
void init(DListNode* phead);
void print_dlist(DListNode* phead);
void dinsert(DListNode* before, element data);
void ddelete(DListNode* head, DListNode* removed);
#endif
doubly_linked_list.c 파일
#include "doubly_linked_list.h"
// 이중 연결 리스트 초기화
void init(DListNode* phead) {
phead->llink = phead;
phead->rlink = phead;
}
// 이중 연결 리스트의 노드를 인쇄
void print_dlist(DListNode* phead) {
DListNode* p;
// p가 최초 위치인 phead에 도달할 때까지 반복
for (p = phead->rlink; p != phead; p = p->rlink)
{
#ifdef USE_STRING
printf("<-| |%s| |->", p->data);
#else
printf("<-| |%d| |->", p->data);
#endif
}
printf("\n");
}
// 새로운 데이터를 노드 before의 오른쪽에 삽입
void dinsert(DListNode* before, element data) {
DListNode* newnode = (DListNode*)malloc(sizeof(DListNode));
#ifdef USE_STRING
strcpy(newnode->data, data);
#else
newnode->data = data; // 새로운 노드에 값 저장
#endif
newnode->llink = before; // 새로운 노드의 선행 링크를 before의 주소로 할당
newnode->rlink = before->rlink; // 새로운 노드의 후행 링크를 before가 가진 후행 링크에서 복사
before->rlink->llink = newnode; // before의 후행 링크에서 보유한 선행 링크의 주소를 새로운 노드의 주소로 할당
before->rlink = newnode; // before의 후행 링크를 새로운 노드의 주소로 할당
}
// removed로 입력된 노드를 삭제
void ddelete(DListNode* head, DListNode* removed) {
if (removed == head) return; // 헤드는 삭제 불가
// 삭제될 노드가 가진 선행 링크의 후행 링크값을 삭제될 노드의 후행 링크값에서 복사
removed->llink->rlink = removed->rlink;
// 삭제될 노드가 가진 후행 링크의 선행 링크값을 삭제될 노드의 선행 링크값에서 복사
removed->rlink->llink = removed->llink;
free(removed);
}
main.c 파일
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "doubly_linked_list.h"
DListNode* current; // 현재 재생중인 노드
void print_dlist2(DListNode* phead) {
DListNode* p;
// p가 최초 위치인 phead에 도달할 때까지 반복
for (p = phead->rlink; p != phead; p = p->rlink)
{
if (p == current)
{
printf("<-| #%s# |->", p->data);
}
else
{
printf("<-| |%s| |->", p->data);
}
}
printf("\n");
}
int main(void) {
char ch;
DListNode* head = (DListNode*)malloc(sizeof(DListNode));
init(head);
dinsert(head, "맘마미아");
dinsert(head, "댄싱퀸");
dinsert(head, "페르난도");
current = head->rlink;
do {
printf("\n명령어를 입력하시오(<, >, q): ");
ch = getchar();
if (ch == '<') // 이전곡
{
current = current->llink; // 선행 링크로 이동
if (current == head) // 이동한 링크가 헤더인 경우
{
current = current->llink; // 헤더의 선행 링크로 이동
}
}
else if (ch == '>') // 다음곡
{
current = current->rlink; // 후행 링크로 이동
if (current == head) // 이동한 링크가 헤더인 경우
{
current = current->rlink; // 헤더의 후행 링크로 이동
}
}
print_dlist2(head);
getchar();
} while (ch != 'q');
// 메모리 해제
current = head;
while (current->rlink != head)
{
ddelete(head, current->rlink);
current = current->rlink;
}
free(head);
}
도서 대출 반납 시스템 예제
doubly_linked_list.h 헤더 파일
#pragma once
#ifndef __doubly_linked_list_h__
#define __doubly_linked_list_h__
// #define USE_NUMBER
// #define USE_STRING
#define USE_STRUCT
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#ifdef USE_STRING
typedef char element[80];
#endif
#ifdef USE_NUMBER
typedef int element;
#endif
#ifdef USE_STRUCT
typedef struct {
char bookname[80]; // 책 이름
int id; // 책 관리 번호
int is_borrowed; // 대여상태 (0: 보유, 1: 대여중)
} element;
#endif
typedef struct DListNode {
element data;
struct DListNode* llink; // 선행 노드 링크
struct DListNode* rlink; // 후행 노드 링크
} DListNode;
void init(DListNode* phead);
void print_dlist(DListNode* phead);
void dinsert(DListNode* before, element data);
void ddelete(DListNode* head, DListNode* removed);
DListNode* dsearch_id(DListNode* head, int id);
DListNode* dsearch_name(DListNode* head, char* name);
void borrow_book(DListNode* head, int id);
void return_book(DListNode* head, int id);
void display_books(DListNode* head);
#endif
<doubly_linked_list.c>
#include "doubly_linked_list.h"
// 이중 연결 리스트 초기화
void init(DListNode* phead) {
phead->llink = phead;
phead->rlink = phead;
}
// 이중 연결 리스트의 노드를 인쇄
void print_dlist(DListNode* phead) {
DListNode* p;
// p가 최초 위치인 phead에 도달할 때까지 반복
for (p = phead->rlink; p != phead; p = p->rlink)
{
#ifdef USE_STRING
printf("<-| |%s| |->", p->data);
#endif
#ifdef USE_NUMBER
printf("<-| |%d| |->", p->data);
#endif
}
printf("\n");
}
// 새로운 데이터를 노드 before의 오른쪽에 삽입
void dinsert(DListNode* before, element data) {
DListNode* newnode = (DListNode*)malloc(sizeof(DListNode));
#ifdef USE_STRING
strcpy(newnode->data, data);
#endif
#if USE_NUMBER || defined(USE_STRUCT)
newnode->data = data; // 새로운 노드에 값 저장
#endif
newnode->llink = before; // 새로운 노드의 선행 링크를 before의 주소로 할당
newnode->rlink = before->rlink; // 새로운 노드의 후행 링크를 before가 가진 후행 링크에서 복사
before->rlink->llink = newnode; // before의 후행 링크에서 보유한 선행 링크의 주소를 새로운 노드의 주소로 할당
before->rlink = newnode; // before의 후행 링크를 새로운 노드의 주소로 할당
}
// removed로 입력된 노드를 삭제
void ddelete(DListNode* head, DListNode* removed) {
if (removed == head) return; // 헤드는 삭제 불가
// 삭제될 노드가 가진 선행 링크의 후행 링크값을 삭제될 노드의 후행 링크값에서 복사
removed->llink->rlink = removed->rlink;
// 삭제될 노드가 가진 후행 링크의 선행 링크값을 삭제될 노드의 선행 링크값에서 복사
removed->rlink->llink = removed->llink;
free(removed);
}
// 검색 함수(id로 검색)
DListNode* dsearch_id(DListNode* head, int id) {
DListNode* p = head->rlink; // 시작 위치
while (p != head)
{
if (p->data.id == id)
{
return p;
}
p = p->rlink; // 다음 노드로 이동
}
return NULL;
}
// 검색 함수(이름으로 검색)
DListNode* dsearch_name(DListNode* head, char* name) {
DListNode* p = head->rlink; // 시작 위치
while (p != head)
{
if (strcmp(p->data.bookname, name) == 0)
{
return p;
}
p = p->rlink; // 다음 노드로 이동
}
return NULL;
}
// 도서 대출 함수
void borrow_book(DListNode* head, int id) {
DListNode* node = dsearch_id(head, id);
if (node == NULL)
{
printf("책 ID %d를 찾을 수 없습니다.\n", id);
}
else if (node->data.is_borrowed)
{
printf("책 '%s' (ID: %d)은 이미 대출 중입니다.\n", node->data.bookname, node->data.id);
}
else
{
node->data.is_borrowed = 1;
printf("책 '%s' (ID: %d)을 대출했습니다.\n", node->data.bookname, node->data.id);
}
}
// 도서 반납 함수
void return_book(DListNode* head, int id) {
DListNode* node = dsearch_id(head, id);
if (node == NULL)
{
printf("책 ID %d를 찾을 수 없습니다.\n", id);
}
else if (!node->data.is_borrowed)
{
printf("책 '%s' (ID: %d)은 이미 반납된 상태입니다.\n", node->data.bookname, node->data.id);
}
else
{
node->data.is_borrowed = 0;
printf("책 '%s' (ID: %d)을 반납했습니다.\n", node->data.bookname, node->data.id);
}
}
// 도서 목록 출력 함수
void display_books(DListNode* head) {
if (!head)
{
printf("등록된 책이 없습니다.\n");
return;
}
DListNode* p = head->rlink; // 이중 연결 리스트 시작 위치
printf("\n도서 목록\n");
while (p != head) // 이중 연결 리스트 끝까지 반복
{
printf("ID : %d, 제목 : %s, 상태 : %s\n", p->data.id, p->data.bookname, p->data.is_borrowed ? "대출" : "보유");
p = p->rlink; // 다음 노드로 이동
}
}
<main.c>
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "doubly_linked_list.h"
typedef DListNode Book;
// 안전한 입력 함수 (숫자 입력 검증)
int safe_input() {
int num;
while (1) {
if (scanf("%d", &num) == 1) {
getchar(); // 개행문자 제거
return num;
}
else {
printf("잘못된 입력입니다. 숫자를 입력하세요: ");
while (getchar() != '\n');
}
}
}
int main(void) {
// 이중 연결 리스트 헤더 생성
Book* head = (Book*)malloc(sizeof(Book));
init(head); // 헤더 초기화
int choice, id;
char bookname[80];
while (1) {
printf("\n도서 대출 시스템\n");
printf("1. 도서 추가\n");
printf("2. 도서 대출\n");
printf("3. 도서 반납\n");
printf("4. 도서 목록 보기\n");
printf("5. 종료\n");
printf("메뉴를 선택하세요 :");
choice = safe_input();
switch (choice) {
case 1: // 도서 추가
printf("책 ID 입력: ");
id = safe_input();
printf("책 제목 입력: ");
fgets(bookname, sizeof(bookname), stdin);
bookname[strcspn(bookname, "\n")] = 0; // 개행문자를 널기호로 변환
element data;
strcpy(data.bookname, bookname);
data.id = id;
data.is_borrowed = 0;
dinsert(head, data);
break;
case 2: // 도서 대출
printf("대출할 책 ID 입력 : ");
id = safe_input();
borrow_book(head, id);
break;
case 3: // 도서 반납
printf("반납할 책 ID 입력 : ");
id = safe_input();
return_book(head, id);
break;
case 4: // 도서 목록 보기
display_books(head);
break;
case 5: // 종료
printf("프로그램을 종료합니다.\n");
return 0;
default:
printf("잘못된 선택입니다. 다시 입력하세요.\n");
break;
}
}
return 0;
}
트리
- 리스트, 스택, 큐 등은 선형 구조
- 트리는 계층적인 구조를 나타내는 자료구조
트리는 부모-자식 관계의 노드들로 이루어진다
응용 분야
- 조직 표현
- 컴퓨터 디스트의 디렉토리 구조
- 인공지능에서의 결정트리 구조
노드(node) : 트리의 구성요소
루트(root) : 부모가 없는 노드
서브트리(subtree) : 하나의 노드와 그 노드들의 자손들로 이루어진 트리
단말노드: 자식이 없는 노드
비단말노드 : 적어도 하나의 자식을 가지는 노드
레벨(level) : 트리의 각층의 번호
높이(height) : 트리의 최대 레벨
차수(degree) : 노드가 가지고 있는 자식 노드의 개수
이진 트리 : 모든 노드가 2개의 서브 트리를 가지고 있는 트리
- 서브 트리는 공집합일 수 있다
- 이진 트리는 공집합이거나 루트와 서브 트리, 오른쪽 서브 트리로 구성된 노드들의 유한 집합으로 정의
- 이진 트리의 서브 트리들은 모두 이진 트리여야 한다
성징
- 노드의 개수가 n개이면 간선의 개수는 n - 1
- 높이가 h인 이진 트리가 가질 수 있는 노드 개수는 최소 (h + 1)개이며, 최대(2h + 1 - 1)개
분류
- 포화 이진 트리
- 완전 이진 트리
- 기타 이진 트리
포화 이진 트리
- 각 레벨에 노드가 꽉 차있는 이진 트리
- 각 노드에 번호를 붙일 수 있다
완전 이진 트리
- 레벨 1부터 k-1까지는 노드가 모두 채워져있고 마지막 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진 트리
- 포화 이진 트리와 번호 일치
표현
- 배열 표현법 : 모든 이진 트리를 포화 이진 트리라고 가정하고 각 노드에 번호를 붙여서 그 번호를 배열의 인덱스로 삼아 노드의 데이터를 배열에 저장하는 방법
- 링크 표현법 : 포인터를 이용하여 부모 노드가 자식 노드를 가리키게 하는 방법
부모와 자식 인덱스 관계
노드i의 부모 노드 인덱스 : i/2
노드 i의 왼쪽 자식 노드 인덱스 : 2i
노드 i의 오른쪽 자식 노드 인덱스 : 2i + 1
링크의 구현
노드는 구조체로 표현
링크는 포인터로 표현
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
typedef struct TreeNode {
int data;
struct TreeNode* left, * right;
} TreeNode;
int main(void) {
TreeNode* n1, * n2, * n3; // n1은 n2, n3의 부모
n1 = (TreeNode*)malloc(sizeof(TreeNode));
n2 = (TreeNode*)malloc(sizeof(TreeNode));
n3 = (TreeNode*)malloc(sizeof(TreeNode));
n1->data = 10;
n1->left = n2;
n1->right = n3;
n2->data = 20;
n2->left = NULL;
n2->right = NULL;
n3->data = 30;
n3->left = NULL;
n3->right = NULL;
free(n1);
free(n2);
free(n3);
return 0;
}
순회(traversal)
- 트리의 노드들을 체계적으로 방문하는 것
3가지 순회 방법
- 전위 순회(VLR) : 자손 노드보다 루트 노드를 먼저 방문
- 중위 순회(LVR) : 왼쪽 자손 루트, 오른쪽 자손 순으로 방문
- 후위순회(LRV) : 루트 노드보다 자손을 먼저 방문
전위 순회
- 루트 노드를 방문
- 왼쪽 서브트리를 방문
- 오른쪽 서브트리를 방문
중위 순회
- 왼쪽 서브트리를 방문
- 루트 노드를 방문
- 오른쪽 서브트리를 방문
후위 순회
- 왼쪽 서브트리를 방문
- 오른쪽 서브트리를 방문
- 루트 노드를 방문
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
typedef struct TreeNode {
int data;
struct TreeNode* left, * right;
} TreeNode;
// 15
// 4 20
//1 16 25
TreeNode n1 = { 1, NULL, NULL };
TreeNode n2 = { 4, &n1, NULL };
TreeNode n3 = { 16, NULL, NULL };
TreeNode n4 = { 25, NULL, NULL };
TreeNode n5 = { 20, &n3, &n4 };
TreeNode n6 = { 15, &n2, &n5 };
TreeNode* root = &n6;
// 중위 순회
void inorder(TreeNode* root) {
if (root != NULL)
{
inorder(root->left); // 왼쪽 서브트리 순회
printf("[%d] ", root->data); // 노드 값 인쇄 (노드 방문)
inorder(root->right); // 오른쪽 서브트리 순회
}
}
// 전위 순회
void preorder(TreeNode* root) {
if (root != NULL)
{
printf("[%d] ", root->data); // 노드 값 인쇄 (노드 방문)
preorder(root->left); // 왼쪽 서브트리 순회
preorder(root->right); // 오른쪽 서브트리 순회
}
}
// 후위 순회
void postorder(TreeNode* root) {
if (root != NULL)
{
postorder(root->left); // 왼쪽 서브트리 순회
postorder(root->right); // 오른쪽 서브트리 순회
printf("[%d] ", root->data); // 노드 값 인쇄 (노드 방문)
}
}
int main(void) {
printf("중위 순회 = ");
inorder(root);
printf("\n");
printf("전위 순회 = ");
preorder(root);
printf("\n");
printf("후위 순회 = ");
postorder(root);
printf("\n");
return 0;
}
반복적인 중위 순회
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
typedef struct TreeNode {
int data;
struct TreeNode* left, * right;
} TreeNode;
#define SIZE 100
int top = -1;
TreeNode* stack[SIZE];
void push(TreeNode* p)
{
if (top < SIZE - 1)
stack[++top] = p;
}
TreeNode* pop()
{
TreeNode* p = NULL;
if (top >= 0)
p = stack[top--];
return p;
}
void inorder_iter(TreeNode* root)
{
while (1) {
for (; root; root = root->left)
push(root);
root = pop();
if (!root) break;
printf("[%d] ", root->data);
root = root->right;
}
}
// 15
// 4 20
// 1 16 25
TreeNode n1 = { 1, NULL, NULL };
TreeNode n2 = { 4, &n1, NULL };
TreeNode n3 = { 16, NULL, NULL };
TreeNode n4 = { 25, NULL, NULL };
TreeNode n5 = { 20, &n3, &n4 };
TreeNode n6 = { 15, &n2, &n5 };
TreeNode* root = &n6;
int main(void)
{
printf("중위 순회=");
inorder_iter(root);
printf("\n");
return 0;
}