Binary Tree Traversal
Traversal(순회)란 무엇일까요?
단순히 말하면 탐색하는 것을 의미합니다.
특정한 자료구조 안에 있는 원소들을 방문한다면 전부 Traversal이라 말 할수 있습니다.
for(int i=0;i<arr.length;i++){
System.out.println(arr[i]);
}
위의 코드는 배열을 순회하는 대표적인 코드입니다.
배열같이 단순한 자료구조라면 다음과 같이 순회하면 되지만
Tree자료구조의 경우 어떨까요?
Tree에서 순회는 대표적으로 3가지가 존재합니다.
- preOrder (전위)
- inOrder (중위)
- postOrder (후위)
Tree안에 있는 노드들을 방문한다는 개념은 전부 같지만
순서의 차이가 존재합니다.
preOrder 는 이름에서 알 수 있듯이 구조가 다음과 같습니다.
노드 출력 -> left 방문-> right 방문
postOrder 또한 이름에서 알 수 있듯이
left 방문 -> right 방문 -> 노드 출력 의 구조를 가집니다.
그렇다면 inOrder는 다음과 같겠죠
left 방문 -> 노드 출력 -> right 방문
이런 구조를 가지고 자바 코드로 구현해 보겠습니다.
public static void preOrder(BinaryTree bst) {
if (bst == null) {
return;
}
System.out.print(bst.getValue()+" ");
printPreOrderNumber(bst.left);
printPreOrderNumber(bst.right);
}
현재 노드가 가지고 있는 value를 출력합니다.
또한 재귀적으로 해당 노드의 left , right를 방문합니다.
만약 노드가 null이라면 return이 되는 BaseCase를 가집니다.
inOrder와 postOrder는 위의 코드와 유사하게 순서만 바꿔주면 됩니다.
public static void inOrder(BinaryTree bst) {
if (bst == null) {
return;
}
preOrder(bst.getLeft());
System.out.print(bst.getValue()+" ");
preOrder(bst.getRight());
}
public static void postOrder(BinaryTree bst) {
if (bst == null) {
return;
}
postOrder(bst.getLeft());
postOrder(bst.getRight());
System.out.print(bst.getValue()+" ");
}이렇게 순회의 대표격인 pre,in,post Order를 알아 봤습니다.
순회에는 이 뿐만 아니라 더 다양한 방법이 존재하는데요
좀더 심화된 방법으로 BFS(Breadth-First Search) 를 알아 보겠습니다.
여태까지의 순회는 재귀적으로 구성됐지만 위의 순회는 재귀적이지 않습니다.
Level Order Traversal (BFS)는 Queue 자료구조를 쓰는 대표적인 알고리즘입니다.
구조는 다음과 같습니다.
- Tree의 Root 노드를 갖고있는 Queue 생성
- Queue를 pop하면서 노드 출력
- 노드의 left가 있다면 Queue에 추가
- 노드의 right가 있다면 Queue에 추가
- Queue의 size가 존재하지 않을떄까지 2~4번 반복
이것을 그대로 코드로 옮긴다면 다음과 같습니다.
public static void bfs(Queue<BinaryTree> q) {
while (!q.isEmpty()) {
BinaryTree temp = q.poll();
System.out.print(temp.getValue()+" ");
if (temp.getLeft() != null) {
q.add(temp.getLeft());
}
if (temp.getRight() != null) {
q.add(temp.getRight());
}
}
}만약 다음과 같은 Tree가 있다면 순회의 결과는 다음과 같습니다.
preOrder : F , B , A , D , C , E , G , I , H
inOrder : A , B , C , D , E , F , G , H , I
postOrder : A , C , E , D , B , H , I , G , F
levelOrder : F , B , G , A , D , I , C , E , H