Data Structure

[Data Structure] Java ์ด์ง„ํŠธ๋ฆฌ(Binary Tree) ๊ตฌํ˜„

An effort will never betray ๐Ÿ˜Ž 2021. 1. 17. 21:07
๋ฐ˜์‘ํ˜•
  • ์ด ๊ธ€์€ "์˜จ๋ผ์ธ ์ž๋ฐ” ์Šคํ„ฐ๋”” ๋‚ด์šฉ"์„ ์ •๋ฆฌํ•œ ๊ธ€์ž…๋‹ˆ๋‹ค.

์ด์ง„ํŠธ๋ฆฌ(Binary Tree)๋ž€?

  • ํŠธ๋ฆฌ๋ž€ ๋…ธ๋“œ์™€ ๊ฐ„์„ ์œผ๋กœ ์ด๋ฃจ์–ด์ ธ ๋ฐ˜๋ณต์ ์œผ๋กœ ์ •์˜๋˜๋Š” ์ž๋ฃŒ๊ตฌ์กฐ์ž…๋‹ˆ๋‹ค.

  • ์ด์ง„ ํŠธ๋ฆฌ๋Š” ํŠธ๋ฆฌ์˜ ์ข…๋ฅ˜ ์ค‘ ํ•˜๋‚˜๋กœ ๋ชจ๋“  ๋…ธ๋“œ๊ฐ€ ๋‘ ๊ฐœ์˜ ์„œ๋ธŒํŠธ๋ฆฌ๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ํŠธ๋ฆฌ์ž…๋‹ˆ๋‹ค.

  • ์ด์ง„ ํŠธ๋ฆฌ์˜ ์„œ๋ธŒ ํŠธ๋ฆฌ๋Š” ๊ณต๋ฐฑ์ด ๋  ์ˆ˜๋„ ์žˆ๊ณ  ํ•˜๋‚˜์˜ ์„œ๋ธŒํŠธ๋ฆฌ๋งŒ ๊ฐ€์ง€๊ฑฐ๋‚˜ ๋‘ ๊ฐœ ๋ชจ๋‘ ๊ฐ€์งˆ ์ˆ˜๋„ ์žˆ์Šต๋‹ˆ๋‹ค.


์ด์ง„ํŠธ๋ฆฌ ๊ตฌํ˜„

๋…ธ๋“œ ํด๋ž˜์Šค

public class Node {
    int value;
    Node left;
    Node right;

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

๋จผ์ € ์ด์ง„ํŠธ๋ฆฌ๋ฅผ ๊ตฌํ˜„ํ•˜๊ธฐ ์ „์— ์ด์ง„ํŠธ๋ฆฌ์— ํ•„์š”ํ•œ ๋…ธ๋“œ๋ฅผ ํด๋ž˜์Šค๋กœ ํ‘œํ˜„ํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. ์ด ๋•Œ ๋…ธ๋“œ ๋‚ด์— ๋‹ด์„ ๋ฐ์ดํ„ฐ์™€ ์™ผ์ชฝ ์„œ๋ธŒํŠธ๋ฆฌ, ์˜ค๋ฅธ์ชฝ ์„œ๋ธŒํŠธ๋ฆฌ๋ฅผ ๊ฐ€๋ฆฌํ‚ฌ ํฌ์ธํ„ฐ๋ฅผ ๊ฐ€์ ธ์•ผ ํ•ฉ๋‹ˆ๋‹ค.


์ด์ง„ํŠธ๋ฆฌ ํด๋ž˜์Šค

  • void push(Node node) : ๋…ธ๋“œ๋ฅผ ํŠธ๋ฆฌ์— ์ถ”๊ฐ€ํ•˜๋Š” ํ•จ์ˆ˜
  • int pop(Node node) : ๋…ธ๋“œ๋ฅผ ํŠธ๋ฆฌ์—์„œ ์ œ๊ฑฐํ•˜๋Š” ํ•จ์ˆ˜
  • boolean contain(Node node) : ๋…ธ๋“œ๊ฐ€ ํŠธ๋ฆฌ์— ์žˆ๋Š”์ง€ ํ™•์ธํ•˜๋Š” ํ•จ์ˆ˜
  • Node removeLastNode(Node node) : ํŠธ๋ฆฌ์—์„œ ๋งˆ์ง€๋ง‰ ๋…ธ๋“œ๋ฅผ ์ œ๊ฑฐํ•˜๋Š” ํ•จ์ˆ˜
  • boolean isSame(Node a, Node b) : ๋‘ ๊ฐœ์˜ ๋…ธ๋“œ๊ฐ€ ๊ฐ™์€ ๋…ธ๋“œ์ธ์ง€ ํ™•์ธํ•˜๋Š” ํ•จ์ˆ˜

BFS (Breadth-First Search)๋ž€?

