5. 이진트리순회(DFS: Depth - First - Searching)

1. 문제

이진트리

해당 이진트리의 전위, 중위, 후위 순회를 연습하자.

 

 

2. 나의 풀이

트리는 학교에서도 안배워서 강의 봄.

 

 

3 - 1. 강의 풀이

트리를 선언해서 값을 넣어주고 순회한다.

 

직접 써보면서 순회가 어떻게 이루어지는 지 느끼자.

 

부모, 왼쪽, 오른쪽 이게 전위 순회의 기본 순서인데

부모위치 전, 중, 후에 따라서 전위, 중위, 후위 순회가 결정된다.

 

전위: 1 2 4 5 3 6 7

중위: 4 2 5 1 6 3 7

후위: 4 5 2 6 7 3 1

 

System.out.print(root.data + "  "); //전위 순회
DFS(root.lt);
DFS(root.rt);

DFS(root.lt);
System.out.print(root.data + "  "); //중위 순회
DFS(root.rt);

DFS(root.lt);
DFS(root.rt);
System.out.print(root.data + "  "); //후위 순회

 

3 - 2. 강의 코드

package BFS_DFS;
import java.util.*;

class Node{
    int data;
    Node lt, rt;

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

}


public class dfs05_root {
    public static Node root; //root 노드 생성

    public static void DFS(Node root) {
        if(root == null) return;
        else{
            System.out.print(root.data + "  "); //부모노드의 값 출력
            DFS(root.lt);
            DFS(root.rt);         
        }
    }

    //부모 왼쪽 오른쪽 중에서 부모 노드가 전 중 후로 출력됨에 따라서 전위 중위 후위로 결정된다.

    public static void main(String[] args) {
        dfs05_root tree = new dfs05_root();
        root = new Node(1); //root 노드에 data 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);
    }


}

 

 

4. 얻어갈 점

직접 순서를 써가면서 순회가 어떻게 이루어지는 지 느껴보는 것이 중요하다.