section7.7

이진트리 순회(넓이우선탐색 : 레벨탐색)
아래 그림과 같은 이진트리를 레벨탐색 연습하세요

                 1
         2               3
    4        5     6          7

레벨 탐색 순회 출력 : 1 2 3 4 5 6 7

 

 

 

ANSWER

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

public class Question7 {
    Node root;

    public static void main(String[] args) {
        /*
        이진트리 순회(넓이우선탐색 : 레벨탐색)
        아래 그림과 같은 이진트리를 레벨탐색 연습하세요

                         1
                 2               3
            4        5     6          7

        레벨 탐색 순회 출력 : 1 2 3 4 5 6 7
        */
        Question7 tree = new Question7();
        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.rt.rt = new Node(5);
        tree.root.lt.lt.rt = new Node(6);
        tree.root.rt.rt.lt = new Node(7);
        tree.DFS(tree.root);
    }

    public void DFS(Node tree) {
        // 무조건 중간 > 왼쪽 > 오른쪽 탐색
        //

    }
}

 

 

 

SOLUTION

public class Answer7 {
    Node root;
    public void BFS(Node root) {
        Queue<Node> Q = new LinkedList<>();
        Q.offer(root);

        while (!Q.isEmpty()) {
            int len = Q.size();
            for (int i = 0; i < len; i++) {
                Node cur = Q.poll();
                System.out.print(cur.data + " ");
                if (cur.lt != null) {
                    Q.offer(cur.lt);
                }

                if (cur.rt != null) {
                    Q.offer(cur.rt);
                }
            }

        }
    }

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

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

• section7.8 먼저 해설 보고 왔는데도 못 풀었다 > 익숙해질 때까지 복습하기