[DataStructure] 완전이진트리의 삽입과 합계

이번 주 목요일부터 자료구조(2)수업이 실습수업을 겸하면서 오랜만에 만져보는 C언어와 자주 쓰지 않는 비쥬얼스튜디오를 익혀야 할 필요가 생겼다. 

 

교수님은 다음과 같은 텍스트파일의 숫자를 트리에 삽입 및 노드에 있는 모든 값들을 더해서 출력하기를 원하셨다. 다만 문제가 있었다. 

트리라고는 말씀하셨는데, 완전이진트리인지, 힙 트리인지 , 이진탐색트리인지를 제대로 못 들은 것이다. 그래서 그냥 완전 이진트리를 사용해서 데이터를 삽입할 계획을 세웠다. 그런데 , 문제는 완전이진트리의 삽입이 다른 트리와 다르게 노드간 데이터를 비교하면서 맞는 위치에 삽입되는 형태가 아니라 노드가 삽입될때 부모노드의 왼쪽자식노드 , 오른쪽 자식노드를 채우고 , 마지막 레벨의 노드를 제외하고 모두 자식노드를 두개씩 가지고 있어야 한다. 

 

위의 완전이진트리에 마지막에 삽입될 위치는 5번의 왼쪽 자식 노드이다. 

 

조금 복잡하고 어려웠지만 구글갓의 도움을 받아 완전이진트리의 마지막 노드를 삽입하려면 큐를 이용하는 방법이 있다는 것을 알게 되었다. 

 

그 방법은 이러하다. 

 

1. 노드가 생성되면 큐에 마지막에 삽입한다. 

 

2. 노드를 새로 삽입하는 경우 큐의 맨 앞에 있는 노드의 왼쪽노드가 비었는지 확인한다. 

 

3. 왼쪽노드가 비었다면 해당 노드의 왼쪽 노드에 삽입한다. 

5. 삽입된 해당 노드는 큐의 마지막에 삽입된다.

 

6. 다시 노드를 새로 삽입하는 경우 큐의 맨 앞에 있는 노드의 왼쪽노드가 비었는지 확인하고 비어있지 않다면 오른쪽 노드에 삽입한다.

7. 오른쪽노드에 삽입 후 큐에 맨 앞에 있는 노드를 큐에서 deque한 후 삽입한 오른쪽 노드를 큐의 맨 뒤에 삽입한다. 

 

구조 

 

내가 만든 노드는 root노드가  queue를 가지고 있는 형태로 구조를 짰다. 아무래도 treeInfo? treeType ? 이라는 다른 구조체를 도입해서 트리의 상위 구조체로써 가지고 있기에는 번거로웠기 때문이다. 

 

typedef struct node {
	int data;
	
	struct node* left;
	struct node* right;
	struct node* queueLink;

}node;

 

 노드는 int 형태의 데이터 필드가 있고 , 왼쪽 오른쪽 노드를 가질 수 있다. queueLink는 root노드가 queue의 1번에 해당하는 노드를 가지고 있고, 노드가 추가될때마다 queueLink 필드로 연결된 linkedQueue 형태를 취하고 있다. 

 

삽입

삽입은 root노드가 모든 데이터를 가지고 있어 최초 root노드의 자식노드가 채우는 것과 root노드의 자식노드들이 노드를 가지는 부분으로 나누었다. 

 

void insertNode(node *root,int data) {

	// newNode는 새롭게 생성될 노드이다. 아래는 생성될 노드의 모든 필드를 초기화 해주는 작업이다. 
	node* newNode = (node*)malloc(sizeof(node));
	newNode->left = NULL;
	newNode->right = NULL;
	newNode->data = data;
	newNode->queueLink = NULL;
	//queue의 마지막 노드를 삽입하기 위한 포인터 
	node* p = root->queueLink;
	if (root->queueLink == NULL) {
		//최초 root노드 삽입시 필드 셋
		root->queueLink = root;
		root->data = data;
	}
	else {
		if (p->left == NULL) {
			//노드 삽입
			p->left = newNode;
			if (root->right == NULL) {
				//최초 root 노드의 왼쪽 오른쪽 채워질때 동안의 강제적인 quelink셋
				root->queueLink = root;
			}else {
				//queue 삽입을 위한 포인터 이동 
				while (p->queueLink != NULL) {
					p = p->queueLink;
				}
				// queue에 삽입
				p->queueLink = newNode;
			}
			
		}
		else {
			if (root->right == NULL) {
				//최초 root 노드의 왼쪽 오른쪽 채워질때 동안의 강제적인 quelink셋
				root->right = newNode;
				root->queueLink = p->left;
				root->queueLink->queueLink = newNode;
			}
			else {
				//오른쪽 루트 삽입 
				p->right = newNode;
				//queue 삽입을 위한 포인터 이동
				while (p->queueLink != NULL) {
					p = p->queueLink;
				}
				//queue 삽입
				p->queueLink = newNode;
				//다음 번 삽입해야할 노드의 정보 변경 
				root->queueLink = root->queueLink->queueLink;
			}
		}
	}
}

 

