19-5-나.이진 트리

노드의 차수에는 제한이 없으므로 임의 개수의 자식들을 가질 수 있다. 이런 노드를 표현하려면 다음과 같은 구조체를 선언해야 한다.

 

struct Node

{

     int data;

     Node *link;

};

 

data는 이 노드가 저장할 실제 데이터이며 필요에 따라 얼마든지 더 많은 멤버들을 포함할 수 있다. link는 자식 노드들로 연결되는 링크의 배열이며 자식의 개수만큼 동적으로 할당된다. 또는 최대 차수를 미리 알 수 있다면 정적 배열로도 선언할 수 있다. 이런 노드들이 서로를 가리킴으로써 트리를 구성한다.

자식의 개수가 정해져 있지 않기 때문에 노드의 차수에 따라 링크의 개수가 가변적이다. 동적 할당해서 만드는 노드의 멤버가 또 동적 할당을 한다면 관리하기 무척 번거롭고 불편해진다. 그렇다고 해서 최대 차수만큼의 정적 배열을 할당하면 미사용 링크가 많아져 메모리의 낭비가 심하며 최대 차수 이상은 표현하지 못하는 한계가 있다.

그래서 임의 차수를 지원하는 트리는 잘 사용되지 않으며 차수의 최대값을 일정한 크기로 제한한다. 이진 트리(Binary Tree)는 모든 노드의 차수가 2이하인 트리이며 구조가 단순하기 때문에 현실적으로 가장 많이 사용된다. 이진 트리의 노드는 자식을 최대 2개까지만 가질 수 있으므로 다음과 같은 구조체로 간단하게 표현할 수 있다.

 

struct Node

{

     int data;

     Node *left;

     Node *right;

};

 

노드에 저장되는 데이터와 좌우 두 개의 링크를 가진다. left가 왼쪽 자식을 가리키며 right가 오른쪽 자식을 가리킨다. 물론 양쪽 자식이 모두 존재할 필요는 없으며 자식이 없는 잎 노드일 경우 링크는 모두 NULL값을 가질 것이다. 이렇게 되면 한 노드의 좌우 자식 노드는 쉽게 알 수 있는데 이 노드의 부모는 알 수 없다는 문제점이 있다. 만약 부모 노드까지도 기억하고 싶다면 parent라는 포인터를 하나 더 추가하면 된다. 이진 트리에 좀 더 엄격한 제약을 가하면 다음과 같은 트리를 정의할 수 있다.

 

포화 이진 트리(Full Binary Tree) : 트리의 높이까지 모든 노드가 가득찬 트리이다. 높이가 1이면 루트 하나만 있으므로 노드 개수는 1개이며 높이가 2이면 루트와 양쪽 자식을 합쳐 세 개의 노드가 존재한다. 높이가 3이면 7개, 4이면 15개이며 일반적으로 높이가 n인 포화 이진 트리의 노드 개수는 2n-1개이다.

완전 이진 트리(Complelte Binary Tree) : 포화 이진 트리의 노드를 좌에서 우로, 위에서 아래로 번호를 붙였을 때 번호가 큰 뒤쪽 노드만 생략된 트리이다. 같은 높이의 포화 이진 트리와 대응되는 노드의 순서값이 일치한다. 다음 그림을 통해 두 이진 트리를 구분해 보자.

첫 번째 트리의 높이는 3인데 노드의 개수가 7(23-1)개이므로 이 트리는 포화 이진 트리이다. 보다시피 빈틈없이 모든 노드가 가득 차 있으며 잎 노드를 제외하고는 모두 차수가 2이다. 포화 이진 트리에서 7, 6, 5, 4를 차례대로 생략할 때 이 트리를 완전 이진 트리라고 한다. 그러나 아래쪽은 순서값이 빠른 노드가 먼저 생략되어 포화 이진 트리의 노드 순서값과 같지 않으므로 완전 이진 트리는 아니다.

정의가 조금 복잡하지만 쉽게 말하자면 포화 이진 트리에서 중간에 빠진 노드가 없는 트리를 완전 이진 트리라고 한다. 높이가 n인 완전 이진 트리의 노드 개수는 2n-1보다 크거나 같고 2n-1보다 작거나 같다. 포화 이진 트리는 물론 완전 이진 트리의 일종이다.