트리의 순회 - 레벨 순서 순회

1. 레벨 순서 순회란?

 

레벨 순서 순회는 위에서 아래로, 좌에서 우로 순차적으로 순회를 하는 것입니다.

위의 트리에서 레벨 순서 순회를 할 경우, 결과는

1 - 2 - 3 - 4 - 5 - 6 이 됩니다.

개념적으로는 가장 이해하기 쉽고 간단한 순회 방법이지만, 구현은 상대적으로 까다로운 편입니다.

 

2. 구현

 

1) 재귀

 

Queue<TreeNode> q = new LinkedList<>();

public void levelOrder(TreeNode node) {
    System.out.print(node.getData() + " "); // ①
    q.add(node.getLeftChild()); // ②
    q.add(node.getRightChild());
    TreeNode temp = q.remove(); // ③
    if(temp != null) levelOrder(temp); // ④
}

① 주어진 node의 값을 먼저 출력하고 

② node의 왼쪽 자식과 오른쪽 자식을 큐에 저장합니다.

③ 큐에서 첫 번째 노드를 꺼내어 temp에 저장한 뒤,

④ temp가 null이 아니라면 temp에 대하여 다시 levelOrder() 를 재귀적으로 호출합니다.

최초에 root를 넣어 실행하고, 트리의 모든 원소를 방문한 뒤 큐가 비워지게 되면 종료됩니다.

 

2) 반복

 

q.add(root);

while(!q.isEmpty()) {
    TreeNode temp = q.remove();
    if (temp != null) {
        System.out.print(temp.getData() + " ");
        if(temp.getLeftChild() == null || temp.getRightChild() == null) continue;
        q.add(temp.getLeftChild());
        q.add(temp.getRightChild());
    }
}

q에 먼저 root를 삽입합니다.

q가 비워질 때까지 while문이 실행되며, 큐에서 값을 하나 꺼내 출력하고 왼쪽, 오른쪽 자식을 큐에 삽입합니다.

 

3. 주저리주저리

처음에 1)로 구현을 해서 결과가 나오는 것을 확인했지만 자식이 null인 경우에도 큐에 넣고 빼고 하는 불필요한 작업을 한다는 문제점을 발견했습니다. 그래서 예외 처리를 해줬더니 에러가 발생했고, 해결책을 찾는 과정에서 굳이 재귀함수를 쓸 필요가 없다는 걸 깨닫게 되었습니다. 그렇게 2)가 탄생한 것입니다.

시간날 때 자료구조 책을 펼쳐보고 더 나은 방법이 있다면 추가하도록 하겠습니다.