스위프트로 구현하는 자료구조 7: 트리와 이진 트리(Binary Tree)

트리의 정의

먼저, 트리에 대해서 정의해보면, 트리는 몇가지 조건을 만족하는 그래프입니다.

 

1) 트리의 간선에는 방향이 없습니다. 즉, 트리는 무방향 그래프입니다. 

2) 트리를 구성하는 모든 노드는 연결되어 있는 연결 그래프입니다. 연결된 간선 중 하나만 삭제해도 연결 그래프가 깨집니다.

-> 여기서 연결그래프란 그래프의 임의의 노드 사이에 항상 경로가 존재함을 의미합니다. 어떤 노드로 가는 경로가 없어지면 해당 노드는 트리에 포함될 수 없겠죠?

3) 트리를 구성하는 간선의 개수는 항상 노드의 개수보다 하나 적습니다. 따라서 사이클이 발생하지 않습니다.

 

이진 트리 (Binary Tree)

이진 트리는 트리를 구성하는 각 노드가 최대 두 개의 자식 노드를 가지는 트리를 의미합니다.

 

이진 트리의 종류

이진 트리는 형태에 따라서 몇 가지 종류로 나눌 수 있습니다.

포화 이진 트리

포화 이진 트리는 위 그림처럼 마지막 리프노드를 가진 레벨이 노드를 더 추가할 수 있는 공간없이 가득 차 있는 이진 트리를 말합니다. 따라서 포화 이진 트리의 노드 개수는 항상 트리의 높이 h에 대해 2^h - 1 개가 됩니다.

완전 이진 트리

완전 이진 트리는 모든 레벨이 왼쪽부터 채워져있는 트리를 의미합니다. 위 그림 처럼 한 레벨이 가득 채워지지 않아도 8번 노드가 가장 왼쪽에 채워져 있기 때문에 완전 이진 트리가 됩니다.

반면에 이런 경우는 왼쪽에 아직 채워지지 않은 공간이 있음에도 중간부터 노드가 들어가있기 때문에 완전 이진 트리가 될 수 없습니다. 

 

가장 왼쪽부터 차례대로 채우는 완전 이진 트리 특성 때문에 완전 이진 트리는 배열로 쉽게 표현할 수 있습니다.

이렇게 배열의 0번째 요소를 비워둔 채로 1번 인덱스를 루트노드로 만들면 오른쪽 자식 노드는 현재 인덱스 i에 대해 i * 2 로 찾아갈 수 있고, 오른쪽  자식 노드는 i * 2 + 1 로 찾아갈 수 있습니다.

편향 이진 트리

 

편향 이진 트리는 트리의 노드가 한쪽 자식 노드로만 계속 연결되면서 노드의 개수는 적지만 트리의 높이는 커지는 모습의 트리를 의미합니다.

 

이진 트리 순회

이진 트리는 트리와 트리에 포함된 서브 트리들의 루트 노드를 언제 방문하는지에 따라 세 가지 방법으로 트리의 전체 노드를 순회할 수 있습니다. 

 

전위 순회

전위 순회는 다른 노드들을 방문 하기 이전에 루트노드를 먼저 방문하는 순회방식입니다. 루트 -> 왼쪽 -> 오른쪽 순으로 트리의 노드들을 방문한다고 생각하면 됩니다.

이 트리를 전위 순회하면 A->B->D->E->C->F->G 의 순서대로 방문하게 됩니다. 보이듯이 어떤 노드의 서브트리를 순회할 때는 해당 노드의 왼쪽의 모든 서브트리가 완료되어야 오른쪽 서브트리를 순회하게 됩니다. 

 

중위 순회

중위 순회는 루트 노드를 중간에 방문하는 순회 방법입니다. 따라서 왼쪽->루트->오른쪽의 순서대로 노드를 방문하게 됩니다.

위 예시와 동일한 트리를 중위 순회하게 되면 D->B->E->A->F->C->G의 순서대로 노드를 방문합니다.

 

후위 순회

후위 순회는 루트 노드를 가장 마지막으로 방문하는 순회 방법입니다. 왼쪽 서브트리의 탐색이 항상 오른쪽보다 선행되기 때문에 왼쪽->오른쪽->루트의 순서대로 노드를 방문하게 됩니다.

동일한 트리를 후위 순회하면 D->E->B->F->G->C->A의 순서대로 방문하게 됩니다. 서브트리를 구성하는 루트 노드는 자신의 왼쪽과 오른쪽 자식노드가 모두 방문 된 이후에 방문됩니다. 

 

완전 이진 트리 구현하기

이전에 힙을 구현하면서 이미 완전 이진트리를 구현했지만, 이번에는 링크드 리스트로 구현해 전위, 중위, 후위 순회까지 구현해보도록 하겠습니다. 

 

뼈대 만들기

TreeNode

먼저 트리의 노드가 될 자료구조부터 정의하겠습니다.

import Foundation

final class TreeNode<T: Comparable> {
    let data: T
    var leftChild: TreeNode?
    var rightChild: TreeNode?
    
    init(data: T) {
        self.data = data
    }
    
    var asString:String { return treeString(self){("\($0.data)",$0.leftChild,$0.rightChild)}  }
}

