[트리] 트리와 노드의 표현 방법

트리 표현 방법

거꾸로 세운 나무

중첩된 괄호(Nested Parenthesis)

위 트리를 해당 표현법으로 나타내면
(1(2(4)(5(7)(8)))(3(6(9))))

이 방법은 읽기는 어렵지만 트리를 하나의 공식처럼 표현할 수 있다.

중첩된 집합(Nested Set)

트리가 하위 트리의 집합이라는 관계를 잘 표현할 수 있다.

들여쓰기(Indentation)

자료의 계층적인 특징을 잘 나타낸다.

노드 표현 방법

노드의 표현법은 부모와 자식, 형제 노드를 서로 연결짓는 방법이다.

트리 노드를 표현하는 방법에는 두 가지가 있다.

• N-링크(N-Link)
• 왼쪽 자식-오른쪽 형제(Left Child-Right Sibling)

N-Link

N-링크는 노드의 차수가 N이라면, 각각 자식 노드를 가리키는 N개의 링크를 갖도록 구성하는 방법이다.
이 노드로 트리를 이룬다면 다음과 같은 모습이 된다.

이 표현법은 차수가 노드마다 달라지는 트리에는 적용하기 힘들다.
예를 들어 폴더 트리 같은 경우, 차수가 0부터 수백, 수천이 될 수 있다.
동적 메모리를 할당하여 가변 배열을 만들거나 링크드리스트를 사용하면 이 문제를 풀 수 있지만, 트리를 더욱 복잡하게 만드는 것이 문제다.
왼쪽 자식-오른쪽 형제 표현법은 이 문제를 해결한다.

Left Child-Right Sibling

왼쪽 자식과 오른쪽 형제에 대한 포인터를 갖는 구조이다.