Krafton_Jungle/Study
Krafton_jungle 5기 28 ~ 29일차 TIL - 자료구조
전낙타
2024. 4. 15. 19:59
자료구조
Binary Search Tree 기본 제공 함수
//////////////////////////////////////////////////////////////////////////////////
/* CE1007/CZ1007 Data Structures
Lab Test: Section F - Binary Search Trees Questions
Purpose: Implementing the required functions for Question 5
Implementing 'remove node' operation for BST*/
//////////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <stdlib.h>
//////////////////////////////////////////////////////////////////////////////////
typedef struct _bstnode{
int item;
struct _bstnode *left;
struct _bstnode *right;
} BSTNode; // You should not change the definition of BSTNode
typedef struct _stackNode{
BSTNode *data;
struct _stackNode *next;
}StackNode; // You should not change the definition of StackNode
typedef struct _stack
{
StackNode *top;
}Stack; // You should not change the definition of Stack
typedef struct _QueueNode {
BSTNode *data;
struct _QueueNode *nextPtr;
}QueueNode; // You should not change the definition of QueueNode
typedef struct _queue
{
QueueNode *head;
QueueNode *tail;
}Queue; // You should not change the definition of queue
///////////////////////// function prototypes ////////////////////////////////////
void insertBSTNode(BSTNode **node, int value);
void push(Stack *stack, BSTNode *node);
BSTNode *pop(Stack *s);
BSTNode *peek(Stack *s);
int isEmpty(Stack *s);
void removeAll(BSTNode **node);
BSTNode* removeNodeFromTree(BSTNode *root, int value);
///////////////////////////// main() /////////////////////////////////////////////
void push(Stack *stack, BSTNode * node)
{
StackNode *temp;
temp = malloc(sizeof(StackNode));
if (temp == NULL)
return;
temp->data = node;
if (stack->top == NULL)
{
stack->top = temp;
temp->next = NULL;
}
else
{
temp->next = stack->top;
stack->top = temp;
}
}
BSTNode * pop(Stack * s)
{
StackNode *temp, *t;
BSTNode * ptr;
ptr = NULL;
t = s->top;
if (t != NULL)
{
temp = t->next;
ptr = t->data;
s->top = temp;
free(t);
t = NULL;
}
return ptr;
}
BSTNode * peek(Stack * s)
{
StackNode *temp;
temp = s->top;
if (temp != NULL)
return temp->data;
else
return NULL;
}
void enqueue(QueueNode **headPtr, QueueNode **tailPtr, BSTNode *node)
{
// dynamically allocate memory
QueueNode *newPtr = malloc(sizeof(QueueNode));
// if newPtr does not equal NULL
if (newPtr != NULL) {
newPtr->data = node;
newPtr->nextPtr = NULL;
// if queue is empty, insert at head
if (isEmpty(*headPtr)) {
*headPtr = newPtr;
}
else { // insert at tail
(*tailPtr)->nextPtr = newPtr;
}
*tailPtr = newPtr;
}
else {
printf("Node not inserted");
}
}
BSTNode* dequeue(QueueNode **headPtr, QueueNode **tailPtr)
{
BSTNode *node = (*headPtr)->data;
QueueNode *tempPtr = *headPtr;
*headPtr = (*headPtr)->nextPtr;
if (*headPtr == NULL) {
*tailPtr = NULL;
}
free(tempPtr);
return node;
}
int isEmpty(Stack *s)
{
if (s->top == NULL)
return 1;
else
return 0;
}
void removeAll(BSTNode **node)
{
if (*node != NULL)
{
removeAll(&((*node)->left));
removeAll(&((*node)->right));
free(*node);
*node = NULL;
}
}다른 문제들과 같이 Queue와 Stack 자료형과 그에 따른 기본함수를 제공한다.
Level Order Traversal
void levelOrderTraversal(BSTNode* root)
{
if (root == NULL) {
return;
}
// 큐 초기화
Queue *queue = (Queue *) malloc(sizeof(Queue));
if (queue == NULL) {
printf("Memory allocation failed\n");
return;
}
queue->head = queue->tail = NULL;
enqueue(&queue->head, &queue->tail, root);
while (!isEmpty(queue->head)) {
BSTNode *node = dequeue(&queue->head, &queue->tail);
printf("%d ", node->item);
if (node->left != NULL) {
enqueue(&queue->head, &queue->tail, node->left);
}
if (node->right != NULL) {
enqueue(&queue->head, &queue->tail, node->right);
}
}
free(queue);
}Queue를 하나 생성하고 이를 사용해 너비 우선 순회를 하는 간단한 코드
In Order Iterative
void inOrderTraversal(BSTNode *root)
{
if (root == NULL) {
return;
}
// 메모리 할당
Stack *s = (Stack*) malloc(sizeof(Stack));
if (s == NULL) {
printf("Stack allocation failed\n");
return;
}
// 스택 초기화
s->top = NULL;
BSTNode *cur = root;
BSTNode *tmp = NULL;
while(1) {
if (cur != NULL) {
push(s, cur);
cur = cur->left;
} else {
if (s->top == NULL) {
free(s);
return;
}
tmp = pop(s);
printf("%d ", tmp->item);
cur = tmp->right;
}
}
}stack을 사용해서 중위순회
Pre Order Iterative
// 단순 재귀
// void preOrderIterative(BSTNode *root)
// {
// if (root == NULL) {
// return;
// }
// printf("%d ", root->item);
// preOrderIterative(root->left);
// preOrderIterative(root->right);
// }
void makeStack(Stack *s, BSTNode *cur) {
if (cur == NULL) {
return;
}
makeStack(s, cur->right);
makeStack(s, cur->left);
push(s, cur);
}
void preOrderIterative(BSTNode *root)
{
if (root == NULL) {
return;
}
Stack *s = (Stack*) malloc(sizeof(Stack));
if (s == NULL) {
printf("Stack allocation failed\n");
return;
}
s->top = NULL;
makeStack(s, root);
BSTNode *tmp = NULL;
while (s->top != NULL) {
tmp = pop(s);
printf("%d ", tmp->item);
}
free(s);
}처음에 단순 재귀로 구현했다가 스택을 꼭 사용해야 한다는 조건을 보고 다시 풀었음
Post Order IterativeS1
void makeStack(Stack *s, BSTNode *cur) {
if (cur == NULL) {
return;
}
push(s, cur);
makeStack(s, cur->right);
makeStack(s, cur->left);
}
void postOrderIterativeS1(BSTNode *root)
{
// 메모리 할당
Stack *s = (Stack *) malloc(sizeof(Stack));
if (s == NULL) {
printf("Stack allocation failed\n");
return;
}
s->top = NULL;
makeStack(s, root);
while(s->top != NULL) {
printf("%d ", pop(s)->item);
}
}stack을 사용해 후위순회를 하는 코드
Post Order IterativeS2
void makeStack(Stack *s, BSTNode *cur) {
if (cur == NULL) {
return;
}
makeStack(s, cur->left);
makeStack(s, cur->right);
push(s, cur);
}
void postOrderIterativeS2(BSTNode *root)
{
// use two stack
Stack *s1 = (Stack *) malloc(sizeof(Stack));
Stack *s2 = (Stack *) malloc(sizeof(Stack));
s1->top = NULL;
s2->top = NULL;
makeStack(s1, root);
while (s1->top != NULL) {
push(s2, pop(s1));
}
while (s2->top != NULL) {
printf("%d ", pop(s2)->item);
}
free(s1);
free(s2);
}전위순회를 하고 다른 스택에 옮겨서 반전시키는 방법
Remove Node From Tree
BSTNode* findMinValue(BSTNode* node) {
BSTNode* curr = node;
while (curr->left != NULL) {
curr = curr->left;
}
return curr;
}
BSTNode* removeNodeFromTree(BSTNode *root, int value)
{
/* add your code here */
// 1. 트리가 비어있다면 NULL 반환
if (root == NULL)
return NULL;
// 2. 삭제할 노드 탐색 (재귀)
if (value < root->item) {
root->left = removeNodeFromTree(root->left, value);
}
else if (value > root->item) {
root->right = removeNodeFromTree(root->right, value);
}
// 3. 삭제할 노드 찾았으면,
else {
// 3-1. 삭제할 노드의 자식이 없으면 걍 삭제 ㄱ
if (root->left == NULL && root->right == NULL) {
free(root);
return NULL;
}
// 3-2. 삭제할 노드의 자식이 1개면?? 맞나??
else if (root->left == NULL) {
BSTNode* tmp = root->right;
free(root);
return tmp;
}
else if (root->right == NULL) {
BSTNode* tmp = root->left;
free(root);
return tmp;
}
// 3-3. 삭제할 노드의 자식이 2개면,
else {
// 오른쪽 최솟값 올리고
BSTNode* tmp = findMinValue(root->right);
root->item = tmp->item; // 값 갱신
root->right = removeNodeFromTree(root->right, tmp->item); // 오른쪽에서 재귀적으로 삭제 작업
}
}
return root;
}이진 탐색 트리에서 노드를 삭제하는 코드