Tree 트리 구조 알고리즘

Tree란? 

한 개 이상의 노드로 이루어진 유한 집합

• 상위 원소와 하위 원소의 관계가 있는 계층적 자료 구조
• 하위 원소로 내려가면서, 나무의 가지가 자라나는 모습에서 Tree라는 이름이 붙었다.

• 각각 데이터를 담고 있는 원소를 노드 또는 정점이라고 한다.
• 노드 중 최상위 노드를 루트(root)노드라 한다.
• 각 노드는 0개 이상의 자식 노드를 가질 수 있다.
• 하나의 부모에 여러 자식이 연결되어 있다.
• 하나의 자식은 둘 이상의 부모를 가질 수 없다.
• 노드의 갯수가 N개 일 때, N-1개의 간선을 가지고 있다. 그래서 순환 구조가 생기지 않는다.

✅ 형제 노드

• 같은 부모 노드를 가진 자식 노드들

 

✅ 조상 노드

• 간선을 따라 루트 노드까지 가는 경로의 모든 노드들

 

✅ 서브 트리

• 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리

 

✅ 자손 노드

• 서브 트리에 있는 모든 하위 노드
• J의 조상 노드들 = A, B, F

✅ 차수 (Degree)

• 노드에 연결된 자식 노드의 수
• A의 차수: 3, B의 차수 : 2

 

✅ 트리의 차수

• 트리 노드들의 차수 중 제일 큰 값

✅ 높이 (Level)

• 루트에서 노드에 이르는 간선의 수

 

✅ 트리의 높이

• 노드 중 높이가 가장 큰 값

 

✅ 이진 트리 - Binary Tree

• 트리 중에서 모든 부모 노드가 최대 2개의 자식 노드를 가진 트리

모든 노드가 최대 2개의 자식 노드만 가질 수 있기 때문에, 높이가 h인 이진 트리에서

• 레벨이 i 인 노드의 갯수는 최대 2 ^ i 개 이며,
• 트리 전체의 노드의 최소 갯수는 h + 1, 최대 갯수는 2^(h + 1) - 1 이다.

 

✅ 완전 이진 트리

• 제일 깊은 레벨을 제외하고, 모든 레벨에 노드의 갯수가 최대로 차 있으며, 마지막 레벨에 노드가 존재할 경우, 제일 왼쪽부터 차례대로 채워 넣어진 이진 트리이다.

✅ 편향 이진 트리

• 이진 트리의 조건을 유지하면서, 높이가 h일 때 이진 트리가 가질 수 있는 최소의 노드 갯수를 가지면서, 한쪽 방향의 자식 노드만 가지는 이진트리이다.
• 왼쪽 편향 이진 트리
• 오른쪽 편향 이진 트리

 

✅ 이진 트리 : 배열로 표현하기

• 완전 이진 트리에 순서대로 번호를 붙여보면 재밌는 현상을 발견 할 수 있다.
• 부모 노드 기준 왼쪽 자식 노드는 자신의 번호에 * 2 를 한 번호를 가지고 있으며, 오른쪽 자식 노드는 자신의 번호에 * 2 + 1 한 번호를 가지고 있게 된다. 또한 자신의 부모 노드가 가지고 있는 번호는, 자신이 번호를 나머지를 버림하여 2로 나눈 결과이다. 이 사실을 이용하면 배열을 이용해 쉽게 이진 트리를 구현할 수 있다. 지금 노드의 인덱스를 i 라고 한다면,

• 현재 노드에서 왼쪽 자식 노드를 찾고 싶다면 i * 2 인덱스에서,
• 현재 노드에서 오른쪽 자식 노드를 찾고 싶다면 i * 2 + 1 인덱스에서,
• 현재 노드의 부모 노드를 찾고 싶다면 i / 2 (소수점 버림) 인덱스에서 찾을 수 있다. 또한 어느 h 레벨의 첫 원소는 2 ^ h 에서 시작한다.

배열로 표현된 이진 트리는, 편향 이진 트리나, 몇몇 자식 노드가 없는 경우에 대해서는 메모리 낭비가 심하게 된다. 예를 들어 높이가 3인 오른쪽 편향 이진 트리의 경우, 높이가 3일때 제일 큰 원소는 15의 위치에 들어가야 하기 때문에 최소 크기 16의 배열에 동일하게 4개의 원소만 들어가게 된다.

 

✅ 이진 트리 순회

이진 트리의 각 노드를 한번씩만 방문하는 체계적인 방법

• 전위순회: 루트 노드 → 왼쪽 서브트리 → 오른쪽 서브트리
• 중위순회: 왼쪽 서브트리 → 루트 노드 → 오른쪽 서브트리
• 후위순회: 왼쪽 서브트리 → 오른쪽 서브트리 → 루트 노드

---

이진 트리 순회의 코드로 풀어보자

 

