이진트리 순회 (DFS : Depth-First Search)

설명

아래 그림과 같은 이진트리를 전위순회와 후위순회를 연습해보세요.

 

전위순회 출력 : 1 2 4 5 3 6 7 (부모 -> 왼쪽 -> 오른쪽)

중위순회 출력 : 4 2 5 1 6 3 7 (왼쪽 -> 부모 -> 오른쪽)

후위순회 출력 : 4 5 2 6 7 3 1 (왼쪽 -> 오른쪽 -> 부모)

 

후위순회를 잘 알아놔야 함 => 병합정렬?

 

중위순회는 스택 그려가면서 하기 꼭 => 강의 다시 듣고 그려보기 직접

 

문제 해결

 

class Node {
    int data;
    Node lt,rt;
    public Node(int val) {
        data = val;
        lt = rt = null;
    }
}

• Node: 각 노드를 나타내는 클래스
• int data : 노드의 값을 저장
• Node lt : 노드의 왼쪽 자식
• Node rt : 노드의 오른쪽 자식

 

 

static Node root;
public static void main(String[] args) {
    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);
}

 

• root = new Node(1); : 루트 노드 생성
  • 1은 해당 노드의 데이터(data)로 저장되고, 이 객체가 생성되는 순간, 노드의 왼쪽(lt)과 오른쪽(rt) 자식 노드는 null로 초기화된다.
• root.lt = new Node(2);와 root.rt = new Node(3); ....
  • 여기서 root.lt와 root.rt는 각각 루트 노드의 왼쪽과 오른쪽 자식 노드를 가리키고 자식 노드는 그 아래로 자신의 자식 노드를 생성하고 연결해가며 트리 구조를 구성함. ( 그 주소를 자식에 넣어감. 말단 노드의 lt,rt는 당연히 null )
• DFS(root);
  • 루트 노드부터 시작하여 트리를 깊이 우선 방식으로 순회한다. ( root는 객체의 주소를 담은 것)

 

 public static void DFS(Node root) {
        if(root == null) return; //말단으로 들어온 것
        else { //두 가닥으로 뻗어야 함 (즉 함수 호출이 두 번 일어남)

            //System.out.print(root.data + " "); // 전위 순회
            DFS(root.lt); //lt로 값 전달
            //System.out.print(root.data + " "); // 중위 순회
            DFS(root.rt); //rt로 값 전달
            System.out.print(root.data + " "); // 후위 순회
        }
    }

 

 

<전위 순회>

•   노드에 도착하자마자 노드의 데이터를 출력
  • System.out.print(root.data + " ");
  • DFS(root.lt);
  • DFS(root.rt);

 

<중위 순회>

• 왼쪽 자식을 먼저 완전히 순회한 후, 노드를 출력. 이러한 방식으로, 노드의 왼쪽에 있는 모든 값들이 먼저 출력되고, 노드가 출력되며, 마지막으로 오른쪽을 처리.
  •  DFS(root.lt);
  • System.out.print(root.data + " ");
  • DFS(root.rt);

 

<후위 순회>

• 노드의 모든 자식을 먼저 출력 ( lt -> rt ) 하고 마지막에 노드 자신을 출력.
  • DFS(root.lt);
  • DFS(root.rt);
  • System.out.print(root.data + " ");

 

최종 코드

 

class Node {
    int data;
    Node lt,rt;
    public Node(int val) {
        data = val;
        lt = rt = null;
    }
}
public class P05_이진트리순회_DFS {
    static Node root;
    public static void main(String[] args) {
        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);
    }

    public static void DFS(Node root) {
        if(root == null) return; //말단으로 들어온 것
        else { //두 가닥으로 뻗어야 함 (즉 함수 호출이 두 번 일어남)

            //System.out.print(root.data + " "); // 전위 순회
            DFS(root.lt); //lt로 값 전달
            //System.out.print(root.data + " "); // 중위 순회
            DFS(root.rt); //rt로 값 전달
            System.out.print(root.data + " "); // 후위 순회
        }
    }

}