트리(자료구조)의 리스트 표현 방법

트리를 다음과 같은 형식의 리스트를 이용하여 재귀적으로 표현한다.

(루트노드(서브 트리1, 서브 트리2, .... , 서브 트리n)) 

서브 트리도 트리이므로 이러한 리스트가 중첩되어 표현된다. 예제를 통해 알아보자.

예제로 사용할 트리

 위의 트리를 리스트 표현 방법으로 표시하면 다음과 같다.

                                   ( A ( B ( E , F ) , C ( G ) , D ) )

예제 트리를 내부적으로 표현하면 다음과 같다.

각각의 노드는 가변적인 포인터 수를 가지므로 효율적인 표현 방법이 되지 못한다. 이 문제를 해결하기 위해 포인터 수를 2개로 고정한 방법이 left child, right sibling 표현 방법과 이진 트리 표현 방법이다.


고정된 포인터 수를 가지는 표현 방법으로 다음과 같은 노드 구조를 가진다.
 

데이터
자식노드	형제노드

   하나의 포인터를 자신의 첫번째 child 노드를 가리키고, 또 하나의 포인터는 인접한 sibling 노드를 가리키도록 한다.
                                 

                               예제 트리                                   Left Child, Right Sibling

포인터의 수가 2개로 고정되어 있으므로 리스트 표현 방법보다 효율적이다.

출처 : http://internet512.chonbuk.ac.kr/