트리 기초

트리란? 

 

뿌리에서 시작하여 가지, 잎으로 이루어진 나무와 비슷한 자료구조. 

운영체제의 파일 시스템, DOM 구조가 '트리'를 활용합니다. 

 

 

 

트리의  구성 요소 

 

부모 : 1번 노드는 2,3,4번 노드의 부모입니다. 

자식 : 2,3,4번 노드는 1번 노드의 자식입니다. 

 

루트(root) : 트리의 맨 꼭대기 '1'번 노드를 루트 노드라고 합니다.

가지 : 트리와 잎노드 사이의 모든 노드들을 뜻합니다. 

잎 노드(terminal node): 가장 끝의 노드, 단말 노드입니다. 

 

경로 : 3번 노드에서 10번 노드까지의 '경로'는 3, 7, 10 입니다. 

길이 : 3번 노드에서 10번 노드까지 2번 이동해야 하므로, 길이는 2입니다. 

노드의 깊이 : 루트 노드에서 해당 노드까지의 길이입니다. 예를 들어, 6번 노드의 깊이는 2입니다.  

(루트의 깊이는 0 입니다. )

 

레벨 : 깊이가  같은 노드의 집합입니다. 예를 들어, 2, 3, 4번 노드는 깊이가 1로 같으므로 레벨1 입니다. 

차수 : 자식 노드의 개수 입니다. 

트리의 차수 : 차수가 최대인 노드의 차수. 아래 그림에서는 1번 노드가 자식이 3개여서, 트리의 차수는 3입니다. 

루트 노드와 잎 노드를 까맣게 표시해 보았다!

 

---

 

트리 구현

 

왼쪽 자식-오른쪽 형제 표현법(Left Child Right Sibling)을 이용하여 노드를 만들고 부모 자식을 연결합니다. 

 

 

노드

 

링크드 리스트랑 똑같습니다.

typedef struct Node {
	struct Node* leftChild;
	struct Node* rightSibling;
	int data;
};

 

노드 생성 및 메모리 해제 

 

왼쪽 자식을 가리키는 포인터와 오른쪽 형제를 가리키는 포인터를 초기화 해줍니다.  

Node* CreateNode(int data) {

	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->leftChild = NULL;
	newNode->rightSibling = NULL;
	newNode->data = data;

	return newNode;
}

 

루트의 왼쪽 자식들 오른쪽 자식들을 free()하고, 루트 자신을 메모리 해제한다. 

/* 트리의 노드 전부 삭제 후, 루트 삭제. */
void FreeTree(Node* rootNode) {

	if (NULL != rootNode->leftChild) {
		FreeTree(rootNode->leftChild);
	}

	if (NULL != rootNode->rightSibling) {
		FreeTree(rootNode->rightSibling);
	}

	rootNode->leftChild = NULL;
	rootNode->rightSibling = NULL;

	FreeNode(rootNode);
}

 

 

자식 노드 연결 

 

부모 노드와 자식 노드 포인터를 매개변수로 입력 받습니다. 

자식이 없다면, 자식에 할당해줍니다. 

자식이 있다면, rightSibling 포인터를 이용하여 마지막 자식을 찾아내서 새 자식(?)을 연결합니다. 

/* 부모에게 자식 연결 */
void ConnectChild(Node** parent, Node* child) {

	if (NULL == (*parent)->leftChild) { // 자식이 없다면, 
		(*parent)->leftChild = child;
	}
	else {// 자식이 있다면, 끝을 찾아서 연결한다.
		Node* lastChild = (*parent)->leftChild;

		while (NULL != lastChild->rightSibling) {
			lastChild = lastChild->rightSibling;
		}

		lastChild->rightSibling = child;
	}
}

 

 

트리를 순회하며 출력 

 

자식과 형제를 출력하기 위해 함수를 재귀 호출 합니다.  

/* 트리 순회하며 출력 */
void Print(Node* node, int depth) {

	int num = 0;

	// 깊이 만큼 들여쓰기 
	for (num = 0; num < depth; num++) {
		printf(" ");
	}

	// 데이터 출력 
	printf("%d\n", node->data);

	// depth를 더해서 자식노드를 출력하도록 함수 재귀 호출 
	if (NULL != node->leftChild) {
		Print(node->leftChild, depth++);
	}

	// 형제노드를 출력하도록 함수 재귀 호출 (depth 유지.)
	if (NULL != node->rightSibling) {
		Print(node->rightSibling, depth);
	}
	
}