Tree의 표현(representation)

Tree도 ADT기에, 여러 방식의 표현법이 존재한다. 트리의 차수나 노드의 수 등에 영향을 끼치지 않는, 모든 경우의 트리를 표현할 수 있는 표현 방식들을 알아보자.

Linked list 표현

선형 자료구조인 linked list를 응용하는 방식이다. 단방향/양방향에 관계 없이 연결 리스트는 오직 연결되어 있는 값과의 link를 위해 사용했는데, 여기서는 child node와의 연결을 표현하기 위해 사용한다.

노드의 삽입과 삭제가 용이하나, 각 노드의 차수만큼 가변적인 포인터 필드를 가져야 한다는 문제가 있다.

Left-Child Right-Sibling(LCRS) 표현

Sibling은 동일한 parent node를 가지고 있는 노드를 의미하며, right sibling은 바로 오른쪽에 있는 sibling을 의미한다. 따라서 LCRS 표현에서는 각 노드가 데이터|가장 왼쪽 child의 주소|바로 오른쪽 sibling의 주소로 이루어진다. 아래 그림은 tree를 LCRS로 표현하는 예다.