Tree 구현하기

Tree를 구현해봤습니다. 노드의 갯수와 간선의 갯수를 받았으며, 노드의 구조체에 부모, 자식의 데이터를 int형으로 구성했습니다.

 

#include <stdio.h>

#define MAX_TREE_NODE 1000
#define MAX_CHILD_NUM 10

typedef struct _node {
	int parent;
	int child[MAX_CHILD_NUM];
}Node;

Node Tree[MAX_TREE_NODE];
int NodeNum;
int edgeNum;

void initTree() {
	for (int i = 1; i <= NodeNum; i++) {
		Tree[i].parent = -1;
		for (int j = 0; j < MAX_CHILD_NUM; j++) {
			Tree[i].child[j] = -1;
		}
	}
}

void addChild(int parent, int child) {
	int j;
	for (j = 0; j < MAX_CHILD_NUM; j++) {
		if (Tree[parent].child[j] == -1) break;
	}
	Tree[parent].child[j] = child;
	Tree[child].parent = parent;
}

int getRoot() {
	for (int i = 1; i <= NodeNum; i++) {
		if (Tree[i].parent == -1) return i;
	}
	return -1;
}

void preOrder(int root) {
	for (int i = 0; i < MAX_CHILD_NUM; i++) {
		int child = Tree[root].child[i];
		if (child != -1) {
			printf("%d ", child);
			preOrder(child);
		}
	}
}

int main(void) {
	int parent;
	int child;

	scanf("%d %d", &NodeNum, &edgeNum);

	initTree();

	for (int i = 0; i < edgeNum; i++) {
		scanf("%d %d", &parent, &child);
		addChild(parent, child);
	}

	int root = getRoot();

	preOrder(root);
}

13 12
1 2 1 3 2 4 3 5 3 6 4 7 7 12 5 9 5 8 6 11 6 10 11 13

위에는 입력값입니다.

 

Tree를 실제 문제에서 적용하기엔.... 음.... 많은 경우가 있나 싶다만은 결국 Tree라는 구조를 확장하면 Heap을 짤 수 있기에 알아두는 것이 좋은거 같습니다.

---

이상 Tree 구현하기였습니다. ^_^