9장 트리

 

트리는 비선형 자료구조 중에서 자료들 간에 계층관계를 가진 계층형 자료구조이다.

이진트리

모든 노드의 차수를 2 이하로 정하여 전체 트리의 차수가 2 이하가 되도록 만든 이진 트리는 왼쪽 서브 트리와 오른쪽 서브 트리를 가지는데, 서브 트리 역시 이진 트리가 된다. n개의 노드로 구성된 이진 트리는 (n-1)개의 간선을 가지며, 높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 h+1개며, 노드의 최대 개수는 (2^h+1 - 1)개가 되는 성질을 가진다.

 

이진 트리를 순차 자료구조 방식을 이용하여 표현하는 방법은 높이가 h인 포화이진트리의 노드 번호를 배열의 인덱스로 사용하여 1창원 배열로 표현하는 것이다. 1차원 배열에서 인덱스 계산을 간단히 하기 위해서 인덱스 0번은 실제로 사용하지 않고 비웓두고 항상 인덱스 1번부터 노드를 저장한다. 그러면 노드 i의 부모노드의 인덱스는 [i/2]가 되고, 왼쪽 자식노드의 인덱스는 ix2, 오른쪽 자식노드의 인덱스는 ix2+1이 되는 인덱스 관계가 성립된다.

 

 

[위 그림] 노드 번호가 5번이고 인덱스 5번에 저장되어 있는 노드 E의 부모 노드가 저장된 인덱스는 [5/2] = 2 가 된다. 그리고 노드 E의 왼쪽 자식 노드의 인덱스는 2x5 = 10이 되고, 오른쪽 자식 노드는 (2x5)+1 = 11이 된다. 루트 노드는 배열 인덱스 1에 저장되어 있다.

 

이진 트리를 연결 자료구조 방식으로 표현하기 위해 사용하는 노드는 데이터를 저장하는 데이터 필드와 왼쪽 자식노드를 연결하는 왼쪽 링크 필드, 오른쪽 자식노드를 연결하는 오른쪽 링크 필드로 구성된다. 자식노드가 없을땐 null을 저장한다.