이진트리 순회(깊이우선 탐색)

깊이우선 탐색(DFS)를 활용하여 이진트리를 순회할 수 있다.

순회 방법에는 (1)전위순회, (2)중위순회, (3)후위순회 이렇게 3가지의 방법이 있다.

트리는 기본 단위로 부모노드와 왼/오 자식노드를 가지고 있다. 

전위 순회는 부모-왼-오 순서를 가지며, 중위 순회는 왼-부모-오 순서를 가진다. 후위 순회는 왼-오-부모 순서로 순회를 한다. 그림을 토대로 각각 순회 방법대로 적용한다면 아래와 같다.

 

전위 순회를 한다면, 1-2-4-5-3-6-7 순서로 순회를 한다.

중위 순회를 한다면, 4-2-5-1-6-3-7 순서로 순회를 한다.

후위 순회를 한다면, 4-5-2-6-7-3-1 순서로 순회를 한다.

 

이를 직접 코드로 구현을 하는 것이 포스팅의 목적이다.

Node클래스를 만들어서 int타입의 data와 왼/오 Node를 구성한다.

DFS메서드를 만들어서 재귀 호출을 하게 구현하였다.

class Node{
    int data;
    Node lt, rt;
 
    Node(int val){
        data = val;
        lt=rt=null;
    }
}
 
public class Practice {
    Node root;
    public void DFS(Node root){
        if(root==null)
            return;
        else{
            //System.out.print(root.data + " "); - 전위 순회
            DFS(root.lt); 
            //System.out.print(root.data + " "); - 중위 순회
            DFS(root.rt);
            //System.out.print(root.data + " "); - 후위 순회 
        }
    }
 
    public static void main(String[] args){
        Practice pr = new Practice();
        pr.root = new Node(1);
 
        pr.root.lt = new Node(2);
        pr.root.rt = new Node(3);
 
        pr.root.lt.lt = new Node(4);
        pr.root.lt.rt = new Node(5);
 
        pr.root.rt.lt = new Node(6);
        pr.root.rt.rt = new Node(7);
 
        pr.DFS(pr.root);
    }
}

위의 코드에서 보면 알 수 있듯이, 출력 메서드가 어디에 위치하느냐에 따라 순회의 결과가 변경되어 나타난다. 

이는 재귀함수의 동작을 스택 프레임과 연관지어 생각하면 원리를 이해할 수 있다.

 

스택프레임(Stack Frame)이란?

함수가 호출될 때마다, LIFO 스택에 적재되는 방식으로 생성된다. 스택 프레임에는 함수와 관계되는 지역변수(local variables), 매개변수(parameters), 복기 주소(return address)로 구성되어 있다. 

복기 주소는 스택의 상위 스택 프레임이 실행되고 나서 돌아갈 주소를 담고 있는 것이다.

 

DFS(4)가 호출되어 스택프레임에 쌓이고 다시 DFS메서드를 실행한다. 

Node의 data가 4일 때에는 왼쪽, 오른쪽 자식 노드가 모두 null값을 가지고 있다.

DFS(null)이 호출되고 코드를 작동하는데 if 조건문에 걸리게 되어 return하여 pop된다.

다시 DFS(4)의 오른쪽 자식 노드를 호출하는데 이것도 null이므로 위의 과정을 반복한다. 

 

 

 

 

DFS(4)의 자식 노드를 호출하는 DFS메소드가 모두 pop된 다음, DFS(4)의 복기주소로 돌아가 수행하려하는데 마지막 출력메서드만 남았다. 그러므로 4를 출력해준 다음 DFS(4)는 종료되어 pop이 된다. 그리고 다시 DFS(2)메소드의 line28부터 수행한다.