Live Study 5주차 : 과제

Optional 과제

• int 값을 가지고 있는 이진트리를 나타내는 Node 클래스 정의
  • int value, Node left, Node right를 포함
• BinaryTree 클래스를 정의하고 주어진 노드를 기준으로 출력하는 bfs(Node node) dfs(Node node) 메소드 구현
  • dfs는 왼쪽, 루트, 오른쪽 순으로 순회

 

직접 그린 이진 트리

 

 

• Node 클래스는 조건대로 구현했으며,
• insert에 대한 언급은 없어서 insertNode()라는 메소드를 만들어 왼쪽 자식과 오른쪽 자식을 가리키게 하여 트리를 구성했다.
• BFS는 큐와 연결리스트를 이용하여 왼쪽 자식과 오른쪽 자식을 큐에 넣어 구성했다. 이게 선생님이 의도한 코드인지는 잘 모르겠다.
• DFS는 전위 순회라고 생각했고 보다시피 매우 간단히 구현하여 마무리.
• 맨 아래에 이진 트리의 순회 결과를 첨부했다.

 

package algorithmTest;

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

public class BinaryTree {
    public static void main(String []args){
    	BinaryTree bt = new BinaryTree();
    	
        Node n1 = bt.insertNode(null, null, 1);
        Node n2 = bt.insertNode(null, null, 2);
        Node n3 = bt.insertNode(null, null, 3);
        Node n4 = bt.insertNode(null, null, 4);
        Node n5 = bt.insertNode(null, null, 12);
        Node n6 = bt.insertNode(n1, n2, 5); 
        Node n7 = bt.insertNode(n3, n4, 6);
        Node n8 = bt.insertNode(n5, null, 10);
        Node n9 = bt.insertNode(null, null, 11);
        Node n10 = bt.insertNode(n6, n7, 7);
        Node n11 = bt.insertNode(n8, n9, 9);
        Node n12 = bt.insertNode(n10, n11, 8); // root node
		 	
        System.out.print("BFS 순회 결과 : ");
        bfs(n12);
        System.out.print("\nDFS 순회 결과 : ");
        dfs(n12);  
    }
    
    
    // 1,2) int 값을 가진 이진 트리를 나타내는 Node 클래스
    public class Node{
    	int value;
    	private Node left;
    	private Node right;
    	
    	public Node(int value) {
            this.value = value;
            this.left = null;
            this.right = null;
    	}
    }
    
    public Node insertNode(Node l, Node r, int val) {
    	Node node = new Node(val);
    	node.left = l;
    	node.right = r;
    	return node;
    }
    
    
    // 3-1) 주어진 노드(root)를 기준으로 bfs
    
    static boolean[] check = new boolean[13];
    
    static void bfs(Node node) {
    	Queue <Node> q = new LinkedList<>();
    	q.add(node);
    	
    	while(!q.isEmpty()) {
            Node x = q.poll();
    		
            System.out.print(x.value + " ");
    		
            if(!check[x.value]) {
                check[x.value] = true;
    			
                if(x.left != null) {
                    q.add(x.left);
                }
                if(x.right != null) {
                    q.add(x.right);
                }
            }
    	}
    }
    
   
    // 3-2) 주어진 노드(root)를 기준으로 dfs
    static void dfs(Node node) {	
    	if(node==null) return;
    	
    	dfs(node.left);
    	System.out.print(node.value + " ");
    	dfs(node.right);
    }     
}

 

출력 결과