자료구조_1 순환 스택 큐

트리 관련 설명

---

개념 링크 참조 자료구조(Data Structure)스택/큐/그래프/트리
이진 트리 참조 트리와_이진_트리_개념_정리

자료구조 실습 과제 블록별 해설

---

📚 문제

문제 1) 이진 검색 트리 만들고 검색하기

학생의 학번과 이름 항목을 가지는 학생정보를 이진 검색트리로 만들어 저장하고자 한다.
이진 검색 트리에서 학생의 학번 항목을 키로 활용하여 이진 검색트리를 만든다
(학번은 중복 되지 않으며, 만약 중복된 학번으로 저장할 경우 두 번째 저장 명령은 무시됨).
만들어진 이진 검색 트리에서 1) 노드수, 2) 단말 노드 수, 3) 트리의 높이 4) 이진 탐색 트리의 레벨 탐색 순회((부모노드)->[자식노드]관계 표시), 5) 이진 탐색 트리의 중위 순회, 6) 이진 검색 트리에서 검색, 7) 이진 검색 트리에서 노드 삭제, 8) 이진 검색 트리 전체 삭제를 수행하는 함수를 구현하시오.

이진 검색 트리를 위한 자료 구조와 main() 함수 내의 코드를 활용하여 아래 실행 예의 결과와 같이 보여줄 수 있도록 프로그램을 작성하시오.

//주어진 코드 및 문제
typedef struct ELEMENT {
	int id_num;
	char name[10];
}element;

typedef struct TreeNode {
	element std;
	struct TreeNode* left, * right;
} TreeNode;

int main(void) {
	TreeNode* root = NULL; TreeNode* tmp = NULL; element item;
	item.id_num = 2021006; strcpy(item.name, "name6"); root = insert_node(root, item);
	item.id_num = 2021001; strcpy(item.name, "name1"); root = insert_node(root, item);
	item.id_num = 2021009; strcpy(item.name, "name9"); root = insert_node(root, item);
	item.id_num = 2021007; strcpy(item.name, "name7"); root = insert_node(root, item);
	item.id_num = 2021003; strcpy(item.name, "name3"); root = insert_node(root, item);
	item.id_num = 2021002; strcpy(item.name, "name2"); root = insert_node(root, item);
	item.id_num = 2021005; strcpy(item.name, "name5"); root = insert_node(root, item);
	item.id_num = 2021004; strcpy(item.name, "name4"); root = insert_node(root, item);
	item.id_num = 2021008; strcpy(item.name, "name8"); root = insert_node(root, item);
	item.id_num = 2021010; strcpy(item.name, "name10"); root = insert_node(root, item);
	printf("이진 탐색 트리의 노드 수, leaf노드 수, 높이 구하기\n");
	printf("노드 수 = %d \nleaf 노드 수 = %d \n높이 = %d \n\n", get_node_count(root), get_leaf_count(root), get_height(root));
	printf("이진 탐색 트리 레벨 탐색 순회 결과\n"); 
	level_order(root);

	printf("\n\n");
	printf("이진 탐색 트리 중위 순회 결과 \n");
	inorder(root);

	printf("\n\n이진 탐색 트리에서 2021010 검색\n");
	tmp = search(root, 2021010);
	if (tmp != NULL)
		printf("검색 성공 : 학번 %d, 이름 %s \n", tmp->std.id_num, tmp->std.name);
	else
		printf("이진 탐색 트리에서 검색 학생을 발견못함 \n");
	printf("\n이진 탐색 트리에서 2021006 삭제\n");
	delete_node(&root, 2021006);
	printf("\n\n이진 탐색 트리에서 2021006 검색\n");
	tmp = search(root, 2021006);
	if (tmp != NULL)
		printf("검색 성공 : 학번 %d, 이름 %s \n", tmp->std.id_num, tmp->std.name);
	else
		printf("이진 탐색 트리에서 검색 학생을 발견못함 \n");

	printf("\n\n이진 탐색 트리 중위 순회 결과 \n"); inorder(root);
	printf("\n\n");
	printf("\n\n이진 탐색 트리 전체 삭제 \n"); root = delete_tree(root);
	printf("\n\n이진 탐색 트리 레벨 탐색 순회 결과\n"); level_order(root);
	printf("\n\n");

	return 0;
}

결과 예시

이진 탐색 트리의 노드 수, leaf노드 수, 높이 구하기
노드 수 = 10
leaf 노드 수 = 4
높이 = 5

이진 탐색 트리 레벨 탐색 순회 결과
Level 1 : [2021006]
Level 2 : (2021006)->[2021001] (2021006)->[2021009]
Level 3 : (2021001)->[2021003] (2021009)->[2021007] (2021009)->[2021010]
Level 4 : (2021003)->[2021002] (2021003)->[2021005] (2021007)->[2021008]
Level 5 : (2021005)->[2021004]


