[Data Structure 기초] Tree

Study for Backend/Data Structure

[Data Structure 기초] Tree

지미니박 2024. 3. 11. 23:26

Tree(트리)

- 노드와 링크로 구성된 자료구조(그래프의 일종, Cycle 없음.)

- 하나의 노드에서 시작해서 다른 정점들을 순회하여 자기 자신에게 돌아오는 순환이 없는 연결그래프

- 계층적 구조를 나타낼 때 사용

- 폴더 구조 (디렉토리, 서브 디렉토리) , 조직도, 가계도 등

- 다른 노드로 이동하는 경로는 유일

- 노드가 N개인 트리의 Edge의 수는 N-1개

- Acyclic

- 모든 노드는 서로 연결 되어있음

- 하나의 Edge를 끊으면 2개의 Sub-Tree로 분리됨

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

Binary Tree(트리)

- 각 노드는 최대 2개의 자식을 가질 수 있음

- 자식 노드는 좌우를 구분함

( 왼쪽 자식 : 부모 노드의 왼쪽 아래 / 오른쪽 자식 : 부모 노드의 오른쪽 아래 )

- 포화 이진 트리의 높이가 h일 때, 노드의 수는 2^h - 1개

- 포화 or 완전 이진 트리의 노드가 N개 일 때, 높이는 logN

- 이진 트리의 노드가 N개 일 때, 최대 가능 높이는 N

이진트리 종류

- 포화 이진 트리 (Perfect Binary Tree) : 모든 레벨에서 노드들이 꽉 채워져 있는 트리

- 완전 이진 트리 (Complete Binary Tree) : 마지막 레벨을 제외하고 노드들이 모드 채워져 있는 트리

- 정 이진 트리 (Full Binary Tree) : 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리

- 편향 트리 (Skewed Binary Tree) : 한 쪽으로 기울어진 트리 , 사향 트리

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

Traversal (이진 트리의 순회)

- 모든 노드를 빠뜨리거나 중복하지 않고 방문하는 연산

- DFS 순회 방법

--> 전위 순회 (Preorder Traversal)

- 방문순서 : 현재 노드 -> 왼쪽 노드 -> 오른쪽 노드

--> 중위순회 (Inorder Traversal)

- 방문순서 : 왼쪽 노드 -> 현재 노드 -> 오른쪽 노드

--> 후위순회 (Postorder Traversal)

- 방문순서 : 왼쪽 노드 -> 오른쪽 노드 -> 현재 노드

- BFS 순회 방법

--> 레벨 순회 (Levelorder Traversal)

- 방문순서 : 위쪽 레벨부터 노드 -> 오른쪽 노드

이진트리 구현

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

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


//배열을 이용한 이진 트리 구성, 순회
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 = 0; i < this.arr.length; i++) {
            System.out.print(this.arr[i] + " ");
        }
        System.out.println();
    }
}

public class tree {
    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();
    }
}