[자료 구조] 자바를 이용한 트리의 3가지 순회 방법 구현하기 :: Tree Traversal (InOrder, PostOrder, PreOrder)

트리 자료구조를 학습하는 가장 큰 이유는 지난 시간에서 설명했듯이 탐색을 효율적으로 하기 위함 이라고 했다.

 

이런 트리 탐색하는데에 조금 더 효율적이며 체계적인 방법이 있는데, 그 대표 주자 3가지를 이번 시간에는 알아보고 구현까지 마쳐보겠다.

• InOrder

• PreOrder

• PostOrder

• 레벨 순서 순회 (이번에는 다루지 않을 것이다)

---

순회

    for(String name : names) {
      name.toString();
    }

배열을 인덱스 0 부터 길이만큼 반복하는 것이 Iteration 이라고 불리는 순회를 하는 것이다.

 

순회라고 한다면 영어로는 Circulation. 바로 원소를 하나 하나 확인한다는 뜻이다.

 

우리는 사실 많은 부분에서 순회를 경험해 왔었다.

하지만 앞으로 우리가 배울 순회와 다른 점이 존재한다면, 배열이나 리스트는 1차원적인 한 가지 방법의 순회만 할 수 있다면, 트리는 여러 방법으로 순회하는 체계가 있다.

천천히 배워보자.

 

해당 구조는 앞으로 배울 순회 방법에 사용될 트리이니 참고하고, 트리의 순회를 구현하기 위해서 다음과 같은 코드를 준비한다.

 

 

간단하게 트리를 클래스와 노드 클래스를 이용해서 이진 트리를 만들어두자. 소스코드는 아래에 첨부할 것이니 잘 따라오길 바란다.

 

InOrder

중위 순회라고도 불리는 InOrder은 왼쪽 자식 -> 루트 노드 -> 오른쪽 자식 순서로 방문한다.

1. 왼쪽 자식 노드
2. 현재 노드
3. 오른쪽 자식 노드

위와 같은 트리가 존재할 때 왼쪽 자식이 노드가 없을 때 까지 방문하고 노드가 없다면 출력한다.

그럼 이렇게 내려가게 될 것이다.

 

이와 같은 과정을 우리는 구현하기 위해서 재귀 호출을 통해서 구현한다.

 

노드가 null이 아닐 때 까지 재귀 호출을 수행한다.

 

InOrder가 왼쪽 자식 노드 먼저 출력하고 현재 노드 출력 후 오른쪽 자식을 출력하는 것이니 위와 같은 코드가 나올 수 있다.

PreOrder

전위 순회라고도 불리는 InOrder은 루트 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 순서로 방문한다.

1. 현재 노드
2. 왼쪽 자식 노드
3. 오른쪽 자식 노드

현재 노드를 출력하고 왼쪽 자식 노드 -> 오른쪽 자식 노드 순서로 방문하며 출력하는데 왼쪽 자식 노드의 자식 노드가 존재하지 않을 때 까지 아래로 계속 재귀호출한다.

이것 또한 노드가 null이 아닐 때 까지 반복하고 현재 노드를 먼저 출력 후 왼쪽 오른쪽을 재귀 호출 한다.

PostOrder

후위 순회라고도 불리는 InOrder은 루트 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 순서로 방문한다.

1. 현재 노드
2. 왼쪽 자식 노드
3. 오른쪽 자식 노드

노드가 존재하지 않을 때 까지 현재 노드의 왼쪽 자식 -> 오른쪽 자식 현재 노드 순서로 순회하면 된다.

전체 소스 코드

class TraversalNode{
    int data;
    TraversalNode rightNode;
    TraversalNode leftNode;
}

class TraversalTree{
    TraversalNode root;

    TraversalNode getRoot() {
        return root;
    }

    void setRoot(TraversalNode root) {
        this.root = root;
    }

    /*노드를 만드는 메서드*/
    void makeNode(int data, TraversalNode left, TraversalNode right){
        TraversalNode node = new TraversalNode();
        node.data = data;
        node.leftNode  = left;
        node.rightNode = right;
    }

    void inOrder(TraversalNode node){

        if (node != null){
            inOrder(node.leftNode);
            System.out.println(node.data);
            inOrder(node.rightNode);
        }
    }

    void preOrder(TraversalNode node){
        if(node != null){
            System.out.println(node.data);
            preOrder(node.leftNode);
            preOrder(node.rightNode);
        }
    }

    void postOrder(TraversalNode node){
        if(node != null){
            postOrder(node.leftNode);
            postOrder(node.rightNode);
            System.out.println(node.data);
        }
    }
}

---

이렇게 트리의 순회 방법에 대해서 알아보았는데 순회 방법은 탐색에도 정말 중요하고 다음에 가서 구현할 BFS, DFS에도 중요한 개념이 된다.

 

안 그래도 어려운 BFS, DFS에 트리의 순회 방법까지 어렵게 느껴진다면 정말 지옥이 될 수 있다.

 

그러므로 지금 미리 고통을 받게 된다면 다음이 편해진다는 마음으로 확실히 알아가자.

 

유튜브 www.youtube.com/watch?v=QN1rZYX6QaA 강의가 정말 잘 나와있기 때문에 해당 유튜브를 보고 학습하는 것을 내 블로그를 보는것 보다 훨씬 많이추천한다..