10-2. 숲

02. 숲

숲의 정의

- 분리된 트리 모임

- 트리의 모임

- 0개 이상의 분리된 트리 집합

숲 : n (n≧0)개 이상의 분리된 트리 집합

- 트리에서 루트(혹은 다른 노드)를 제거하면 숲을 쉽게 얻을 수 있음

- 반대로 숲을 연결하면 트리를 만들 수도 있음

 

- 먼저 각 트리 (T_i)를 이진 트리(T_i^BT )로 바꿈 (이때 T_i^BT 의 루트는 왼쪽 서브트리만 가짐)

- 다음은 T_i^BT 의 루트를 최상위 루트로 하고, 왼쪽 자식은 그 왼쪽 서브트리, 오른쪽 자식은 나머지들의 이진 트리(BT_2~n)가 되도록 함

 

 

이진 트리로 변환 방법

 

 

숲의 이진트리 변환