트리 - 1

🐢 트리

    - 계층적인 구조를 나타내는 자료구조

    - 부모-자식 관계의 노드들로 이루어짐

    - 정의: 1개 이상의 노드로 이루어진 유한 집합

        - 하나의 루트 노드 존재

        - acyclic graph

 

** 가계도는 트리가 아니다.

** 동등한 위치에 있는 노드끼리는 간선이 존재하지 않는다. (트리는 acyclic graph)

 

🐢 트리의 용어

    - 노드: 트리의 구성요소

    - 루트: 부모가 없는 노드

    - 서브트리: 하나의 노드와 자손들로 이루어짐

    - 단말노드 (terminal, leaf): 자식이 없는 노드

    - 비단말노드: 자식을 가지는 노드

 

** 노드 하나만 존재 --> 트리인가요?? : YES

** empty, 즉 트리에 아무 노드도 없는 경우도 트리인가요? :  1) 일반트리에서는 NO 2) 이진트리에서는 YES

 

    - 레벨: 트리의 각 층의 번호 (루트 노드 부터 1부터 시작)

    - 높이, 깊이: 트리의 최대 레벨

    - 차수: 노드의 자식 노드 수

 

** 트리의 차수는 그 트리에 있는 노드의 최대 차수

 

🐢 일반 트리

--> 링크 배열 이용 시 길이가 결정되지 않는다.. 자식이 몇 개가 올지 알 수 없음

 

🐢  가변수 필드 구조

 - 효율적인 알고리즘 작성을 위해서 노드 구조가 일정한 것이 좋다.

 

- 트리 표현 방법 1. left child - right sibling

    --> 왼쪽에는 자식 노드 포인터, 오른쪽에는 형제 노드 포인터!

    ** 모든 노드는 자신의 가장 왼쪽 자식 노드만 가리키고 다음 자식들은 가장 왼쪽 자식들이 linked list 로 관리한다.

 

- 트리 표현 방법 2. binary tree

    --> 이진트리 (자식 노드 only two)

    - 모든 노드가 정확하게 두 서브 트리를 가지고 있는 트리

        - 서브 트리는 공백이 될 수 있음

    - 일반 트리와의 차이점

        - 왼쪽 서브 트리와 오른쪽 서브 트리를 명확하게 구별

 

    - 공백 이진 트리 (일반 트리는 공백 트리가 없음)

 

🐢이진트리

    모든 노드가 2개의 서브 트리를 가지고 있는 트리 (서브 트리는 공집합 일 수 있다.)

    - 각 노드에는 최대 2개까지의 자식 노드가 존재

    - 모든 노드의 차수가 2 이하가 된다. --> 구현하기가 편리함 (차수 = 자식 노드 개수)

    - 서브 트리 간의 순서가 존재 (왼쪽, 오른쪽)

 

** 노드의 개수가 n개 이면 간선의 개수는 n - 1개

** 높이가 h이면 최소 h개~ 최대 2^h - 1개의 노드를 가짐

** 레벨 i의 최대 노드 수: 2^(i - 1)

** n개 노드의 이진 트리 높이: log2 (n + 1) 올림수 ~ n

 

🐢 포화 이진 트리 (Full)

    - 트리의 각 레벨에 노드가 꽉 차있는 이진트리

    - 높이가 h이고 노드수가 2^h - 1인 이진 트리

 

🐢 완전 이진 트리 (complete)

    - 높이가 h일 때 레벨 1부터 h - 1까지는 노드가 모두 채워짐

    - 마지막 레벨 h에서는 노드가 순서대로 채워짐

    - 포화 이진 트리 --> 완전 이진 트리 (역은 성립하지 않는다.)

    - 노드 번호가 포화 이진 트리와 같다.

 

🐢 이진트리의 표현 방법

방법1. 배열표현법

    - 모든 이진트리를 포화 이진 트리라고 가정

장점

1. 어떤 이진 트리에도 사용 가능하다.

2. 완전 이진트리에 최적이다.

 

단점

1. 편향 이진 트리일 때 배열 공간을 절반도 사용하지 못할 수 있음

2. 트리의 중간에 노드의 삭제나 삽입 시 많은 다른 노드들의 이동이 불가피하다.

 

방법2. 링크 표현법

    - 부모 노드가 자식 노드를 가리키게 하는 방법 (포인터를 이용한다.)

 

