자료구조_08.트리

트리의 개념

지금까지는 리스트, 스택, 큐 등의 선형 자료 구조(linear data structure)를 알아봤다.

이번에는 계층적인 구조(hierachiacal structure)알아보려 한다.

계층적인 구조에 대해 예를 들면 컴퓨터의 폴더를 들수있다. 폴더는 상위폴더와 하위폴더로 이루어져있는 것을 알 수 있다.하위폴더를 들어가기 위해서는 먼저 상위폴더를 들어간 후에 하위폴더로 들어갈 수 있다.

 

트리의 용어들

트리의 구성 요소에 해당하는 A,B,C,...,N,O를 노드(node)라 한다.

계층적인 구조에서 가장 높은 곳에 있는 노드(위 그림의 A)를 루트(root)노드라고 하며, 그 외의 노드를 서브트리(subtree)라고 한다.위 그림은 {B,F,G},{C,H,K,L,M},{D,I,N},{E,J,O}로 4개의 집합으로 나누어지는데 이들을 A의 서브트리라한다.

다시 서브트리인 {C,H,K,L,M}의 루트는 C가 되고 나머지 노드들{H,K,L,M}가 서브트리로, {H,K,L,M}의 루트는 H가 되고 서브트리는 {K,L,M}으로 나누어질 수 있다.

 

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

 

노드들 간에는 부모 관계, 형제 관계, 조상과 자손 관계가 존재한다.

위 그림에서 보면 각 계층을 레벨(Level)로 나누어놓은것을 알 수 있다. 노드간의 관계는 노드들의 Level로 나뉜다.

관계를 이루는 노드들의 Level가 1이 차이나면 부모 관계로 볼 수있고, Level이 같다면 형제 관계가 된다.

위 그림에서는 A는 B의 부모 노드(parant node)가, B는 A의 자식 노드(childeren node)가 된다. B,C,D,E노드는 서로 형제 노드가 된다. 

조상 노드(ancestor node)란 루트 노드에서 임의의 노드까지 경로를 이루고 있는 노드들을 말한다. 즉, 루트 노드로 부터 Level이 (-1 ~ -n)까지의 노드(서브트리)가 자손 노드가 된다.

위 그림에서 C를 루트로 봤을 때, C는 조상 노드가 되고 그 아래 계층에 있는 모든 노드.즉, H의 서브트리의 구성 노드 {H,K,L,M}을 자손노드가 된다.

 

노드의 차수(degree)는 어떤 노드가 가지고 있는 자식 노드의 개수를 의미한다.

또한 자식 노드가 없는 노드를 단말노드(temival node, 또는 leaf node)라 하며, 자식 노드가 있는 노드를 비단말 노드(nonterminal node)라 한다.

위 그림에서 C노드를 루트 노드로 봤을 때, 자식노드가 1개(H)이기에 차수가 1이 되고 또한 자식 노드가 있기에 단말노드이다. H노드를 루트 노드로 봤을 때는 자식노드가 3개(K,L,M)이기에 차수가 3이 되고 이 노드 또한 자식 노드가 있기에 단말노드가 된다.

K노드를 루트 노드로 봤을 때는 자식노드가 없어 차수가 0이며, 이 노드는 비단말 노드이다.

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

위 그림에서 A노드를 루트 노드로 봤을 때, 높이는 4이다. B노드를 루트 노드로 보면 높이는 2이다.

 

트리의 종류

트리는 크게 일반트리와 이진트리로 나눌 수 있다.

일반적인 트리에서 각 노드들은 서로 다른 개수의 자식 노드를 가진다.

하지만 이진 트리(bjnary tree)는 자식 노드의 개수가 최대 2개로 정해져 있는 트리이다.

일반적인 트리는 자식 노드의 개수에 따라서 노드의 크기가 달라져 즉, 일정하지 않아 프로그램이 복잡하게 된다.

반면에 이진트리는 2개로 정해져 있어 트리를 이해하고 프로그램을 설계하기 편해 이진트리에 대해서만 알아보겠다.

---

이진 트리 소개

이진 트리의 정의

모든 노드가 2개의 서브 트리를 가지고 있는 트리를 이진 트리(binary tree)라 한다.

또한 이진 트리에는 서브 트리간의 순서가 존재한다. 따라서 왼쪽 서브 트리와 오른쪽 서브 트리는 서로 구별된다.

