Te JAVA (3) - 자료구조 구현 (Binary Tree)

1. Node 클래스 정의
2. BFS(Node node) 구현
3. DFS(Node node) 구현

 

---

 

1. Node 클래스 정의

• 값은 int로 한다.
• 이진 트리를 나타내는 Node 클래스다.
• int value, Node left, Node right를 가진다.

public class Node {

    private int value;
    private Node left;
    private Node right;

    public Node(int value, Node left, Node right){
        this.value = value;
        this.left = left;
        this.right = right;
    }

    public int getValue() {
        return value;
    }

    public Node getLeft() {
        return left;
    }

    public Node getRight() {
        return right;
    }

}

 

---

 

2. BFS(Node node) 구현

• BinaryTree 클래스 내에 구현한다.
• 주어진 노드를 기준으로 출력한다.

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

public class BinaryTree {

    public void BFS(Node node){
        
        Queue<Node> q = new LinkedList<>();
        q.add(node);

        while(!q.isEmpty()){
            Node newNode = q.poll();    // 노드 하나 꺼내기
            Node left = newNode.getLeft();  // 현재 노드의 왼쪽 자식 노드
            Node right = newNode.getRight();    // 현재 노드의 오른쪽 자식 노드

            System.out.print(newNode.getValue() + " - ");

            // 자식 노드가 존재하는 경우에만 q에 add
            if (left != null){
                q.add(left);
            }
            if (right != null){
                q.add(right);
            }
        }

    }

 

---

 

3. DFS(Node node) 구현

• BinaryTree 클래스 내에 구현한다.
• 주어진 노드를 기준으로 출력한다.
• 왼쪽, 루트, 오른쪽 순으로 순회한다. -> 중위 순회

    public void DFS(Node node){

        Node left = node.getLeft();     // 왼쪽 자식 노드
        Node right = node.getRight();   // 오른쪽 자식 노드

        if (left != null){
            DFS(left);
        }

        // 중위 순회
        System.out.print(node.getValue() + " - ");

        if (right != null){
            DFS(right);
        }

    }

}

 

---

 

Test

Tree

class BinaryTreeTest {

    Node node9 = new Node(9, null, null);
    Node node8 = new Node(8, node9, null);
    Node node7 = new Node(7, null, null);
    Node node6 = new Node(6, null, node8);
    Node node5 = new Node(5, null, node7);
    Node node4 = new Node(4, null, null);
    Node node3 = new Node(3, node6, null);
    Node node2 = new Node(2, node4, node5);
    Node node1 = new Node(1, node2, node3);

 

BFS Test

    @Test
    void BFS() {

        BinaryTree binaryTree = new BinaryTree();

        binaryTree.BFS(node1);  // 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 -
        binaryTree.BFS(node2);  // 2 - 4 - 5 - 7 -
        binaryTree.BFS(node3);  // 3 - 6 - 8 - 9 -

    }

 

DFS Test

    @Test
    void DFS() {

        BinaryTree binaryTree = new BinaryTree();

        binaryTree.DFS(node1); // 4 - 2 - 5 - 7 - 1 - 6 - 9 - 8 - 3 -
        binaryTree.DFS(node2); // 4 - 2 - 5 - 7 - 
        binaryTree.DFS(node3); // 6 - 9 - 8 - 3 -

    }
}