  • BFS๋Š” ๊ทธ๋ž˜ํ”„ ์ „์ฒด๋ฅผ ํƒ์ƒ‰ํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ค‘ ํ•˜๋‚˜๋กœ ๋ฃจํŠธ ๋…ธ๋“œ์—์„œ๋ถ€ํ„ฐ ์‹œ์ž‘ํ•˜์—ฌ ๊ฐ€๊นŒ์šด ๋…ธ๋“œ๋ถ€ํ„ฐ ๋จผ์ € ํƒ์ƒ‰ํ•˜๋Š” ๋ฐฉ๋ฒ•์ž…๋‹ˆ๋‹ค.
  • ๋ฃจํŠธ๋…ธ๋“œ๋ถ€ํ„ฐ ๊ฐ€๊นŒ์šด ์ •์ ์„ ๋ฐฉ๋ฌธํ•˜๊ณ  ๋ฉ€๋ฆฌ ๋–จ์–ด์ ธ ์žˆ๋Š” ๋…ธ๋“œ๋Š” ์ƒ๋Œ€์ ์œผ๋กœ ๋‚˜์ค‘์— ๋ฐฉ๋ฌธํ•จ์œผ๋กœ์จ ๋…ธ๋“œ๋ฅผ ๋„“๊ฒŒ ํƒ์ƒ‰ํ•ฉ๋‹ˆ๋‹ค.
  • BFS ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ตฌํ˜„ ์‹œ ํ(Queue) ๋ฅผ ์ด์šฉํ•˜์—ฌ ๊ตฌํ˜„ํ•ฉ๋‹ˆ๋‹ค.
    public void printBFS(Node node) {

        Queue<Node> queue = new LinkedList<Node>();
        queue.add(node);

        while (!queue.isEmpty()) {
            Node temp = queue.poll();
            System.out.println(temp.value);

            if (temp.left != null) {
                queue.add(temp.left);
            }

            if (temp.right != null) {
                queue.add(temp.right);
            }
        }
    }

DFS(Depth-First Search)๋ž€?

  • DFS๋„ ๋งˆ์ฐฌ๊ฐ€์ง€๋กœ ๊ทธ๋ž˜ํ”„ ์ „์ฒด๋ฅผ ํƒ์ƒ‰ํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ ๋ฃจํŠธ๋…ธ๋“œ์—์„œ ํ•˜๋‚˜์˜ ๋…ธ๋“œ๋ฅผ ๋ฐฉ๋ฌธํ•˜๊ฒŒ ๋˜๋ฉด ๋‹ค์Œ ์ธ์ ‘ํ•œ ๋…ธ๋“œ๋กœ ๊ฐ€๊ธฐ ์ „์— ๋ฐฉ๋ฌธํ•œ ๋…ธ๋“œ๋ฅผ ๋๊นŒ์ง€ ํƒ์ƒ‰ํ•˜๋Š” ๋ฐฉ๋ฒ•์ž…๋‹ˆ๋‹ค.
  • ํ•˜๋‚˜์˜ ๋…ธ๋“œ๋ฅผ ๋๊นŒ์ง€ ๋ฐฉ๋ฌธํ•˜๊ธฐ ๋•Œ๋ฌธ์— ๋…ธ๋“œ๋ฅผ ๊นŠ๊ฒŒ ํƒ์ƒ‰ํ•œ๋‹ค๊ณ  ๋ณผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
  • DFS ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ตฌํ˜„ ์‹œ ์žฌ๊ท€ํ•จ์ˆ˜ ๋˜๋Š” ์Šคํƒ์„ ์ด์šฉํ•˜์—ฌ ๊ตฌํ˜„ํ•ฉ๋‹ˆ๋‹ค.
    public void printDFS(Node node) {

        if(node.left == null && node.right == null){
            System.out.println(node.value);
        }else{
            if(node.left != null){
                printDFS(node.left);
            }
            System.out.println(node.value);
            if(node.right != null){
                printDFS(node.right);
            }
        }
    }

๊ฒฐ๊ณผ

public class Main {
    public static void main(String[] args) {
        BinaryTree bt = new BinaryTree();

        Node node = new Node(3);
        Node node1 = new Node(5);
        Node node2 = new Node(7);
        Node node3 = new Node(4);
        Node node4 = new Node(2);

        bt.push(node);
        bt.push(node1);
        bt.push(node2);
        bt.push(node3);
        bt.push(node4);

        System.out.println("BFS๋กœ ํƒ์ƒ‰ํ•ฉ๋‹ˆ๋‹ค");
        bt.printBFS(node);

        System.out.println("\nDFS๋กœ ํƒ์ƒ‰ํ•ฉ๋‹ˆ๋‹ค");
        bt.printDFS(node);
    }
}


๋ฐ˜์‘ํ˜•