[자료구조] 트리(Tree)와 이진 트리(Binary Tree)

트리 (Tree)

노드(Node)와 간선(Edge)로 이루어진 비선형 자료구조

 

트리의 용어

구분	설명
간선(Edge)	두 노드를 연결하는 선(링크)
노드(Node)	트리를 구성하는 기본 원소
루트 노드(Root)	트리의 최 상위 노드
리프 노드(Leaf)	자식 노드가 없는 노드
형제 노드(Sibling)	같은 부모를 갖는 노드
노드의 크기(Size)	자신을 포함한 모든 자식 노드의 개수
노드의 깊이(depth)	루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
노드의 레벨(Level)	트리의 특정 깊이를 가지는 노드의 집합
노드의 차수(Degree)	각 노드의 자식 노드 개수
트리의 차수(Degree of Tree)	트리의 최대 차수
트리의 높이(Height)	루트 노드에서 가장 깊숙이 있는 노드의 깊이

 

트리의 특징

• 부모-자식 관계의 계층 구조를 가진다.
• 루트 노드를 제외한 모든 노드는 반드시 하나의 부모 노드를 가진다.
• 트리 내의 특정 노드와 다른 특정 노드까지의 경로는 반드시 존재한다.
• 노드가 N개인 트리는 항상 N-1개의 간선을 가진다.
• 사이클이 존재하지 않는다.

 

이진 트리(Binary Tree)

자식의 노드 수가 두 개 이하인 트리

 

이진 트리 종류

종류	설명
정이진 트리 (Full)	자식 노드가 0 또는 두 개인 이진 트리
완전 이진 트리 (Complete)	- 왼쪽부터 채워져 있는 이진 트리 - 마지막 레벨을 제외하고 모든 레벨이 채워져 있는 형태 - 마지막 레벨의 경우 왼쪽부터 채워져 있는 형태
변질 이진 트리 (Degenerate)	자식 노드가 하나밖에 없는 이진 트리
포화 이진 트리 (Perfect)	모든 노드가 꽉 차 있는 이진 트리
균형 이진 트리 (Balanced)	- 왼쪽과 오른쪽 노드의 높이 차이가 1이하인 이진 트리 - map, set을 구성하는 레드 블랙 이진 트리

 

이진 트리 순회

이진 트리에 속하는 모든 노드를 한 번씩 방문하는 방법으로, 주로 재귀적으로 구현된다. 재귀를 통해 노드를 방문하면서 순회를 수행할 수 있다. 또한 스택이나 큐를 이용하여 반복적으로 순회할 수도 있다.

 

이진 트리를 순회하는 방법으로는 세 가지가 있다.

• 전위 순회(Pre-Order)
• 중위 순회(In-Order)
• 후위 순회(Post-Order)

전위 순회 순서(가운데 → 왼쪽 → 오른쪽)

• Root 노드 방문
• 왼쪽 서브 트리 전위 순회
• 오른쪽 서브 트리 전위 순회
• F → B → A → D → C → E → G → I → H

중위 순회 순서(왼쪽 → 가운데 → 오른쪽)

• 왼쪽 서브 트리 중위 순회
• Root 노드 방문
• 오른쪽 서브 트리 중위 순회
• A → B → C → D → E → F → G → H → I

후위 순회 순서(왼쪽 → 오른쪽 → 가운데)

• 왼쪽 서브 트리 후위 순회
• 오른쪽 서브 트리 후위 순회
• Root 노드 방문
• A → C → E → D → B → H → I → G → F

 

이진 트리 순회 코드 구현

Node.swift

class Node<T: Comparable> {
    var data: T
    var left: Node?
    var right: Node?
    
    init(data: T) {
        self.data = data
    }
}

 

BinaryTree.swift

class BinaryTree<T: Comparable> {
    // 전위 순회 순서(가운데 → 왼쪽 → 오른쪽)
    func preOrder(node: Node<T>?) {
        guard let node = node else { return }
        
        print(node.data, terminator: " -> ")
        self.preOrder(node: node.left)
        self.preOrder(node: node.right)
    }
    
    // 중위 순회 순서(왼쪽 → 가운데 → 오른쪽)
    func inOrder(node: Node<T>?) {
        guard let node = node else { return }
        
        self.inOrder(node: node.left)
        print(node.data, terminator: " -> ")
        self.inOrder(node: node.right)
    }
    
    // 후위 순회 순서(왼쪽 → 오른쪽 → 가운데)
    func postOrder(node: Node<T>?) {
        guard let node = node else { return }
        
        self.postOrder(node: node.left)
        self.postOrder(node: node.right)
        print(node.data, terminator: " -> ")
    }
}

 

실행 결과