[JAVA] 이진트리 순회(DFS, BFS)

이진트리

출처)https://velog.io/@xdfc1745/

 

이진트리 순회(DFS)

• 전위순회: 중 - 왼 - 오
• 중위순회: 왼 - 중 - 오
• 후위순회: 왼 - 오 - 중

import java.util.*;

class Node {
    int data;
    Node lt, rt;  // 왼쪽 주소, 오른쪽 주소 저장

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

class Main {
    Node root;

    public void DFS(Node root) {
        if (root == null) return;
        else {
            // System.out.print(root.data + " "); 전위순회
            DFS(root.lt); 
            // System.out.print(root.data + " "); 중위순회
            DFS(root.rt);
            // System.out.print(root.data + " "); 후위순회

        }
    }

    public static void main(String[] args) {
        Main tree = new Main();
        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);
    }
}

• 전위순회 : 1 - 2 - 4 - 5 - 3 - 6 - 7
• 중위순회 : 4 - 2 - 5 - 1 - 6 - 3 - 7
• 후위순회 : 4 - 5 - 2 - 6 - 7 - 3 - 1

 

 

 

 

 

💡 시간복잡도는 O(logn) 이다

---

이진트리 순회(BFS, 레벨탐색)

    public void BFS(Node root) {
        Queue<Node> Q = new LinkedList<>();
        Q.offer(root);
        int L = 0; // level
        while (!Q.isEmpty()) {
            int len = Q.size(); // 레벨 당 원소개수
            System.out.print(L + " : ");
            for (int i = 0; i < len; i++) {
                Node cur = Q.poll();
                System.out.print(cur.data + " ");
                if (cur.lt != null) Q.offer(cur.lt); // 왼쪽 자식이 있으면 offer
                if (cur.rt != null) Q.offer(cur.rt); // 오른쪽 자식이 있으면 offer
            }
            L++; // level 1 증가
            System.out.println();
        }
    }

• 레벨탐색: 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8