이진트리

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

 

이진트리의 분류

이진 트리는 다음과 같이 분류할 수 있다.

• 포화 이진 트리(full binary tree)
• 완전 이진 트리(complete binary tree)
• 기타 이진 트리

포화 이진 트리는 트리의 각 레벨에 노드가 꽉 차있는 이진트리를 의미한다.

완전 이진 트리는 높이가 k일 때 레벨 1부터 k-1까지는 노드가 모두 채워져 있고 마지막 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진트리이다.

마지막 레벨에서는 노드가 꽉차있지 않아도 되지만 중간에 빈곳이 있어서는 안된다.

따라서 포화 이진트리는 항상 완전 이진트리이지만 완전 이진트리는 항상 포화 이진트리가 되는것은 아니다.

---

이진 트리의 표현

컴퓨터 프로그램으로 표현하는 방식은 다음과 같이 2가지가 있다.

• 배열을 이용하는 방법
• 포인터를 이용하는 방법

배열 표현법

저장하고자 하는 이진 트리를 일단 완전 이진 트리라고 가정하고 이진 트리의 깊이가 k이면 최대 2^(k) - 1개의 공간을 연속적으로 할당한 다음, 완전 이진 트리의 번호대로 노드들을 저장한다.

부모와 자식의 인덱스 사이에는 다음과 같은 공식이 성립한다.

• 노드 i의 부모 노드 인덱스 = i/2의 무조건 내림
• 노드 i의 왼쪽 자식 노드 인덱스 = 2i
• 노드 i의 오른쪽 자식 노드 인덱스 = 2i+1

포인터 표현법

하나의 노드가 3개의 필드를 가지는데, 데이터를 저장하는 필드와 왼쪽 자식 노드와 오른쪽 자식노드를 가리키는 2개의 포인터 필드를 가진다. 이 2개의 포인터를 이용하여 부모노드와 자식 노드를 연결한다.

 

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

typedef struct TreeNode {
	int data;	//해당 노드의 데이터 필드
	struct TreeNode* left, * right;	//왼쪽,오른쪽 자식 노드를 가리킬 포인터 필드
}TreeNode;

int main() {
	TreeNode* n1, * n2, * n3;	//n1, n2, n3노드 생성
	n1 = (TreeNode*)malloc(sizeof(TreeNode));
	n2 = (TreeNode*)malloc(sizeof(TreeNode));
	n3 = (TreeNode*)malloc(sizeof(TreeNode));
	n1->data = 10;
	n1->left = n2;	//n1노드의 왼쪽 자식 노드는 n2
	n1->right = n3;	//n1노드의 왼쪽 자식 노드는 n3
	n2->data = 20;
	n2->left = NULL;	//왼쪽 자식 노드는 공집합
	n2->right = NULL;	//오른쪽 자식 노드는 공집합
	n3->data = 30;
	n3->left = NULL;	//왼쪽 자식 노드는 공집합
	n3->right = NULL;	//오른쪽 자식 노드는 공집합
	free(n1); free(n2); free(n3);
	return 0;
}

---

이진 트리의 순회

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

지금까지 알아본 스택이나 큐는 데이터를 선형으로 저장하고 있어 순회하는 방법이 순차적으로 순회하는 방법밖에 없지만, 트리는 여러가지 종류의 순회법이 있다.

 

이진 트리 순회방법

루트 방문 : V, 왼쪽 서브 트리 방문 : L, 오른쪽 서브트리 방문 : R

이진트리를 순회하는 표준적인 방법에는 전위, 중위, 후위의 3가지 방법이 있다.

이는 루트와 왼쪽 서브트리, 오른쪽 서브트리 중에서 루트를 언제 방문하느냐에 따라 구분된다.

• 전위 순회(preoreder traversal) : VLR
  • 루트 노드를 방문한다.
  • 왼쪽 서브트리를 방문한다.
  • 오른쪽 서브트리를 방문한다.
• 중위 순회(inorder traversal) : LVR
  • 왼쪽 서브트리를 방문한다.
  • 루트노드를 방문한다.
  • 오른쪽 서브트리를 방문한다.
• 후위 순회(postorder traversal) : LRV
  • 왼쪽 서브트리의 모든 노드를 방문한다.
  • 오른쪽 서브트리의 모든 노드를 방문한다.
  • 루트노드를 방문한다.