[C언어] min leftist tree (최소 좌향 트리) 구현

0.

본 게시물은 자료구조프로그래밍 수업의 과제로 사용되었던 자료입니다.

참고용으로만 보시길 권장드리며, 코드 복제 시 본인에게 불이익이 따를 수 있음을 알려드립니다.

 

1. 문제

min leftist tree 합병(meld) 하기 (최소 좌향 트리)

- min leftist tree의 정수 key값이 입력 파일에서 순서대로 주어짐

- 정수 4개로 min leftist tree를 생성하여 queue에 삽입

- 정수 key를 하나씩 삽입하면서 tree 생성 (마지막에는 4개 이하로 된 min leftist tree 생성)

- queue에서 leftist tree 2개를 가져와서 합병하여 다시 queue에 삽입하는 과정을 반복하여 하나의 min leftist tree 생성

 

- 정수는 파일에서 입력 (개수 정해지지 않음)

- 입력, 출력 파일 이름은 명령 인자로 주어짐

- queue에 트리를 삽입할 때마다 트리 전체를 level order로 출력

- 자식이 없는 노드는 % 로 표현하기

 

입력 예시 1)

4 8 7 10

 

출력 예시 1)

4

8 7

% % 10 %

 

 

2.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX_QUEUE_SIZE 100

// 노드를 구성하는 구조체
typedef struct node* nodep;
typedef struct node {
	int data;
	int shortest;
	nodep leftChild, rightChild;
} node;
nodep root;

// 큐 선언 ( 최대 크기는 100으로 설정 )
nodep queue[MAX_QUEUE_SIZE];
int rear = -1;
int front = -1;
int count = 1;		// 몇번째 출력인지 확인하는 변수

// 레벨 오더를 위한 큐 선언
nodep queue_level[MAX_QUEUE_SIZE];
int rear_level = -1;
int front_level = -1;


nodep initNode(int data);	// 노드 초기화
void minMeld(nodep*, nodep*);	// 병합하는 함수
void minUnion(nodep*, nodep*);	// 공백이 아닌 트리를 병합하는 함수

void addq(nodep item, FILE* fpOut);	// 큐 삽입
nodep deleteq();		// 큐 삭제
void queueFull();		// 큐 가득 찾을 때
nodep queueEmpty();		// 큐 비었을 때

void levelOrder(nodep ptr, FILE* fpOut);
int depth(nodep);		// 트리의 깊이를 구하기 위한 함수
void addq_level(nodep item);	// 레벨오더를 위한 큐 삽입
nodep deleteq_level();						// 레벨오더를 위한 큐 삭제

int main(int argc, char* argv[]) {
	if (argc < 3) {
		fprintf(stderr, "입력파일과 출력파일 이름을 명령줄에 넣어주세요.");
		exit(EXIT_FAILURE);
	}

	FILE* fpIn = fopen(argv[1], "r");
	FILE* fpOut = fopen(argv[2], "w");

	int input_temp[4];		// 4개씩 입력받는 임시 배열
	int input_flag = 1;		// 입력 종료 플래그
	int input_count = 4;
	nodep input_node[4] = { NULL, };	// 임시 노드 배열
	while (input_flag) {
		for (int i = 0; i < 4; i++) {
			if (fscanf(fpIn, "%d", &input_temp[i]) == -1) {
				input_flag = 0;
				input_count = i;
				break;		// 마지막에 4개아닌 몇개인지를 나타냄
			}

			input_node[i] = initNode(input_temp[i]);		//노드 할당
		}

		for (int i = 1; i < input_count; i++) {
			minMeld(&input_node[0], &input_node[i]);		//input_node 첫번째에다가 구성하기
		}
		if(input_count != 0)
			addq(input_node[0], fpOut);		//큐에 넣기
	}

	while ((rear - front) != 1) {		// 큐에 한개가 남을 때 까지
		nodep a = deleteq();
		nodep b = deleteq();

		minMeld(&a, &b);
		addq(a, fpOut);
	}
}

nodep initNode(int data) {
	nodep new;
	new = malloc(sizeof(*new));
	new->data = data;
	new->shortest = 1;
	new->leftChild = NULL;
	new->rightChild = NULL;
	return new;
}

// 교재 코드
void minMeld(nodep* a, nodep* b) {
	if (!*a) *a = *b;
	else if (*b) minUnion(a, b);
	*b = NULL;
}

// 교재 코드
void minUnion(nodep* a, nodep* b) {
	nodep temp;

	if ((*a)->data > (*b)->data) {
		temp = *a;
		*a = *b;
		*b = temp;
	}

	if (!(*a)->rightChild) {
		(*a)->rightChild = *b;
	}
	else {
		minUnion(&(*a)->rightChild, b);
	}

	if (!(*a)->leftChild) {
		(*a)->leftChild = (*a)->rightChild;
		(*a)->rightChild = NULL;
	}
	else if ((*a)->leftChild->shortest < (*a)->rightChild->shortest) {
		temp = (*a)->leftChild;
		(*a)->leftChild = (*a)->rightChild;
		(*a)->rightChild = temp;
	}

	(*a)->shortest = (!(*a)->rightChild) ? 1 : (*a)->rightChild->shortest + 1;
}

void addq(nodep item, FILE* fpOut) {
	if (rear == MAX_QUEUE_SIZE - 1)
		queueFull();
	queue[++rear] = item;

	// 큐에 삽입할 때 마다 출력
	fprintf(fpOut, "%d번째 트리\n", count);
	levelOrder(item, fpOut);
	fprintf(fpOut, "\n");
	count++;
}

nodep deleteq() {
	if (front == rear)
		return queueEmpty();
	return queue[++front];
}

void queueFull() {
	printf("queue is full, cannot add element\n");
	exit(EXIT_FAILURE);
}

nodep queueEmpty() {
	nodep temp = initNode(-999);		// 에러코드
	return temp;
}

void levelOrder(nodep ptr, FILE* fpOut) {
	if (!ptr) return;
	int max = (int)pow(2, depth(ptr));			//max는 2^(깊이) 이다.

	addq_level(ptr);
	for (int i = 1; i < max; i *= 2) {
		int count = i;							// count는 해당 레벨에서의 최대 노드 개수

		while (count > 0) {
			ptr = deleteq_level();

			if (!ptr) {
				fprintf(fpOut, "%% ");
				addq_level(NULL);
				addq_level(NULL);
			}
			else {
				fprintf(fpOut, "%d ", ptr->data);
				addq_level(ptr->leftChild);
				addq_level(ptr->rightChild);
			}
			count--;
		}
		fprintf(fpOut, "\n");
	}
	rear_level = front_level = -1;
}

int depth(nodep node) {
	if (node == NULL) return 0;
	else {
		int left, right;
		left = depth(node->leftChild) + 1;		// 왼쪽 부분의 최대 깊이를 재귀적으로 구하기
		right = depth(node->rightChild) + 1;	// 오른쪽도 재귀적으로 구하기

		if (left < right) return right;			// 더 큰 깊이 값을 반환하기
		else return left;
	}
}

void addq_level(nodep item) {
	if (rear_level == MAX_QUEUE_SIZE - 1) {
		printf("queue for level-order is full, cannot add element\n");
		exit(EXIT_FAILURE);
	}
	queue_level[++rear_level] = item;
}

nodep deleteq_level() {
	if (front_level == rear_level)
		return queueEmpty();
	return queue_level[++front_level];
}