DFS 이진트리 순회 [전위순회, 중위순회, 후위순회] with Java

들어가며

DFS 알고리즘을 이용한 이진트리 순회과정을 코드로 구현하고 그림을 통해 이해하려고 한다.

 

순회의 방문 순서는 다음과 같다.

전위순회 : root, left, right

중위순회 : left, root, right

후위순회 : left, right, root

즉 root의 위치가 어딨는지에 따라 다르므로 root 기준으로 생각하면 된다.

 

코드 구현

먼저 하나의 Node라는 객체를 생성해야 한다.

Node 는 하나의 정점이라고 생각하면 된다.

Node 는 field로 data, left, right 를 가지는데 left, right를 연결된 노드라고 생각하면 된다. 

class Node {
    int data;
    Node lt;
    Node rt;
    public Node(int data) {
        this.data = data;
        lt = rt = null;
    }
}

public class Tree_Exam {

    public static void DFS(Node root) {
        if (root == null) {
            return;
        }

        // 구현예정
    }

    public static void main(String[] args) {
        Node root = new Node(1);
        root.lt = new Node(2);
        root.rt = new Node(3);

        root.lt.lt = new Node(4);
        root.lt.rt = new Node(5);

        root.rt.lt = new Node(6);
        root.rt.rt = new Node(7);

        DFS(root);
    }
}

 

main에서 root를 기준으로 가지를 뻗어 나간다.

위 코드를 그림으로 그려보면 다음과 같다.

 

100 ~ 700은 Node 클래스의 주소이다.

실제 메모리에 저장되는 주소값은 아니지만 이해를 돕기위해 임의로 지정하였다.

 

다음으로 1 ~ 7은 각각의 노드의 data이다.

마지막으로 밑에 두칸은 left, right Node의 주소이다.

 

DFS 함수 추적

 

전위순회 방식을 예로 살펴보자 [root, left, right]

1 2 4 5 3 6 7 순서이다.

DFS 함수 내의 변경 부분만 봐보자.

public static void DFS(Node root) {
    if (root == null) {
        return;
    }

    System.out.print(root.data + " "); // line 20
    DFS(root.lt); // line 21
    DFS(root.rt); // line 22
}

 

먼저 전위순회이므로 root.data를 제일 먼저 출력한다.

그다음으로 left, right를 순서대로 타고 내려가야 한다.

함수는 stack구조와 똑같이 작동하므로 stack 을 그려 보면서 이해해보자.

stack에는 이전 위치로 돌아가는 주소와 line을 기입하겠다.

 

main 메소드에서 첫 DFS(root)를 호출했으므로 주소가 100인 Node로 시작이 된다.

null 이 아니므로 if 문 밑으로 가서 자신의 data인 100을 출력한다 (line 20)

 

출력 -> 1

 

그다음 21번 line에서 DFS 함수를 다시 실행하는데 root.lt 를 인자로 넘긴다.

돌아와야 하는 주소가 100이고 line21로 돌아와야 하니 stack에는 다음과 같이 쌓이게 된다.

편의상 DFS 함수를 D로 정의하겠다.

 

그럼 root.lt의 주소는 200이고 null이 아니므로 다시 if 문 밑으로 이동하게 된다.

다시 자신의 data를 찍고 DFS(root.lt) 를 가게 되면 이번에는 주소가 400인 Node로 이동한다.

출력 -> 1 2

다시 본인의 data 출력

출력 -> 1 2 4

Node (400)의 left는 null 이므로 if문에서 걸려서 바로 return을 하게된다.

즉 함수를 종료하여 stack pop을하여 이전 위치로 복귀한다.

즉 D(400)의 21번 line으로 복귀한다.

그럼 22번 line에서 root.rt를 하는데 마찬가지로 null이므로 바로 복귀를한다.

D(400)의 함수가 할일을 다 했으니 다시 pop하여 D(200)의 21번 line으로 돌아간다.

이제 D(200)의 21번 line에 왔으니 다음 line인 22번으로 가서 D(500) 으로 연결된다.

 

이런식으로 함수호출은 메모리 내부에서 stack 형식으로 구성되어 있으니 stack을 그려보면서 나머지 stack을 그려보기 바란다.

전위순회를 성공했다면 중위순회, 후위순회도 그려보자

 

중위순회 방식 [left, root, right]

4 2 5 1 6 3 7

public static void DFS(Node root) {
    if (root == null) {
        return;
    }

    DFS(root.lt); // line 20
    System.out.print(root.data + " "); // line 21
    DFS(root.rt); // line 22
}

 

후위순회 방식 [left, right, root]

4 5 2 6 7 3 1

public static void DFS(Node root) {
    if (root == null) {
        return;
    }

    DFS(root.lt); // line 20
    DFS(root.rt); // line 21
    System.out.print(root.data + " "); // line 22
}