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

 

Problem 💻

아래 그림과 같은 이진트리를 전위순회, 중위순회, 후위순회로 출력할 수 있게 연습해 보세요.

 

전위순회 출력 : 1 2 4 5 3 6 7

중위순회 출력 : 4 2 5 1 6 3 7

후위순회 출력 : 4 5 2 6 7 3 1

 

Solution 💡

class Node {

    int data;
    Node lt, rt;

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

public class INF0705 {

    Node root;

    public static void main(String args[]) {
        INF0705 tree = new INF0705();
        tree.root = new Node(1);
        tree.root.lt = new Node(2);
        tree.root.rt = new Node(3);
        tree.root.lt.lt = new Node(4);
        tree.root.lt.rt = new Node(5);
        tree.root.rt.lt = new Node(6);
        tree.root.rt.rt = new Node(7);
        tree.DFS(tree.root);
    }

    public void DFS(Node root) {
        if (root == null) {
            return;
        } else {
//            System.out.print(root.data + " "); // 전위순회 1 2 4 5 3 6 7
            DFS(root.lt);
//            System.out.print(root.data + " "); // 중위순회 4 2 5 1 6 3 7
            DFS(root.rt);
            System.out.print(root.data + " "); // 후위순회 4 5 2 6 7 3 1
        }
    }
}

 

 

풀이

트리 구조를 꼭 그려보고, 전위순회/중위순회/후위순회에 대해 순서가 스택을 그려보면서 꼭 이해해 보자!

적는데 오래 걸렸지만 확실히 이해가 됐다.

 

트리

전위순회

중위순회

후위순회