1. Types of Binary Tree
Full Binary Tree (포화 이진 트리)
모든 노드의 자식의 개수가 0개 이거나 2개인 이진트리를 말한다. 포화 이진 트리에서는 leaf node 들의 개수(L)가 internal node 들의 개수(I) 에다가 1을 더한 값이다.
L = I + 1Complete Binary Tree (완전 이진 트리)
완전 이진트리는 낮은 레벨에서부터, 왼쪽에서부터 1 부터 n까지 노드의 번호를 매길 수 있는 구조의 트리이다. 다시 말하면 트리의 height 가 k 일때, k — 1번째까지는 모든 노드가 있어야 하고, 높이 k에 존재하는 노드들은 왼쪽에서부터 순서대로 있어야 한다.
이렇게 번호가 부여되면, k번 노드의 부모는 k/2, 왼쪽 오른쪽 자식은 2k, 2k + 1 이다.
모든 노드가 연속적으로 배치되어 있기 때문에 이 구조의 트리는 배열에 저장하기가 용이하다.
2. BFS and DFS for Binary Tree
트리의 순회하는 방법은 BFS, DFS 두 가지 방법이 있다.
Breadth First Traversal (= Level Order Tree Traversal)
BFS 는 Level Order Tree Traversal, 즉, 말 그대로 레벨 별로 노드를 방문하는 트리 순회 방법을 말한다.
위 트리의 노드 방문 순서는 1, 2, 3, 4, 5 이다.
트리의 BFS 를 구현하는 방법은 두가지가 있다.
레벨이 파라미터로 주어질때 해당 레벨의 모든 레벨을 print 하는 방법과 큐를 이용하는 방법이다.
첫번째 방법은 2개의 메소드를 만들어 구현한다. 주어진 레벨의 모든 노드들을 출력하는 printGivenLevel() 과 전체 트리를 출력하는 printLevelOrder() 이다.
이렇게 구현할 경우 O(n²) 의 성능을 보인다.
두번째 방법인 큐를 이용하는 방법은 문제 하나를 예로 들어서 설명해 보려고 한다.
다음은 구현코드이다.
트리의 BFS 를 구현하는 방법은 큐를 하나 생성하고, 레벨별로 트리의 노드를 담을 List 를 마련한다. 그런 다음 처음에 큐에 root 노드를 삽입하고, root 노드의 왼쪽, 오른쪽 노드를 큐에 삽입한다. 그 다음 root 노드를 큐에서 추출해 낸다.
트리의 BFS(=Level Order Traversal)에서 노드들이 큐에 삽입되는 과정을 작업단위로 나타내보면,
- 맨 처음에 단 한번만 루트 노드가 큐에
offer()된다. - 각 subtree 의 루트노드의
left,right가 큐에offer()된다.
또한 큐의 사이즈를 구하여 각 레벨에 들어있는 노드 개수 만큼 왼쪽, 오른쪽 노드가 큐에 삽입되는 작업이 진행되도록 했다. 다시 설명하면, 위의 문제를 예를들면 레벨 2에 해당하는 노드들은 9, 20 이고 이전 작업에 의해서 현재 큐에는 9, 20 만 존재한다. 다음 레벨의 노드들을 하나의 리스트에 담기 위해서 9 의 자식노드들과 20 의 자식노드들을 모두 큐에 담아야 하므로 자식 노드들을 큐에 삽입하는 for 문을 현재 큐의 사이즈(size = 2) 만큼 실행해야 한다.
이때 쓰이는 java.util.Queue 의 메소드들을 간단하게 정리해보면,
offer(): 큐에 노드를 삽입한다.peek(): 큐의 head 의 삽입된 노드를 삭제하진 않고 검색이 가능하다.poll(): 큐에 head 에 삽입된 노드를 삭제하면서 검색한다.
이다.
Depth First Traversal
트리의 깊이 우선 탐색 방법에는 루트노드의 방문 시점에 따라 세 가지 방법으로 나눌 수 있다. 다음 트리를 예로 들어서 설명 해보겠다.
- Inorder (Left, Root, Right) : 4 2 5 1 3
- Preorder (Root, Left, Right) : 1 2 4 5 3
- Postorder (Left, Right, Root) : 4 5 2 3 1
이때 유의해야 할 점은 항상 Left 방문 후에 Right 방문이 이루어진다는 점이다.
각 순회 방식의 구현방법과 어떤 경우에 이런 순회 방식이 유용한지에 대해서 알아보자.
Inorder Traversal :
Inorder traversal 은 binary search tree(BST) 일 경우에 노드들을 오름차순대로 나열할 수 있다는 장점이 있다. (참고로 위에서 예로 든 binary tree 는 BST 가 아니다.)
Preorder Traversal :
Preorder traversal 은 트리를 복사할 때 사용한다. 또한 expression tree 의 prefix expression 을 얻는데도 유용하다는데 이는 해당 문제를 만나면 추후에 정리해보도록 하겠다.
Postorder Traversal :
Postorder traversal 은 트리를 삭제하는데 사용한다고 한다. 또한 expression tree 의 postfix expression 을 얻는데도 유용하다는데 이 또한 해당 문제를 만나면 추후에 정리해보도록 하겠다.
세개의 traversal 에 대한 구현은 간단하다.
현재위치의 node가 존재하지 않을때는 return 을 해주어 다음 순서의 노드로 넘어가게 하고, 해당 순서대로 재귀호출을 이용해 구현하면 된다.
