트리

May 13, 2024

트리 (Tree)

노드와 링크로 구성된 자료구조 (그래프의 일종, Cycle 없음)
계층적 구조를 나타낼 때 사용
폴더 구조 (디렉토리, 서브 디렉토리)
조직도, 가계도, …

트리의 구조

노드(Node): 트리 구조의 자료 값을 담고 있는 단위
에지(Edge): 노드 간의 연결선 (=link, branch)
루트 노드(Root): 부모가 없는 노드, 가장 위의 노드
잎새 노드(Leaf): 자식이 없는 노드 (=단말)
내부 노드(Internal): 잎새 노드를 제외한 모든 노드
부모(Parent): 연결된 두 노드 중 상위의 노드
자식(Child): 연결된 두 노드 중 하위의 노드
형제(Sibling): 같은 부모를 가지는 노드
깊이(Depth): 루트에서 어떤 노드까지의 간선의 수
레벨(Level): 트리의 특정 깊이를 가지는 노드 집합
높이(Height): 트리에서 가장 큰 레벨 값
크기(Size): 자신을 포함한 자식 노드의 개수
차수(Degree): 각 노드가 지닌 가지의 수
트리의 차수: 트리의 최대 차수

new repo

트리의 특징

하나의 노드에서 다른 노드로 이동하는 경로는 유일
노드가 N개인 트리의 Edge의 수는 N-1개
Acyclic (Cycle이 존재하지 않음)
모든 노드는 서로 연결되어 있음
하나의 Edge를 끊으면 2개의 Sub-Tree로 분리됨

이진 트리 (Binary Tree)

각 노드는 최대 2개의 자식을 가질 수 있음
자식 노드는 좌우를 구분함
왼쪽 자식: 부모 노드의 왼쪽 아래
오른쪽 자식: 부모 노드의 오른쪽 아래

new repo

이진 트리 종류 (1)

포화 이진 트리 (Perfect binary tree)
모든 레벨에서 노드들이 꽉 채워져 있는 트리
완전 이진 트리 (Complete Binary tree)
마지막 레벨을 제외하고 노드들이 모두 채워져 있는 트리

new repo

이진 트리 종류 (2)

정 이진 트리 (Full binary tree)
모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리
편향 트리 (Skewed Binary Tree) = 사향 트리
한쪽으로 기울어진 트리

new repo

이진 트리 종류 (3)

균형 이진 트리 (Balanced binary tree)
모든 노드의 좌우 서브 트리 높이가 1이상 차이 나지 않는 트리

new repo

이진 트리 특징

포화 이진 트리의 높이가 h일 때, 노드의 수는 2^(ℎ+1)−1개
포화(or 완전) 이진 트리의 노드가 N개 일 때, 높이는 logN
이진 트리의 노드가 N개 일 때, 최대 가능 높이는 N-1

이진 트리의 순회 (Traversal)

모든 노드를 빠뜨리거나 중복하지 않고 방문하는 연산
순회 종류는 4가지
전위 순회, 중위 순회, 후위 순회
레벨 순회

이진 트리의 순회 – 전위 순회

Preorder Traversal
방문 순서: 현재 노드 → 왼쪽 노드 → 오른쪽 노드

new repo

이진 트리의 순회 – 중위 순회

Inorder Traversal
방문 순서: 왼쪽 노드 → 현재 노드 → 오른쪽 노드

new repo

이진 트리의 순회 – 후위 순회

Postorder Traversal
방문 순서: 왼쪽 노드 → 오른쪽 노드 → 현재 노드

new repo

이진 트리의 순회 – 레벨 순회

Levelorder Traversal
방문 순서: 위쪽 레벨 부터 왼쪽 노드 → 오른쪽 노드

new repo

이진 트리 구현

배열
레벨 순회 순으로 배열에 구성

new repo

연결 리스트
값과 간선을 관리하기 위한 노드로 연결리스트 구성

배열을 이용한 이진 트리 구성, 순회

// Practice1
// 배열을 이용한 이진 트리 구성, 순회

class BinaryTree {
    char[] arr;

    BinaryTree(char[] data) {
        this.arr = data.clone();
    }