이렇게 구성했는데요, data에는 트리에 담을 데이터를 넣어주고, 자신의 왼쪽 자식 노드와 오른쪽 자식 노드의 참조값을 저장할 수 있도록 했습니다.

 

asString 프로퍼티는 트리를 엄청 예쁘게 출력해주는 treeString 메서드를 호출하는데 이건 스택 오버플로우에서 진짜 잘 만들어주신 분이 계셔서 그대로 사용했어요!

 

이 질문에 대한 답변에 메서드가 정의되어 있구요,

How to “draw” a Binary Tree in Console?

 

적용하면 이렇게 예쁘게 콘솔에 트리가 출력됩니다!

 

노드 추가

이번 구현에서는 다른 연산은 구현하지 않고(이진 트리에 대해서는 정형화된 방법이 없기 때문에) 노드를 추가하는 연산만 구현한 뒤에 순회 함수를 구현하고 호출만 해보려고 합니다. 

 

완전 이진트리이기 때문에 항상 가장 왼쪽 부터 차례대로 노드를 추가해주어야겠죠?

    private func add(newNode: TreeNode<T>, to node: TreeNode<T>) {
        var queue = Queue<TreeNode<T>> ()
        queue.push(root!)
        
        while !queue.isEmpty {
            let now = queue.pop()
            if now?.leftChild == nil {
                now?.leftChild = newNode
                return
            }
            if now?.rightChild == nil {
                now?.rightChild = newNode
                return
            }
            queue.push(now!.leftChild!)
            queue.push(now!.rightChild!)
        }
    }

그래서 이렇게 BFS를 사용해서 트리를 순회해주고, 아직 자식 노드가 완전히 채워지지 않은 노드를 만나면 왼쪽 자식 노드부터 채워주는 방식으로 구현했습니다. 사실 그래프에 대한 포스트를 안써서 BFS를 여기서 소개하는게 맞을까 싶지만.. BFS에 대한 내용은 여기에 정리되어 있으니 어떻게 동작하는지 잘 모르시겠다면 참고하시면 좋을 것 같아요!

[알고리즘 정리] 너비 우선 탐색(BFS)

 

트리 순회

트리의 순회는 재귀적인 방식으로 이루어집니다. 그런데 생각해보면 사실 왼쪽 자식 노드는 항상 오른쪽 자식 노드보다 먼저 방문 되니, 루트노드를 언제 방문하는지만 다르게 구현해주면 될 것 같습니다.

 

먼저 전위 순회 결과를 출력하는 코드입니다!

    private func printPreorder(node: TreeNode<T>?) {
        guard let node = node else { return }
        print(node.data, terminator: " ")
        self.printPreorder(node: node.leftChild)
        self.printPreorder(node: node.rightChild)
    }

재귀적으로 전위 순회를 진행하면서 출력을 해주는데요, 루트 노드를 먼저 출력해주고 왼쪽 자식 노드가 루트 노드인 서브트리로 이동해 순회를 모두 마친뒤, 오른쪽 자식 노드가 루트 노드인 서브트리로 이동해 순회를 마치고 돌아오는 코드입니다.

이런 트리가 있다면 먼저 A를 출력해주고, B를 루트로 가지는 서브트리로 이동할 테니 재귀적으로 호출된 새로운 함수는

이 서브트리를 가지고 다시 똑같은 로직을 수행합니다. 따라서 이제 B를 출력하고 왼쪽 자식노드를 루트로 가지는 서브트리로 재귀 호출을 하니

이번엔 자식 노드가 없는 리프노드를 가지고 로직을 수행합니다. 여기서 D를 출력 하고 재귀적으로 한 번 더 호출하지만 nil이 루트이기 때문에 함수가 리턴되면서 모든 왼쪽 서브트리의 순회를 마치게 됩니다.

 

이 작업이 전체 트리에 대해서 완료되면 전위 순회의 결과가 출력됩니다.

 

중위 순회

로직은 동일하니 그림은 이제 생략하겠습니다..

    private func printInorder(node: TreeNode<T>?) {
        guard let node = node else { return }
        self.printInorder(node: node.leftChild)
        print(node.data, terminator: " ")
        self.printInorder(node: node.rightChild)
    }

중위 순회의 로직은 전위 순회와 거의 동일한데요, 단순히 루트 노드의 출력이 왼쪽 자식 노드를 루트로 가지는 서브트리의 순회가 모두 끝나야 이루어진다는 것만 다릅니다. 

후위 순회

    private func printPostorder(node: TreeNode<T>?) {
        guard let node = node else { return }
        self.printPostorder(node: node.leftChild)
        self.printPostorder(node: node.rightChild)
        print(node.data, terminator: " ")
    }

후위 순회도 마찬가지입니다. 후위 순회는 왼쪽와 오른쪽 자식 노드의 순회가 모두 끝난 뒤에 루트노드를 출력하기 때문에 루트노드를 출력하는 코드를 재귀 함수의 가장 뒤에 넣어주는 것만 변경되었습니다.

 

전체 코드

 

GitHub - jeonyeohun/Data-Structures-In-Swift: 👷🏻‍♂️ STL 왜 없어.. 스위프트로 구현하는 자료구조

자료구조 시리즈의 코드들은 이 레포에서 모두 확인할 수 있어요!