포레스트
위키백과 ― 우리 모두의 백과사전.
그래프 이론에서 포레스트는 하나 이상으로 이루어진 트리의 집합을 의미한다. 그림의 상단에 위치한 A와 L을 각각 루트로 하는 두 개의 트리는 하나의 포레스트이다.
[편집] 이진 트리로의 변환
모든 포레스트는 하나의 이진 트리로 변할 수 있다. 기본 원칙은 자식은 왼쪽 자식으로, 형제는 오른쪽 자식으로 변환한다는 것이다. 다음 순서로 합쳐보자.
1. 왼쪽 트리의 루트는 A, 오른쪽 트리의 루트는 L이다. 첫번째 루트인 A를 루트로 잡고 L을 A의 오른쪽 자식으로 잡자.
2.1. A의 자식들은 B,C,D이다. 첫번째 자식 B를 왼쪽 자식으로 잡고 B의 형제인 C는 B의 오른쪽 자식으로 C의 형제인 D는 C의 오른쪽 자식으로 잡자.
2.2. L의 자식은 M,N이다. 첫번째 자식인 M을 L의 왼쪽 자식으로 잡고 M의 형제인 N을 M의 오른쪽 자식으로 잡자.
3. B의 자식은 E,F이다. 첫번째 자식인 E를 B의 왼쪽 자식으로 잡고 E의 형제인 F를 E의 오른쪽 자식으로 잡자.
이 과정은 기계적인 과정이다. 트리가 3개, 4개, 심지어 100개라도 같은 방식으로 이루어 진다. 단 하나의 트리만 있더라도 같은 방법으로 이진 트리로 변경할 수 있다.