    public void preOrder(int idx) {
        System.out.print(this.arr[idx] + " ");

        int left = 2 * idx + 1;
        int right = 2 * idx + 2;
        if (left < this.arr.length) {
            this.preOrder(left);
        }
        if (right < this.arr.length) {
            this.preOrder(right);
        }
    }

    public void inOrder(int idx) {
        int left = 2 * idx + 1;
        int right = 2 * idx + 2;

        if (left < this.arr.length) {
            this.inOrder(left);
        }

        System.out.print(this.arr[idx] + " ");

        if (right < this.arr.length) {
            this.inOrder(right);
        }
    }

    public void postOrder(int idx) {
        int left = 2 * idx + 1;
        int right = 2 * idx + 2;

        if (left < this.arr.length) {
            this.postOrder(left);
        }

        if (right < this.arr.length) {
            this.postOrder(right);
        }

        System.out.print(this.arr[idx] + " ");
    }

    public void levelOrder(int idx) {
        for (int i = idx; i < this.arr.length; i++) {
            System.out.print(this.arr[i] + " ");
        }
        System.out.println();
    }
}

public class Practice1 {
    public static void main(String[] args) {
        // Test code
        char[] arr = new char[10];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (char)('A' + i);
        }

        BinaryTree bt = new BinaryTree(arr);

        System.out.println("== Preorder ==");
        bt.preOrder(0);
        System.out.println();

        System.out.println("== Inorder ==");
        bt.inOrder(0);
        System.out.println();

        System.out.println("== Postorder ==");
        bt.postOrder(0);
        System.out.println();

        System.out.println("== Levelorder ==");
        bt.levelOrder(0);
        System.out.println();
    }
}

== Preorder ==
A B D H I E J C F G 
== Inorder ==
H D I B J E A F C G 
== Postorder ==
H I D J E B F G C A 
== Levelorder ==
A B C D E F G H I J 

연결 리스트를 이용한 이진 트리 구성, 순회

// Practice2
// 연결 리스트를 이용한 이진 트리 구성, 순회

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

class Node {
    char data;
    Node left;
    Node right;

    Node(char data, Node left, Node right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
}

class BinaryTree2 {
    Node head;

    BinaryTree2() {}
    BinaryTree2(char[] arr) {
        Node[] nodes = new Node[arr.length];
        for (int i = 0; i < arr.length; i++) {
            nodes[i] = new Node(arr[i], null, null);
        }

        for (int i = 0; i < arr.length; i++) {
            int left = 2 * i + 1;
            int right = 2 * i + 2;

            if (left < arr.length) {
                nodes[i].left = nodes[left];
            }

            if (right < arr.length) {
                nodes[i].right = nodes[right];
            }

        }
        this.head = nodes[0];
    }

    public void preOrder(Node node) {
        if (node == null) {
            return;
        }

        System.out.print(node.data + " ");
        preOrder(node.left);
        preOrder(node.right);
    }

    public void inOrder(Node node) {
        if (node == null) {
            return;
        }

        inOrder(node.left);
        System.out.print(node.data + " ");
        inOrder(node.right);
    }

    public void postOrder(Node node) {
        if (node == null) {
            return;
        }

        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.data + " ");
    }

    public void levelOrder(Node node) {
        Queue<Node> queue = new LinkedList();
        queue.add(node);
        while (!queue.isEmpty()) {
            Node cur = queue.poll();

            System.out.print(cur.data + " ");
            if (cur.left != null) {
                queue.offer(cur.left);
            }

            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }
}


public class Practice2 {
    public static void main(String[] args) {
        // Test code
        char[] arr = new char[10];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (char)('A' + i);
        }

        BinaryTree2 bt = new BinaryTree2(arr);

        System.out.println("== Preorder ==");
        bt.preOrder(bt.head);
        System.out.println();

        System.out.println("== Inorder ==");
        bt.inOrder(bt.head);
        System.out.println();

        System.out.println("== Postorder ==");
        bt.postOrder(bt.head);
        System.out.println();

        System.out.println("== Levelorder ==");
        bt.levelOrder(bt.head);
        System.out.println();
    }
}

== Preorder ==
A B D H I E J C F G 
== Inorder ==
H D I B J E A F C G 
== Postorder ==
H I D J E B F G C A 
== Levelorder ==
A B C D E F G H I J

