Tree(트리) - 1 [Binary Tree]

1. 트리의 개념

 - 자료들이 선형 자료 구조가 아니라 계층적인 구조를 가지고 있을 때 이용되는 자료구조

 - 인공 지능 문제에서도 트리가 사용되는데 대표적인 것이 결정 트리(decision tree)이다.

 

 1) 트리에서 나타나는 용어들

  - 트리를 구성하고 있는 것들을 노드(node)라고 한다.

  - 루트와 서브 트리는 선으로 연결되는데 이 연결선을 간선(edge)라고 한다.

  - 부모노드, 자식노드, 형제 관계(같은 레벨) 조상 노드, 자손 노드가 있다.

  - 자식 노드가 없는 노드를 단말 노드(terminal node, leaf node), 그 반대가 비단말 노드(nonterminal node)이다.

  - 노드의 차수(degree)는 그 노드의 자식 노드의 개수를 의미한다.

  - 트리의 차수는 트리가 가지고 있는 노드의 차수 중에서 가장 큰 차수이다.

  - 레벨은 루트의 레벨이 1이고 그 밑으로 1단계씩 내려갈수록 1씩 증가한다.

  - 트리의 높이(height)는 트리가 가지고 있는 최대 레벨을 말한다.

 

2. 이진 트리의 소개

 

 1) 이진 트리의 정의(순환적 정의)

  - 공집합이거나

  - 루트와 왼쪽 서브 트리, 오른쪽 서브 트리로 구성된 노드들의 유한 집합으로 정의된다. 이진 트리의 서브 트리들은 모두 이진 트리여야한다.

 

 2) 이진 트리의 성질

  - n개의 노드를 가진 이진 트리는 정확하게 n-1개의 간선을 가진다.

  - 높이가 h인 이진 트리의 경우, 최소 h개의 노드를 가지며 최대 2h-1개의 노드를 가진다.

  - 레벨 i에서의 노드의 최대 개수는 2i-1이다.

  - n개의 노드를 가지는 이진 트리의 높이는 최대 n이거나 최소 log2(n+1) (소수점 올림)이 된다.

  - 증명 : 높이 h의 이진트리가 가질 수 있는 노드의 최댓값은 2h-1이므로 n≤2h-1의 부등식이 성립하고 양변에 로그취하면 h≥ log2(n+1)이 된다.

 

 3) 이진 트리의 분류

  - 포화 이진 트리 : 모든 레벨에 노드가 꽉 참

  - 완전 이진 트리 : 마지막 레벨이전까지 노드가 꽉 차고 마지막 레벨에서는 왼쪽부터 채워져 있을 때

  - 기타 이진 트리

 

3. 이진 트리의 표현

 1) 배열 표현법

  - 인덱스 0을 사용하지 않는 편이 계산을 간단하게 만든다.

  - 완전 이진 트리가 아닌 일반적인 이진 트리의 경우 기억 공간 낭비가 심해진다.

  - 노드 i의 부모 노드 인덱스 = i/2 (소수점 내림)

  - 노드 i의 왼쪽 자식 노드 인덱스 = 2i

  - 노드 i의 오른쪽 자식 노드 인덱스 = 2i+1

 

 2) 링크 표현법

typedef struct TreeNode {
	int data;
	struct TreeNode *left, *right;
} TreeNode;

 

4. 이진 트리의 순회

 - 이진 트리를 순회(traversal)한다는 것은 이진 트리에 속하는 모든 노드를 한 번씩 방문하여 노드가 가지고 있는 데이터를 목적에 맞게 처리하는 것을 의미한다.

 - 자료를 순차적으로 순회하는 것은 이진 트리에서 중요한 연산이다.

 1) 이진 트리 순회 방법

  - 루트를 서브 트리에 앞서서 먼저 방문하면 전위 순회

  - 루트를 왼쪽과 오른쪽 서브 트리 중간에 방문하면 중위 순회

  - 루트를 왼쪽과 오른쪽 서브 트리 방문 후에 방문하면 후위 순회

  - 항상 왼쪽 서브 트리를 오른쪽 서브 트리에 앞서서 방문한다고 가정

  - 순회 알고리즘은 순환 기법을 사용한다.

// 중위 순회
void inorder( TreeNode *root ){
    if ( root ){
	 inorder( root->left );// 왼쪽서브트리 순회
	 printf("%d", root->data );  // 노드 방문
	 inorder( root->right );// 오른쪽서브트리 순회
    }
}
// 전위 순회
void preorder( TreeNode *root ){
    if ( root ){
	 printf("%d", root->data );  // 노드 방문
	 preorder( root->left );// 왼쪽서브트리 순회
	 preorder( root->right );// 오른쪽서브트리 순회
    }
}
// 후위 순회
void postorder( TreeNode *root ){
    if ( root ){
	 postorder( root->left );// 왼쪽서브트리 순회
	 postorder( root->right );// 오른쪽서브트리순회
	 printf("%d", root->data );  // 노드 방문
    }
}

 2) 레벨 순회

  - 이전 순회에서는 스택을 사용했던 것에 비해 레벨 순회는 큐를 사용하는 순회법이다.

  - 먼저 큐에 있는 노드를 꺼내어 방문한 다음, 그 노드의 자식 노드를 큐에 삽입하는 것으로 한번의 반복

// 레벨 순회 
void level_order(TreeNode *ptr)
{
	QueueType q;

	init(&q);
	if (!ptr) return;
	enqueue(&q, ptr);
	while (is_empty(&q)) {
		ptr = dequeue(&q);
		printf(" %d ", ptr->data);
		if (ptr->left)
			enqueue(&q, ptr->left);
		if (ptr->right)
			enqueue(&q, ptr->right);
	}
}

 3) 이진 트리 순회의 응용

  (1) 수식 트리 처리

   - 피연산자들은 단말 노드가 되며 연산자는 비단말 노드가 된다.

   - 가장 적합한 순회 방식은 자식 노드를 먼저 방문하는 후위 순회라 할 수 있을 것이다.

  (2) 디렉터리 용량 계산

   - 후위 순회 사용

 

5. 이진 트리의 연산

 1) 노드의 개수

int get_node_count(TreeNode *node)
{
	int count = 0;
	if (node != NULL)
		count = 1 + get_node_count(node->left) + get_node_count(node->right);
	return count;
}

 2) 단말 노드 개수 구하기

int get_leaf_count(TreeNode *node)
{
	int count = 0;
	if (node != NULL)
	{
		if (node->left == NULL && node->right == NULL) return 1;
		else count = get_leaf_count(node->left) + get_leaf_count(node->right);
	}
	return count;
}

 3) 높이 구하기

int get_height(TreeNode *node)
{
	int height = 0;
	if (node != NULL)
		height = 1 + max(get_height(node->left), get_height(node->right));
	return height;
}

 

 

[Reference]

• 천인국, 공용해, 하상호, 「C언어로 쉽게 풀어쓴 자료구조」, 생능출판, 2009년