합계

 

합계는 재귀적인 방법을 사용해서 파라미터로 받은 노드의 자식이 있는지 없는지를 판별하여 값을 더해서 반환하는 함수로 만들었다. 

int add(node *root) {
	if (root->left == NULL && root->right == NULL) {
		return root->data;
	}
	else {
		if (root->left != NULL && root->right != NULL) {
			return root->data + add(root->left) + add(root->right);
		}
		else if (root->left != NULL && root -> right == NULL) {
			return root->data + add(root->left);
		}
		else if (root->left == NULL && root->right != NULL) {
			return root ->data + add(root->right);
		}
	}
}

 

메인

 

int main() {
	FILE *inputFile = NULL;
	int data;
    
    //에러 검사 
	if ((inputFile = fopen("..\\hello\\input.txt", "r+")) == NULL) {
		printf("file is not open");
		return EXIT_FAILURE;
	}
    
    //root노드 생성 및 초기화
	node* root = (node *)malloc(sizeof(node));
	root->left = NULL;
	root->right = NULL;
	root->queueLink = NULL;

	while (fscanf(inputFile, "%d", &data) != EOF) {
		insertNode(root, data);
	}

	//preOrder(root);
	printf("%d", add(root));



	fclose(inputFile);
	return 0;
}

 

전체

 

#define _CRT_SECURE_NO_WARNINGS
#define MAX_QUE_SIZE 100

#include <stdio.h>
#include <stdlib.h>
typedef struct node {
	int data;
	
	struct node* left;
	struct node* right;
	struct node* queueLink;

}node;

typedef struct queue {
	 struct node* front;
}queue;


void insertNode(node *root,int data) {

	// newNode는 새롭게 생성될 노드이다. 아래는 생성될 노드의 모든 필드를 초기화 해주는 작업이다. 
	node* newNode = (node*)malloc(sizeof(node));
	newNode->left = NULL;
	newNode->right = NULL;
	newNode->data = data;
	newNode->queueLink = NULL;
	//queue의 마지막 노드를 삽입하기 위한 포인터 
	node* p = root->queueLink;
	if (root->queueLink == NULL) {
		//최초 root노드 삽입시 필드 셋
		root->queueLink = root;
		root->data = data;
	}
	else {
		if (p->left == NULL) {
			//노드 삽입
			p->left = newNode;
			if (root->right == NULL) {
				//최초 root 노드의 왼쪽 오른쪽 채워질때 동안의 강제적인 quelink셋
				root->queueLink = root;
			}else {
				//queue 삽입을 위한 포인터 이동 
				while (p->queueLink != NULL) {
					p = p->queueLink;
				}
				// queue에 삽입
				p->queueLink = newNode;
			}
			
		}
		else {
			if (root->right == NULL) {
				//최초 root 노드의 왼쪽 오른쪽 채워질때 동안의 강제적인 quelink셋
				root->right = newNode;
				root->queueLink = p->left;
				root->queueLink->queueLink = newNode;
			}
			else {
				//오른쪽 루트 삽입 
				p->right = newNode;
				//queue 삽입을 위한 포인터 이동
				while (p->queueLink != NULL) {
					p = p->queueLink;
				}
				//queue 삽입
				p->queueLink = newNode;
				//다음 번 삽입해야할 노드의 정보 변경 
				root->queueLink = root->queueLink->queueLink;
			}
		}
	}
}

int add(node *root) {
	if (root->left == NULL && root->right == NULL) {
		return root->data;
	}
	else {
		if (root->left != NULL && root->right != NULL) {
			return root->data + add(root->left) + add(root->right);
		}
		else if (root->left != NULL && root -> right == NULL) {
			return root->data + add(root->left);
		}
		else if (root->left == NULL && root->right != NULL) {
			return root ->data + add(root->right);
		}
	}
}

void preOrder(node* root) {
	if (root != NULL) {
		printf("%d", root->data);
		preOrder(root->left);
		preOrder(root->right);
	}
}

 



int main() {
	FILE *inputFile = NULL;
	int data;
	if ((inputFile = fopen("..\\hello\\input.txt", "r+")) == NULL) {
		printf("file is not open");
		return EXIT_FAILURE;
	}
	node* root = (node *)malloc(sizeof(node));
	root->left = NULL;
	root->right = NULL;
	root->queueLink = NULL;

	while (fscanf(inputFile, "%d", &data) != EOF) {
		insertNode(root, data);
	}

	//preOrder(root);
	printf("%d", add(root));



	fclose(inputFile);
	return 0;
}