Krafton_jungle 5기 28 ~ 29일차 TIL - 자료구조

자료구조

 

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

이진 탐색 트리에서 노드를 삭제하는 코드