[DataStructure] 완전이진트리 삽입과 삭제 light 버전

기존에 만들어서 올린 완전이진트리는 node타입이 마지막 삽입을 위한 노드에 대한 정보를 가진 링크가 더 있어서 구조체가 최소화 되지 못했다고 생각한다. 그래서 기존에 만든 완전이진트리의 노드는 node + queue의 역할을 겸하기에 이번에는 따로 분리 해주었다. 

 

이번 작업에서는 queue를 이용한 트리에서 마지막 삽입된 노드를 찾는 흐름과 마지막 삽입된 노드의 부모를 찾는 작업의 흐름, 삽입되어야 할 위치를 찾기 위한 흐름을 보기위해서 삽입과 삭제시마다 queue를 새로 생성해서 찾게 하였다. 만약 적은 움직임으로 찾게 하고 싶으면, 트리의 선형적인 구조를 담은 queue를 어딘가 보관하고, 삭제할 노드의 부모노드에 대한 정보를 알고 있어야 한다. 

 

구조

 

// tree -> node
typedef struct tree {
	struct node* root;
}tree;

//node 타입은 최소한의 정보만 가지고 있다.
typedef struct node {
	struct node* left;
	struct node* right;
	int data;
}node;

//다양한 용도로 사용되는 queue
typedef struct queue {
	node* queue[100];
	int lastInsertedNode;
}queue;

 

모든 구조체는 최대한 적은 정보를 가지고 있게 하였고, queue 구조는 별도로 구조체로 만들지 않더라도, 작성할 수 있지만 편의를 위해 만들었다. 

 

삽입

 

void insertNode(tree* tree, int numb) {
	node* newNode = (node*)malloc(sizeof(node));
	newNode->left = NULL;
	newNode->right = NULL;
	newNode->data = numb;

	node* rootNode = tree->root;
	if (!(rootNode)) {
		tree->root = newNode;
	}
	else {
		node* nodeWillInserted = findNode(rootNode,true);
		
		if (!(nodeWillInserted->left)) {
			nodeWillInserted->left = newNode;
		}
		else {
			nodeWillInserted->right = newNode;
		}
	}
}

 

삽입의 경우 힙 처럼 따로 부모와의 관계가 중요하지 않기 때문에 삽입해야할 노드의 위치만 알면 간단하다. 

 

node* findNode(node * root,int condition) {
	node* temp = root;
	queue* q = (queue *)malloc(sizeof(queue));
	q->lastInsertedNode = 0;
	int dummy = 1;
	q->queue[0] = temp;
	while (temp->left) {
		q->queue[dummy] = temp->left;
		dummy++;
		if (temp->right) {
			q->queue[dummy] = temp->right;
			q->lastInsertedNode++;
			dummy++;
			temp = q->queue[q->lastInsertedNode];
		}
		else {
			break;
		}
	}
	if (condition) {
		return temp;
	}
	else {
		return q->queue[dummy-1];
	}
}

 

노드를 찾는 함수는 별로 마음에는 안들지만, condition 인자에 따라 삽입해야 할 노드의 위치 혹은 트리의 마지막에 삽입된 노드를 찾을 수 있게 2가지 기능을 만들어 놨다. 

 

반복문이 실행되는 동안 queue에 삽입된 순서대로 left,right를 queue에 마지막에 삽입한다. 반복문이 실행될 때 마다 queue에 순서대로 삽입된 노드들의 left, right를 검사하여, 만약 temp 의 left,right중 하나라도 없다면, 해당 노드는 삽입되어야 할 위치임을 알 수 있다. 

 

삭제

void deleteNode(tree * Ctree) {
	node * root = Ctree->root;
	node * removeNode = findNode(root, false);

	if (removeNode == root) {
		Ctree->root = NULL;
	}
	else {

		node * parents = findparentNode(root, removeNode);

		if (parents->left == removeNode) {
			parents->left = NULL;
		}
		else {
			parents->right = NULL;
		}
		free(removeNode);
		preOrder(root);
	}
}

 

삭제에 필요한 정보는 마지막으로 삽입된 노드의 부모노드이다. 부모노드를 알기 위해서는 두가지 방법이 있다. 한가지는 마지막 레벨에서 " 다음 형제 노드가 자식노드가 비어있고, 해당 노드는 자식노드가 꽉찼거나, 해당 노드의 자식이 왼쪽 밖에 없는 노드" 를 찾는 방법이고,  다른 하나는 마지막 레벨-1 노드 중 마지막에 삽입된 노드가 존재하는 노드를 찾는것이다.  