트리 구조 복습 / 구현

// Practice3
// 트리 구조 복습 / 구현

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

class Node2 {
    char data;
    Node2 left;
    Node2 right;
    Node2 parent;

    public Node2(char data, Node2 left, Node2 right, Node2 parent) {
        this.data = data;
        this.left = left;
        this.right = right;
        this.parent = parent;
    }
}

class BinaryTree3 {
    Node2 head;

    BinaryTree3(char[] arr) {
        Node2[] nodes = new Node2[arr.length];
        for (int i = 0; i < arr.length; i++) {
            nodes[i] = new Node2(arr[i], null, null, null);
        }

        for (int i = 0; i < arr.length; i++) {
            int left = 2 * i + 1;
            int right = 2 * i + 2;

            if (left < arr.length) {
                nodes[i].left = nodes[left];
                nodes[left].parent = nodes[i];
            }

            if (right < arr.length) {
                nodes[i].right = nodes[right];
                nodes[right].parent = nodes[i];
            }

        }
        this.head = nodes[0];
    }

    public Node2 searchNode(char data) {
        Queue<Node2> queue = new LinkedList();
        queue.add(this.head);
        while (!queue.isEmpty()) {
            Node2 cur = queue.poll();
            if (cur.data == data) {
                return cur;
            }

            if (cur.left != null) {
                queue.offer(cur.left);
            }

            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
        return null;
    }

    public Integer checkSize(char data) {
        Node2 node = this.searchNode(data);

        Queue<Node2> queue = new LinkedList();
        queue.add(node);
        int size = 0;
        while (!queue.isEmpty()) {
            Node2 cur = queue.poll();

            if (cur.left != null) {
                queue.offer(cur.left);
                size++;
            }

            if (cur.right != null) {
                queue.offer(cur.right);
                size++;
            }
        }
        return size + 1;
    }
}

public class Practice3 {

    public static void main(String[] args) {
        char[] arr = new char[10];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (char)('A' + i);
        }

        BinaryTree3 bt = new BinaryTree3(arr);

        // Root node
        System.out.println("Root: " + bt.head.data);


        // B's child node
        Node2 B = bt.searchNode('B');
        if (B.left != null) {
            System.out.println("B -> left child: " + B.left.data);
        }
        if (B.right != null) {
            System.out.println("B -> right child: " + B.right.data);
        }


        // F's parent node
        Node2 F = bt.searchNode('F');
        System.out.println("F -> parent: " + F.parent.data);


        // Leaf node
        System.out.print("Leaf node: ");
        for (int i = 0; i < arr.length; i++) {
            Node2 cur = bt.searchNode((char)('A' + i));

            if (cur.left == null && cur.right == null) {
                System.out.print(cur.data + " ");
            }
        }
        System.out.println();


        // E's Depth
        Node2 E = bt.searchNode('E');
        Node2 cur = E;
        int cnt = 0;
        while (cur.parent != null) {
            cur = cur.parent;
            cnt++;
        }
        System.out.println("E depth: " + cnt);


        // Level2 Node
        System.out.print("Level2 Node: ");
        for (int i = 0; i < arr.length; i++) {
            Node2 target = bt.searchNode((char)('A' + i));
            cur = target;
            cnt = 0;
            while (cur.parent != null) {
                cur = cur.parent;
                cnt++;
            }

            if (cnt == 2) {
                System.out.print(target.data + " ");
            }
        }
        System.out.println();


        // Height
        int maxCnt = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            Node2 target = bt.searchNode((char)('A' + i));
            cur = target;
            cnt = 0;
            while (cur.parent != null) {
                cur = cur.parent;
                cnt++;
            }

            if (maxCnt < cnt) {
                maxCnt = cnt;
            }
        }
        System.out.println("Height: " + maxCnt);


        // B's Size
        int size = bt.checkSize('B');
        System.out.println("B size = " + size);

    }
}

Root: A
B -> left child: D
B -> right child: E
F -> parent: C
Leaf node: F G H I J 
E depth: 2
Level2 Node: D E F G 
Height: 3
B size = 6

문제 풀이

종이 접기