🐢 이진트리의 순회

순회: 트리의 노드들을 체계적으로 한 번씩 방문

    - 다양한 순회 방법이 존재함 (전위순회 . 중위순회 . 후위순회)

 

전위순회 (V --> L --> R)

    - ex) 구조화된 문서 출력

void preorder(BinaryNode* node) {
		if (node != NULL) {
			printf(" [%c] ", node->getData());
			if (node->getLeft() != NULL) preorder(node->getLeft());
			if (node->getRight() != NULL) preorder(node->getRight());
		}
	}

 

중위순회 (L --> V --> R)

void inorder(BinaryNode* node) {
	if (node != NULL) {
		if (node->getLeft() != NULL) inorder(node->getLeft());
		printf(" [%c] ", node->getData());
		if (node->getRight() != NULL) inorder(node->getRight());
	}
}

 

후위순회 (L --> R --> V)

    - ex) 폴더 용량 계산

void postorder(BinaryNode* node) {
	if (node != NULL) {
		if (node->getLeft() != NULL) postorder(node->getLeft());
		if (node->getRight() != NULL) postorder(node->getRight());
		printf(" [%c] ", node->getData());
	}
}

 

🐢 레벨 순회

노드를 레벨 순으로 검사하는 순회방법 (큐를 사용)

void levelorder() {
	printf("\nlevelorder: ");
	if (!isEmpty()) {
		CircularQueue q;
		q.enqueue(root);
		while (!q.isEmpty()) {
			BinaryNode* n = q.dequeue();
			if (n != NULL) {
				printf(" [%c] ", n->getData());
				q.enqueue(n->getLeft());
				q.enqueue(n->getRight());
			}
		}
	}
	printf("\n");
}

 

🐢 이진 트리 연산

    1. 노드 개수: 트리의 전체 노드 수를 계산

        - 각 서브 트리에 대해 순환 호출한 후, 반환되는 값에 1을 더함 (1은 루트 노드에 해당)

// 트리의 노드 개수를 구하는 함수
int	getCount() { return isEmpty() ? 0 : getCount(root); }

// 순환 호출에 의해 node를 루트로 하는 서브 트리의 노드 수 계산 함수
int getCount(BinaryNode* node) {
	if (node == NULL) return 0;
	return 1 + getCount(node->getLeft()) + getCount(node->getRight());
}

 

    2. 단말 노드 개수: 트리의 단말 노드 개수를 계산

        - 각 서브 트리에 대해 순환 호출하고 결과를 합해 반환

int	getLeafCount() { return isEmpty() ? 0 : getLeafCount(root); }

int getLeafCount(BinaryNode* node) {
	if (node == NULL) return 0;
	if (node->isLeaf()) return 1;
	else return getLeafCount(node->getLeft()) + getLeafCount(node->getRight());
}

 

    3. 높이: 트리의 높이 = 서브 트리의 높이 + 1

        - 서브 트리에 대하여 순환 호출하고 서브 트리들의 반환 값 중에서 최댓값을 구하여 1을 더해 반환

int	getHeight() { return isEmpty() ? 0 : getHeight(root); 

int getHeight(BinaryNode* node) {
	if (node == NULL) return 0;
	int	hLeft = getHeight(node->getLeft());
	int	hRight = getHeight(node->getRight());
	return (hLeft > hRight) ? hLeft + 1 : hRight + 1;
}

 

🐢 수식 트리: 산술식을 트리 형태로 표현한 것

    - 비단말 노드: 연산자

    - 단말 노드: 피연산자

 

    - 수식 트리 계산 --> 후위 순회를 사용

int evaluate() { return evaluate(root); }

// 수식 계산 함수
int evaluate(BinaryNode* node) {
	if (node == NULL) return 0;
	if (node->isLeaf()) return node->getData();
	else {
		int op1 = evaluate(node->getLeft());
		int op2 = evaluate(node->getRight());
		switch (node->getData()) {
		case '+': return op1 + op2;
		case '-': return op1 - op2;
		case '*': return op1 * op2;
		case '/': return op1 / op2;
		}
		return 0;
	}

 

🐢 폴더 용량 계산

    - 후위 순회를 사용

int	calcSize() { return calcSize(root); }

int calcSize(BinaryNode* node) {
	if (node == NULL) return 0;
	return node->getData() + calcSize(node->getLeft()) + calcSize(node->getRight());
}