( 마지막 노드는 위의  findNode로 작성한 queue에 마지막으로 삽입된 노드이다. )

 

node* findparentNode(node * root, node * removedNode) {
	node* temp = root;
	queue* q = (queue *)malloc(sizeof(queue));
	q->lastInsertedNode = 0;
	int dummy = 1;
	q->queue[0] = temp;
	while (temp->left) {
		q->queue[dummy] = temp->left;
		dummy++;
		if (q->queue[q->lastInsertedNode]->left == removedNode || q->queue[q->lastInsertedNode] ->right == removedNode) {
			return q->queue[q->lastInsertedNode];
		}
		if (temp->right) {
			q->queue[dummy] = temp->right;
			q->lastInsertedNode++;
			dummy++;
			temp = q->queue[q->lastInsertedNode];
		}
		else {
			break;
		}
	}
	return q->queue[q->lastInsertedNode];
}

변수명을 조금 더 잘 지었으면 좋을 것 같다. 

 

탐색

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

 

전체

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>


// tree -> node
typedef struct tree {
	struct node* root;
}tree;

//node 타입은 최소한의 정보만 가지고 있다.
typedef struct node {
	struct node* left;
	struct node* right;
	int data;
}node;

//다양한 용도로 사용되는 queue
typedef struct queue {
	node* queue[100];
	int lastInsertedNode;
}queue;

node* findNode(node * root,int condition) {
	node* temp = root;
	queue* q = (queue *)malloc(sizeof(queue));
	q->lastInsertedNode = 0;
	int dummy = 1;
	q->queue[0] = temp;
	while (temp->left) {
		q->queue[dummy] = temp->left;
		dummy++;
		if (temp->right) {
			q->queue[dummy] = temp->right;
			q->lastInsertedNode++;
			dummy++;
			temp = q->queue[q->lastInsertedNode];
		}
		else {
			break;
		}
	}
	if (condition) {
		return temp;
	}
	else {
		return q->queue[dummy-1];
	}
}
void preOrder(node * root) {
	if (root != NULL) {
		printf("%d ->", root->data);
		preOrder(root->left);
		preOrder(root->right);
	}
}

node* findparentNode(node * root, node * removedNode) {
	node* temp = root;
	queue* q = (queue *)malloc(sizeof(queue));
	q->lastInsertedNode = 0;
	int dummy = 1;
	q->queue[0] = temp;
	while (temp->left) {
		q->queue[dummy] = temp->left;
		dummy++;
		if (q->queue[q->lastInsertedNode]->left == removedNode || q->queue[q->lastInsertedNode] ->right == removedNode) {
			return q->queue[q->lastInsertedNode];
		}
		if (temp->right) {
			q->queue[dummy] = temp->right;
			q->lastInsertedNode++;
			dummy++;
			temp = q->queue[q->lastInsertedNode];
		}
		else {
			break;
		}
	}
	return q->queue[q->lastInsertedNode];
}
void insertNode(tree* tree, int numb) {
	node* newNode = (node*)malloc(sizeof(node));
	newNode->left = NULL;
	newNode->right = NULL;
	newNode->data = numb;

	node* rootNode = tree->root;
	if (!(rootNode)) {
		tree->root = newNode;
	}
	else {
		node* nodeWillInserted = findNode(rootNode,true);
		
		if (!(nodeWillInserted->left)) {
			nodeWillInserted->left = newNode;
		}
		else {
			nodeWillInserted->right = newNode;
		}
	}
}

void deleteNode(tree * Ctree) {
	node * root = Ctree->root;
	node * removeNode = findNode(root, false);

	if (removeNode == root) {
		Ctree->root = NULL;
	}
	else {

		node * parents = findparentNode(root, removeNode);

		if (parents->left == removeNode) {
			parents->left = NULL;
		}
		else {
			parents->right = NULL;
		}
		free(removeNode);
		preOrder(root);
	}
}


int main() {	

	FILE* inputFile = NULL;
	int numb;
	if (!(inputFile = fopen("./input.txt", "r"))) {
		printf("√£¥¬ ∆ƒ¿œ¿Ã æ¯Ω¿¥œ¥Ÿ. ");
		return EXIT_FAILURE;
	}
	tree * Ctree = (tree*)malloc(sizeof(tree*));
	Ctree->root = NULL;

	while ((fscanf(inputFile, "%d", &numb)) != EOF) {
		insertNode(Ctree, numb);
	}
	preOrder(Ctree->root);
	
	for (int i = 0; i < 3; i++) {
		printf("\n");
		deleteNode(Ctree);
	}
	

	system("pause");
	fclose(inputFile);
	return 0;
}