💻 1. 전위 순회

public class TreeTraverse {
    private int nodes;
    private int[] arr; //이진트리를 표현하기 위한 배열

    // { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}
    public void setArr(int[] arr ){
        this.arr = arr;
        this.nodes = arr.length;

    }
    //완전 이진트리 전위 순회 V -> L -> R
    //preorder(): System.out.println(V) -> preorder(L) -> preorder(R)
    public void traversPreorder(int node){
        if (node < this.nodes && arr[node] != 0)  {
            System.out.print(arr[node] + ", "); //방문한다.
            this.traversPreorder(node * 2); //왼쪽 자식(i * 2)을 루트로 다시 preorder 호출
            this.traversPreorder(node * 2 + 1); //오른쪽 자식(i * 2 + 1)을 루트로 다시 preorder 호출

        }
    }
    public static void main(String[] args) {
        TreeTraverse tree = new TreeTraverse();
        tree.setArr(new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12});

        tree.traversPreorder(1); // 처음 방문점은 root node
        System.out.println();
    }
}

전위 순회 실행 결과

 

💻2.  중위 순회

//완전 이진트리 중위 순회 L -> V -> R
    //inorder(): preorder(L) ->  System.out.println(L) -> preorder(R)
    public void traversInorder(int node){
        if (node < this.nodes && arr[node] != 0)  {
            this.traversInorder(node * 2); //왼쪽 자식(i * 2)을 루트로 다시 preorder 호출
            System.out.print(arr[node] + ", "); //나 방문
            this.traversInorder(node * 2 + 1); //오른쪽 자식(i * 2 + 1)을 루트로 다시 preorder 호출
        }
    }

중위 순회 실행 결과

 

💻 3. 후위 순회

//완전 이진트리 후위 순회 L -> R ->  V
    //inorder(): preorder(L) ->  preorder(R) -> System.out.println(V)
    public void traversPostorder(int node){
        if (node < this.nodes && arr[node] != 0)  {
            this.traversPostorder(node * 2); //왼쪽 자식(i * 2)을 루트로 다시 preorder 호출
            this.traversPostorder(node * 2 + 1); //오른쪽 자식(i * 2 + 1)을 루트로 다시 preorder 호출
            System.out.print(arr[node] + ", "); //나 방문
        }
    }

후위 순회 실행 결과

 

💻 정리) 완전 이진 트리 순회 전체 코드

package tree;

import com.sun.source.tree.Tree;

public class TreeTraverse {
    private int nodes;
    private int[] arr; //이진트리를 표현하기 위한 배열

    // { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}
    public void setArr(int[] arr ){
        this.arr = arr;
        this.nodes = arr.length;

    }
    //완전 이진트리 전위 순회 V -> L -> R
    //preorder(): System.out.println(V) -> preorder(L) -> preorder(R)
    public void traversPreorder(int node){
        if (node < this.nodes && arr[node] != 0)  {
            System.out.print(arr[node] + ", "); //방문한다.
            this.traversPreorder(node * 2); //왼쪽 자식(i * 2)을 루트로 다시 preorder 호출
            this.traversPreorder(node * 2 + 1); //오른쪽 자식(i * 2 + 1)을 루트로 다시 preorder 호출

        }
    }
    //완전 이진트리 중위 순회 L -> V -> R
    //inorder(): preorder(L) ->  System.out.println(V) -> preorder(R)
    public void traversInorder(int node){
        if (node < this.nodes && arr[node] != 0)  {
            this.traversInorder(node * 2); //왼쪽 자식(i * 2)을 루트로 다시 preorder 호출
            System.out.print(arr[node] + ", "); //나 방문
            this.traversInorder(node * 2 + 1); //오른쪽 자식(i * 2 + 1)을 루트로 다시 preorder 호출
        }
    }
    //완전 이진트리 후위 순회 L -> R ->  V
    //inorder(): preorder(L) ->  preorder(R) -> System.out.println(V)
    public void traversPostorder(int node){
        if (node < this.nodes && arr[node] != 0)  {
            this.traversPostorder(node * 2); //왼쪽 자식(i * 2)을 루트로 다시 preorder 호출
            this.traversPostorder(node * 2 + 1); //오른쪽 자식(i * 2 + 1)을 루트로 다시 preorder 호출
            System.out.print(arr[node] + ", "); //나 방문
        }
    }

    public static void main(String[] args) {
        TreeTraverse tree = new TreeTraverse();
        tree.setArr(new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12});
        //전위순회
        tree.traversPreorder(1); // 처음 방문점은 root node
        System.out.println();
        //중위 순회
        tree.traversInorder(1);
        System.out.println();
        //후위 순회
        tree.traversPostorder(1);
        System.out.println();
    }
}

 

전체 실행 결과

순서대로 전위순회, 중위순회, 후위순회이다.

---