Java Study 3-2주차

• int 값을 가지고 있는 이진 트리를 나타내는 Node 라는 클래스를 정의하시오.

class Nod {  
    int data;  
    Nod left;  
    Nod right;  
  
    public Nod(int data) {  
        this.data = data;  
        this.left = null;  
        this.right = null;  
    }  
  
    public Nod() {  
        this(0);  
    }  
}

• BinrayTree라는 클래스를 정의하고 주어진 노드를 기준으로 출력하는 bfs(Node node)와 dfs(Node node) 메소드를 구현하세요.

class BinaryTree {  
    Nod nod;  
    int size;  
  
    public BinaryTree() {  
        nod = new Nod();  
        size = 0;  
    }  
  
    public void addFirstNode(int data) {  
        size++;  
        nod.data = data;  
    }  
  
    public void addNode(int data) {  
        if (size == 0) {  
            addFirstNode(data);  
            return;        
            }  
        Nod result = findNode(nod, nod);  
        if(result.left == null){  
            result.left = new Nod(data);  
            return;        
            }  
        result.right = new Nod(data);  
  
    }  
    public Nod findNode(Nod left, Nod right){  
        if(left.left == null || left.right == null){  
            return left;  
        } else if (right.left == null || right.right == null) {  
            return right;  
        }  
        Nod result = findNode(left.left,left.right);  
        return result;  
    }  
  
    public void bfs(Nod node){  
        Queue<Nod> q = new LinkedList<>();  
        q.add(node);  
        while(!q.isEmpty()){  
            Nod cur = q.poll();  
            System.out.println(cur.data);  
            if(cur.left != null){  
                q.add(cur.left);  
            }  
            if(cur.right != null){  
                q.add(cur.right);  
            }  
        }  
    }  
  
    public void dfs(Nod node){  
        if(node == null) return;  
        if(node.left == null){  
            System.out.println(node.data);  
            return;        
            }  
        dfs(node.left);  
        System.out.println(node.data);  
        dfs(node.right);  
    }  
  
}

실행 화면

public class MakeBinaryTree {  
    public static void main(String[] args) {  
        BinaryTree binaryTree = new BinaryTree();  
        binaryTree.addNode(1);  
        binaryTree.addNode(2);  
        binaryTree.addNode(3);  
        binaryTree.addNode(4);  
        binaryTree.addNode(5);  
        binaryTree.addNode(6);  
        binaryTree.bfs(binaryTree.nod);  //1,2,3,4,5,6 순서로 순회
        binaryTree.dfs(binaryTree.nod);  //4,2,5,1,6,3 순서로 순회
    }  
}