// Practice1
// 종이 접기
// 종이를 반으로 접었을 때, 안으로 파인 부분은 0, 볼록 튀어나온 부분은 1이라고 하자.
// 종이를 접을 때는 오른쪽에서 왼쪽으로 접는다.
// 종이를 N번 접었을 때의 접힌 상태를 출력하는 문제를 작성하세요.

// 입출력 예시
// 입력: 1
// 출력: 0

// 입력: 2
// 출력: 0, 0, 1

// 입력: 3
// 출력: 0, 0, 1, 0, 0, 1, 1


public class Practice1 {
    public static void solution(int n) {
        int[] binaryTree = new int[(int)Math.pow(2, n)];

        binaryTree[0] = 0;
        for (int i = 0; i < (int) Math.pow(2, n - 1) - 1; i++) {
            binaryTree[i * 2 + 1] = 0;
            binaryTree[i * 2 + 2] = 1;
        }

        inOrder(binaryTree, 0);
        System.out.println();
    }

    public static void inOrder(int[] arr, int idx) {
        int left = 2 * idx + 1;
        int right = 2 * idx + 2;

        if (left < arr.length - 1) {
            inOrder(arr, left);
        }

        System.out.print(arr[idx] + " ");

        if (right < arr.length - 1) {
            inOrder(arr, right);
        }
    }

    public static void main(String[] args) {
        // Test code
        solution(1);
        solution(2);
        solution(3);
    }
}


0 1 
0 1 0 0 1 1

모든 가중치들의 총합이 최소가 되도록 하는 프로그램

// Practice2
// 각각의 에지에 가중치가 있는 포화 이진 트리가 있다.
// 루트에서 각 리프까지의 경로 길이를 모두 같게 설정하고,
// 이 때, 모든 가중치들의 총합이 최소가 되도록 하는 프로그램을 작성하세요.

class BinaryTree {
    int h;
    int[] arr;
    int res;

    public BinaryTree(int h, int[] w) {
        this.h = h;
        // 이렇게 만들고 0번 위치 인덱스는 사용 X
        arr = new int[(int)Math.pow(2, h + 1)];
        res = 0;

        // 포화 이진 트리의 간선의 수는 노드 수 - 1로 2부터 저장
        for (int i = 2; i < (int)Math.pow(2, h + 1); i++) {
            arr[i] = w[i - 2];
        }
    }

    // 하단 부터 형제 노드의 간선을 맞춰 나가면서 진행
    public int dfs(int idx, int h) {
        if(this.h == h) {
            res += arr[idx];
            return arr[idx];
        }

        int left =  dfs(idx * 2, h + 1);
        int right = dfs(idx * 2 + 1, h + 1);
        res += arr[idx] + Math.abs(left - right);
        return arr[idx] + Math.max(left, right);
    }
}

public class Practice2 {
    public static void solution(int h, int[] w) {
        BinaryTree bt = new BinaryTree(h, w);
        bt.dfs(1, 0);
        System.out.println(bt.res);
    }

    public static void main(String[] args) {
        // Test code
        int h = 2;
        int[] w = {2, 2, 2, 1, 1, 3};
        solution(h, w);
        System.out.println();

        h = 3;
        w = new int[]{1, 2, 1, 3, 2, 4, 1, 1, 1, 1, 1, 1, 1, 1};
        solution(h, w);
    }
}

15

27

출처 : 제로베이스

트리

트리 (Tree)

트리의 구조

트리의 특징

이진 트리 (Binary Tree)

이진 트리 종류 (1)

이진 트리 종류 (2)

이진 트리 종류 (3)

이진 트리 특징

이진 트리의 순회 (Traversal)

이진 트리의 순회 – 전위 순회

이진 트리의 순회 – 중위 순회

이진 트리의 순회 – 후위 순회

이진 트리의 순회 – 레벨 순회

이진 트리 구현

배열을 이용한 이진 트리 구성, 순회

연결 리스트를 이용한 이진 트리 구성, 순회

트리 구조 복습 / 구현

문제 풀이

종이 접기

모든 가중치들의 총합이 최소가 되도록 하는 프로그램

Leave a comment

You may also enjoy

김태원 8월 특강 정렬

김태원 8월 특강 그리디

스프링 핵심가이드 8주차

스프링 핵심가이드 7주차