[자료구조] 트리

\

트리(Tree)란?

---

• 노드와 링크로 구성된 자료구조(그래프의 일종)
• 계층적 구조를 나타낼 때 사용한다.
  
  
  
  

트리의 구조

• 노드(Node): 트리 구조의 자료 값을 담고 있는 단위

• 에지(Edge): 노드 간의 연결선 (=link, branch)

• 루트 노드(Root): 부모가 없는 노드, 가장 위의 노드

• 잎새 노드(Leaf): 자식이 없는 노드 (=단말)

• 내부 노드(Internal): 잎새 노드를 제외한 모든 노드

• 부모(Parent): 연결된 두 노드 중 상위의 노드

• 자식(Child): 연결된 두 노드 중 하위의 노드

• 형제(Sibling): 같은 부모를 가지는 노드

• 깊이(Depth): 루트에서 어떤 노드까지의 간선의 수

• 레벨(Level): 트리의 특정 깊이를 가지는 노드 집합

• 높이(Height): 트리에서 가장 큰 레벨 값

• 크기(Size): 자신을 포함한 자식 노드의 개수

• 차수(Degree): 각 노드가 지닌 가지의 수

• 트리의 차수: 트리의 최대 차수

트리의 특징

---

• 하나의 노드에서 다른 노드로 이동하는 경로는 유일하다.
• 노드가 N개인 트리의 간선(Edge)의 수는 N-1개다.
• Cycle이 존재하지 않는다.
• 모든 노드는 서로 연결되어 있다.
• 이진 트리, 이진 탐색 트리, 균형 트리(AVL 트리, Red-Black트리), 이진 힙(최대 힙, 최소힙) 등이 있다.

이진 트리(Binary Tree)

• 각 노드가 최대 두 개의 자식을 갖는 트리

• 자식 노드는 좌우를 구분한다.

• 왼쪽 자식: 부모 노드의 왼쪽 아래

• 오른쪽 자식: 부모 노드의 오른쪽 아래

이진 트리 종류

---

포화 이진 트리 (Perfect Binary Tree)

• 모든 레벨에서 노드 들이 꽉 채워져 있는 트리

완전 이진 트리 (Complete Binary Tree)

• 마지막 레벨을 제외하고 노드들이 모두 채워져 있는 트리

포화 이진 트리 VS 완전 이진 트리

정 이진 트리 (Full Binary Tree)

• 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리

편향 트리 (Skewed Binary Tree) = 사향 트리

• 한쪽으로 기울어진 트리

정 이진 트리 VS 편향 트리

균형 이진 트리 (Balanced Binary Tree)

• 모든 노드의 좌우 서브 트리 높이가 1이상 차이 나지 않는 트리

이진 트리의 순회

---

너비 우선 검색 (BFS: Breadth-First Search)
낮은 레벨부터 왼쪽에서 오른쪽으로 검색하고, 한 레벨에서 검색을 마치면 다음 레벨로 내려가는 방법

깊이 우선 검색 (DFS: Depth-First Search)
리프에 도달할 때까지 아래쪽으로 내려가면서 검색하는 것을 우선으로 하는 방법, 리프에 도달해서 더 이상 검색할 곳이 없으면 일단 부모 노드로 돌아가고 그 뒤 다시 자식 노드로 내려간다.

전위순회 : 노드 방문 -> 왼쪽 자식 -> 오른쪽 자식
중위순회 : 왼쪽 자식 -> 노드 방문 -> 오른쪽 자식
후위순회 : 왼쪽 자식 -> 오른쪽 자식 -> 노드 방문

이진 트리 구현

---

노드와 이진트리

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

// 노드 구성: 데이터, 왼쪽노드, 오른쪽노드, 부모노드
class Node {
    char data;
    Node left;
    Node right;
    Node parent;

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

// 이진 트리
class BinaryTree {
    Node head;

    // 이진 트리 세팅
    BinaryTree(char[] arr) {
        // null로 세팅
        Node[] nodes = new Node[arr.length];
        for (int i = 0; i < arr.length; i++) {
            nodes[i] = new Node(arr[i], null, null, null);
        }

        for (int i = 0; i < arr.length; i++) {
            int left = 2 * i + 1;       // root노드 인덱스는 0이고, 왼쪽노드 인덱스는 1이된다.
            int right = 2 * i + 2;      // 마찬가지로 오른쪽노드 인덱스는 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];
            }
        }

        // root 노드
        this.head = nodes[0];
    }


    // 노드 검색 메서드
    public Node searchNode(char data) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(this.head);
        while (!queue.isEmpty()) {
            Node 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) {
        Node node = this.searchNode(data);

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

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

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

이진 트리 사용

public class Main {
    public static void main(String[] args) {
        // 트리에 넣을 배열
        char[] arr = new char[10];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (char)('A' + i);
        }

        BinaryTree bt = new BinaryTree(arr);

        // root node
        System.out.println(bt.head.data);       // A


        // A's child node
        Node A = bt.searchNode('A');
        if (A.left != null) {
            System.out.println(A.left.data);        // B
        }
        if (A.right != null) {
            System.out.println(A.right.data);       // C
        }


        // E's parent node
        Node E = bt.searchNode('E');
        System.out.println(E.parent.data);          // B


        // Leaf node
        for (int i = 0; i < arr.length; i++) {
            Node cur = bt.searchNode((char)('A' + i));

            if (cur.left == null && cur.right == null) {
                System.out.print(cur.data + " ");       // F G H I J
            }
        }
        System.out.println();


        // F's Depth
        Node F = bt.searchNode('F');
        Node cur = F;
        int cnt = 0;
        while (cur.parent != null) {
            cur = cur.parent;
            cnt ++;
        }
        System.out.println(cnt);        // 2


        // Lv.2 Node
        for (int i = 0; i < arr.length; i++) {
            Node 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 + " ");        // D E F G
            }
        }
        System.out.println();


        // Height
        int maxCnt = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            Node 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(maxCnt);     // 3


        // C's Size
        int size = bt.checkSize('C');       // 3
        System.out.println(size);
    }
}