이진트리 레벨탐색 (7)- BFS: Breath-FirstSearch

ho's·2022년 7월 1일
0

🥗 이진트리 레벨 탐색

🥫 이진트리 레벨탐색

🥫 코드를 작성해보자.

🧃 Node 클래스

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

🧊 Main클래스

public class Main{
	Node root;
    public void BFS(Node root){
    ...
    }
    
    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.BFS(tree.root);
    }
}	

Node형식의 객체를 생성하고,
main메소드에서 Main객체인 tree를 사용해
각각의 노드 data를 저장해준다.

🍲 BFS메소드

public void BFS(Node root){
	Queue<Node> Q = new LinkedList<>();
    Q.offer(root);
    int L = 0;
    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);
            if(cur.rt != null)
            	Q.offer(cur.rt);
        }
        L++;
        System.out.println();
    }	
}

🥫 전체 코드

package Nodes.bfs_breath_first_search;

import java.util.LinkedList;
import java.util.Queue;

class Node{

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


public class Main {
    Node root;
    public void BFS(Node root){
        Queue<Node> Q = new LinkedList<>();
        //Q.add(root);
        Q.offer(root);
        int L = 0;
        // 비어있지 않을때 while문이 동작해야 하므로
        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);
                if(cur.rt != null)
                    Q.offer(cur.rt);
            }
            L++;
            System.out.println();
        }
    }

    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.BFS(tree.root);
    }
}
profile
그래야만 한다

0개의 댓글