[DS] Binary Tree

1. Binary Tree 정의

  제일 상위 레벨에 있는 루트 노드를 기준으로 2개의 서브트리를 가지며, 두개의 서브트리도 모두 이진트리이어야 한다. 또한 노드가 위치할 수 있는 곳에 노드가 없다면 공집합 노드가 있다고 간주하게 되므로 [그림1]과 같이 한쪽에 치우친 트리도 이진트리이고 심지어 [그림2]와 같이 노드 1개만 있어도 이진트리라고 할 수 있다. 

[그림1]                                                    [그림2]

 

2. Binary Tree 구현 방법

1. 배열을 이용
    - 인덱스를 활용할 수 있기에 탐색에 용이하지만 유연하게 사용하기 힘들다.
2. 링크드 리스트를 이용
    - 이해하기 쉽고 유연하며, 메모리를 동적으로 사용하기 좋다.

이러한 특징으로 우선순위큐(Heap) 등과 같이 완전이진트리 구조를 갖는 경우에는 배열로 많이 구현하고 그 외에는 대부분 링크드 리스트로 구현하게 된다.

*완전이진트리 : 노드가 위에서 아래로, 왼쪽에서 오른쪽으로 순서대로 빈틈없이 채워진 트리

 

 

3. Binary Tree 순회

  이진트리 역시 노드 삭제 또는 출력 등을 위해 모든 노드를 방문해야하는 '순회'가 필요하며 트리의 정의에서 봤듯이 트리구조는 재귀적인 구조적 특징이 있으므로 재귀를 이용하면 순쉽게 순회를 구현할 수 있다. 순회 방법은 아래와 같이 루트노드를 언제 방문하냐에 따라 세가지 방식으로 구현될 수 있다.

    - 전위 순회(Preorder Traversal)
    - 중위 순회(Inorder Traversal)
    - 후위 순회(Postorder Traversal)