[C언어와 함께 자료구조를] 트리 (Tree) - 용어 정리와 이진트리

지금까지 다뤄본 자료구조들을 모두 선형적인 일차원 구조였습니다. 즉, 처음부터 끝까지 차례로 이동하면 모든 노드를 거칠 수 있었죠. 하지만 트리(Tree)는 대표적인 비선형구조(Non-linear structure)로 2차원구조 입니다.

트리(Tree) 구조는 일상에서도 많이 볼 수 있는데요, 대표적으로 탐색기 폴더구조를 들 수 있습니다. 로컬디스크(C:)에 여러 폴더들이 존재하고 그 하위 폴더 그 아래 하위 폴더 등으로 구성되는 구조입니다.

탐색기 폴더 구조

트리(Tree) 구조는 나무를 거꾸로 뒤집어 놓은 것 같은 모양입니다. 가장 위에 있는 노드를 root라 하고 거기서 시작하여 가지 (link)가 밑으로 향하며 맨 아래에 잎(leaf)이 달려 있습니다.

트리(Tree) 구조

위 그림을 가지고 트리(Tree)구조에서 일반적으로 사용하는 용어를 정리해 보도록 하겠습니다.

• 노드(Node) : 위에서 동그라미 모양으로 되어 있고 정보를 담고 있는 곳을 의미하며 버텍스(Vertex)라고도 합니다.
• 링크(Link) : 노드를 선으로 연결한 것으로 엣지(Edge)라고도 부릅니다.
• 루트(Root) : 위 그림에서 트리(Tree)의 시작인 노드를 가리킵니다.
• 레벨(Level) : 루트 노드인 A를 level1, B,C,D를 level2, E~I를 level3, J를 level4라 부릅니다. root를 level1으로 놓고 한 단계씩 깊어질 수록 level이 1씩 증가합니다.
• 부모-자식(Parent-Children) : A와 B의 관계를 보면 위에 있는 A가 B의 부모입니다. 반대로 B는 A의 자식입니다. level이 1차이나는 노드간의 관계를 말합니다.
• 조부모(Grandparent) : 예상 하셨겠지만 level이 2차이나는 노드간의 관계를 말합니다. A와 E, C와 J등의 관계에서 앞의 노드를 의미합니다. 마찬가지로 Grandchildren의 의미도 이해하시겠죠?
• 형제(Sibling) : 같은 level의 노드의 관계를 의미합니다. B,C,D의 관계 또는 E,F,G,H,I의 관계를 말하죠.
• 잎(Leaf) : E,F,G,H,J,D와 같이 자식이 없는 노드를 말합니다. 끝이라는 의미로 터미널 노드(Terminal Node)라고도 하고, 외부노드(External Node)라고도 부릅니다. 반대로 A, B, C, I같이 자식이 있는 노드는 논터미널 노드(Nonterminal Node) 또는 내부노드(Internal Node)라고 합니다.
• 서브트리(Subtree) : 트리구조에서 일부분을 서브트리라고 합니다. 위 그림에서 A의 자식인 B,C,D를 각각 루트로 보면 작은 3개의 트리로 나눠서 생각할 수 있습니다.
• 이진트리(Binary Tree) : 자식 노드를 최대로 2개까지 가질 수 있는 특수한 형태의 트리입니다. 이진트리는 비교적 실용적이고 구현하기가 용이하므로 가장 널리 사용합니다.

바이너리 트리

위 그림의 두 이진트리(Binary Tree)를 보면 왼쪽은 마지막 레벨(Level)을 제외하고 꽉 차있네요. 오른쪽은 모든 레벨이 꽉차 있습니다. 왼쪽을 꽉차있는 이진트리(Full binary tree) 오른쪽을 완전 이진트리(Complete binary tree)라고 부릅니다.

 

이진트리의 기본 자료형은 다음과 같이 정의 할 수 있겠네요.

 

typedef struct _node {
	char key;
	struct _node *left;	/* 왼쪽 자식 노드 */
	struct _node *right;	/* 오른쪽 자식 노드 */
} node;

위와 같이 정의한 이진트리 자료형으로 다음시간에는 트리 순회 (Tree Traverse)를 해보겠습니다.