이진 탐색 트리 중위 순회 결과
[2021001] [2021002] [2021003] [2021004] [2021005] [2021006] [2021007] [2021008] [2021009] [2021010]

이진 탐색 트리에서 2021010 검색
검색 성공 : 학번 2021010, 이름 name10

이진 탐색 트리에서 2021006 삭제


이진 탐색 트리에서 2021006 검색
이진 탐색 트리에서 검색 학생을 발견못함


이진 탐색 트리 중위 순회 결과
[2021001] [2021002] [2021003] [2021004] [2021005] [2021007] [2021008] [2021009] [2021010]



이진 탐색 트리 전체 삭제
[2021002] [2021004] [2021005] [2021003] [2021001] [2021008] [2021010] [2021009] [2021007]

이진 탐색 트리 레벨 탐색 순회 결과
공백 트리입니다.

---

👨🏻‍💻 해결 코드

아마도 깨끗하게 되어진 코드는 아니다. 나중에 보면 엉터리 코드이겠지만, 그럼에도 남긴다.

문제를 보면 알 수 있 듯이 필요한 함수는

함수명	변수	설명
insert_node	root, item	노드 삽입
get_node_count	root	노드 수
get_leaf_count	root	단말 노드 수
get_height	root	트리의 높이
level_order	root	트리의 레벨 탐색 순회
inorder	root	트리의 중위 순회
search	root, id_num	트리에서 학번 검색
delete_node	root, id_num	트리에서 학번 삭제
delete_tree	root	트리 전체 삭제

📝 함수 의사코드, 현실화

---

전체 코드

//binary Tree 설명
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct ELEMENT {
	int id_num;
	char name[10];
}element;

typedef struct TreeNode {
	element std;
	struct TreeNode* left, * right, * parent;
} TreeNode;

int max(int a, int b) {
	return (a > b) ? a : b;
}

TreeNode* new_node(element item) {
	TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
	newNode->std.id_num = item.id_num;
	strcpy(newNode->std.name, item.name);
	newNode->left = newNode->right = newNode->parent = NULL;
	return newNode;
}

TreeNode* insert_node(TreeNode* node, element item) {
    if (node == NULL) {
        TreeNode* newNode = new_node(item);
        return newNode;
    }
	if (item.id_num < node->std.id_num) {
		node->left = insert_node(node->left, item);
		node->left->parent = node;  // 부모 노드 설정
	}
	else if (item.id_num > node->std.id_num) {
		node->right = insert_node(node->right, item);
		node->right->parent = node;  // 부모 노드 설정
	}

    return node;
}

int get_node_count(TreeNode* node) {
	int count = 0;
	if (node != NULL) {
		count = 1 + get_node_count(node->left) + get_node_count(node->right);
	}
	return count;
}
int get_leaf_count(TreeNode* node) {
	int count = 0;
	if (node != NULL) {
		if (node->left == NULL && node->right == NULL) return 1;
		else {
			count = get_leaf_count(node->left) + get_leaf_count(node->right);
		}
	}
	return count;
}
int get_height(TreeNode* node) {
	int height = 0;
	if (node != NULL) {
		height = 1 + max(get_height(node->left), get_height(node->right));
	}
	return height;
}

void inorder(TreeNode* node) {
	if (node) {
		inorder(node->left);
		printf("[%d] ", node->std.id_num);
		inorder(node->right);
	}
}

TreeNode* search(TreeNode* node, int id_num) {
	if (node == NULL) return NULL;
	if (id_num == node->std.id_num) return node;
	else if (id_num < node->std.id_num)
		return search(node->left, id_num);
	else
		return search(node->right, id_num);

}

TreeNode* min_value_node(TreeNode* node) {
	TreeNode* current = node;

	while (current && current->left != NULL) {
		current = current->left;
	}
	return current;
}

void delete_node(TreeNode** rootRef, int id_num) {
	TreeNode* root = *rootRef;
	if (root == NULL) return;

	if (id_num < root->std.id_num)
		delete_node(&(root->left), id_num);
	else if (id_num > root->std.id_num)
		delete_node(&(root->right), id_num);
	else { // key is same
		if (root->left == NULL) {
			TreeNode* temp = root->right;
			free(root);
			*rootRef = temp;
		}
		else if (root->right == NULL) {
			TreeNode* temp = root->left;
			free(root);
			*rootRef = temp;
		}
		else {
			TreeNode* temp = min_value_node(root->right);
			root->std.id_num = temp->std.id_num;
			strcpy(root->std.name, temp->std.name);
			delete_node(&(root->right), temp->std.id_num);
		}
	}
}

TreeNode* delete_tree(TreeNode* root) {
	if (root == NULL) return NULL;

	root->left = delete_tree(root->left);
	root->right = delete_tree(root->right);
	printf("[%d] ",root->std.id_num);
	free(root);
	return NULL;
}

