트리는 꽤 다양한 방법으로 표현할 수 있습니다.
일단 지난 글에서 썼던 트리를 다시 가져와봅시다.
단순한 표현 방법
첫 번째로, 이 그림 자체로도 트리를 표현할 수 있습니다.
두 번째로는 중첩된 괄호(Nested Parenthesis)로 표현할 수 있습니다. 읽기 어렵지만, 트리를 하나의 수식처럼 표현할 수 있습니다.
(A((B(E)(F(J)))(C(G))(D(H(K)(L)(M))(I))))
이렇게 표현할 수 있습니다.
세 번째 방법은 코드로 구현할 때 가장 많이 쓰이는 구조체 를 활용하는 방법입니다.
구조체를 활용한다고 하면 가장 먼저 떠오르는 방법은 각 노드의 자식들을 모두 저장하는 방식일 것입니다.
하지만 차수가 노드마다 달라지는 트리에서는 적용하기 어렵다는 단점이 있습니다. 가변 배열이나 연결리스트를 사용하면 되겠지만, 필요 이상으로 복잡해지는 경우가 발생합니다.
Left Chird-Right Sibling
그래서 나온 해결책이 왼쪽 자식-오른쪽 형제(Left Chird-Right Sibling) 표현법입니다. 이 표현법은 이름 그대로 한 개의 포인터는 가장 왼쪽의 자식을, 다른 포인터는 자신 바로 오른쪽에 있는 형제를 가리켜 차수가 다양한 트리를 각 노드 당 2개의 포인터로만 표현할 수 있습니다.
대략 이런 형태로 구성이 됩니다.
다음 글부터는 이진 트리를 다룰 예정입니다.