트리

트리(Tree)

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

트리의 구조

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

트리의 특징

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

   이진 트리(Binary Tree)

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

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

 

 

이진 트리 종류(1)

포화 이진트리(Perfect Binary tree)

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

완전 이진 트리(Complete Binary tree)

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

 

이진 트리 종류(2)

정 이진 트리(Full Binary tree)

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

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

- 한 쪽으로 기울어진 트리

 

이진 트리 종류(3)

균형 이진트리(Balanced Binary Tree)

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

 

 

이진 트리 특징

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

 

이진 트리의 순회(Traversal)

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

순회종류는 4가지

- 전위 순회, 중위 순회, 후위 순회 (DFS)

- 레벨 순회 (BFS)

 

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

- Preorder Traversal-

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

 

 

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

- Inorder Traversal-

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

 

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

- Postorder Traversal-

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

 

 

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

- Levelorder Traversal-

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

 

 

이진 트리 구현

 

배열

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

---

 

value(1)

L1

L2

                  

  연결 리스트

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

 

 

배열을 이용한 순회

- 전위 순회

 // 재귀함수 이해도 *****
 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 < arr.length) {
            inOrder(left);   
        }
        System.out.print(this.arr[idx] + " "); 

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

- 후위 순회

   public void postOrder(int idx){ // (후위 순회) 왼쪽노드 -> 오른쪽 노드 - > 현재 노드
        int left = 2 * idx + 1;
        int right = 2 * idx + 2;
        if (left < arr.length){
            postOrder(left);
        }
        if (right < arr.length){
            postOrder(right);
        }
            System.out.print(this.arr[idx] + " ");
    }

연결리스트를 이용한 순회

기본 생성자

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

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

연결리스트 연결 작업

class BinaryTree2 {
    Node head;
    BinaryTree2(){}
    BinaryTree2(char[] arr){ // char 배열을 받아서 node 형태의 배열로 전환
        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.println(node.data + "");
        this.preOrder(node.left);
        this.preOrder(node.right);
    }

- 중위 순회

 public void inOrder(Node node){ // 중위 순회
        if(node == null){ // 재귀함수의 탈출 조건
            return;
        }
        this.inOrder(node.left);
        System.out.println(node.data + "");
        this.inOrder(node.right);
}

- 후위 순회

public void postOrder(Node node){ // 후위 순회
        if(node == null){ // 재귀함수의 탈출 조건
            return;
        }
        this.inOrder(node.left);
        this.inOrder(node.right);
        System.out.println(node.data + "");
    }