// 큐 노드 정의
typedef struct QueueNode {
	TreeNode* treeNode;
	struct QueueNode* next;
} QueueNode;

// 큐 정의
typedef struct {
	QueueNode* front;
	QueueNode* rear;
	int count;
} Queue;

// 큐 초기화
void initQueue(Queue* q) {
	q->front = q->rear = NULL;
	q->count = 0;
}

// 큐가 비었는지 확인
int isEmpty(Queue* q) {
	return q->count == 0;
}

// 큐에 노드 추가
void enqueue(Queue* q, TreeNode* node) {
	QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
	newNode->treeNode = node;
	newNode->next = NULL;
	if (isEmpty(q)) {
		q->front = q->rear = newNode;
	}
	else {
		q->rear->next = newNode;
		q->rear = newNode;
	}
	q->count++;
}

// 큐에서 노드 제거
TreeNode* dequeue(Queue* q) {
	if (isEmpty(q)) return NULL;
	QueueNode* temp = q->front;
	TreeNode* result = temp->treeNode;
	q->front = q->front->next;
	if (q->front == NULL) q->rear = NULL;
	free(temp);
	q->count--;
	return result;
}

// 레벨 순회 구현
void level_order(TreeNode* root) {
	if (root == NULL) {
		printf("공백 트리입니다.\n");
		return;
	}

	Queue q;
	initQueue(&q);
	enqueue(&q, root);

	int level = 0;

	while (!isEmpty(&q)) {
		int levelCount = q.count; // 현재 레벨의 노드 수
		printf("Level %d : ", ++level);

		while (levelCount > 0) {
			TreeNode* current = dequeue(&q);

			// 현재 노드 출력
			if (current->parent != NULL) printf("(%d)->", current->parent->std.id_num);
			printf("[%d] ", current->std.id_num);

			if (current->left != NULL) enqueue(&q, current->left);
			if (current->right != NULL) enqueue(&q, current->right);

			levelCount--;
		}

		printf("\n");
	}
}

int main(void) {
	TreeNode* root = NULL; TreeNode* tmp = NULL; element item;
	item.id_num = 2021006; strcpy(item.name, "name6"); root = insert_node(root, item);
	item.id_num = 2021001; strcpy(item.name, "name1"); root = insert_node(root, item);
	item.id_num = 2021009; strcpy(item.name, "name9"); root = insert_node(root, item);
	item.id_num = 2021007; strcpy(item.name, "name7"); root = insert_node(root, item);
	item.id_num = 2021003; strcpy(item.name, "name3"); root = insert_node(root, item);
	item.id_num = 2021002; strcpy(item.name, "name2"); root = insert_node(root, item);
	item.id_num = 2021005; strcpy(item.name, "name5"); root = insert_node(root, item);
	item.id_num = 2021004; strcpy(item.name, "name4"); root = insert_node(root, item);
	item.id_num = 2021008; strcpy(item.name, "name8"); root = insert_node(root, item);
	item.id_num = 2021010; strcpy(item.name, "name10"); root = insert_node(root, item);
	printf("이진 탐색 트리의 노드 수, leaf노드 수, 높이 구하기\n");
	printf("노드 수 = %d \nleaf 노드 수 = %d \n높이 = %d \n\n", get_node_count(root), get_leaf_count(root), get_height(root));
	printf("이진 탐색 트리 레벨 탐색 순회 결과\n"); 
	level_order(root);
	
	printf("\n\n");
	printf("이진 탐색 트리 중위 순회 결과 \n");
	inorder(root);

	printf("\n\n이진 탐색 트리에서 2021010 검색\n");
	tmp = search(root, 2021010);
	if (tmp != NULL)
		printf("검색 성공 : 학번 %d, 이름 %s \n", tmp->std.id_num, tmp->std.name);
	else
		printf("이진 탐색 트리에서 검색 학생을 발견못함 \n");
	printf("\n이진 탐색 트리에서 2021006 삭제\n");
	delete_node(&root, 2021006);
	printf("\n\n이진 탐색 트리에서 2021006 검색\n");
	tmp = search(root, 2021006);
	if (tmp != NULL)
		printf("검색 성공 : 학번 %d, 이름 %s \n", tmp->std.id_num, tmp->std.name);
	else
		printf("이진 탐색 트리에서 검색 학생을 발견못함 \n");

	printf("\n\n이진 탐색 트리 중위 순회 결과 \n"); inorder(root);
	printf("\n\n");
	printf("\n\n이진 탐색 트리 전체 삭제 \n"); root = delete_tree(root);
	printf("\n\n이진 탐색 트리 레벨 탐색 순회 결과\n"); level_order(root);
	printf("\n\n");

	return 0;
}