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;
}