[Swift] 이진 트리

안녕하세요. 밀쿄입니다. 오늘은 이진트리에 대해서 알아보겠습니다.

이진 트리는 최소한 2개의 자식 노드를 가지고 있습니다.

그럼 스위프트 코드로 한 번 만들어보겠습니다.

일단 트리는 노드로 구성되어있습니다. 

그럼 먼저 노드란 클래스를 구성합니다.

그 후 그 노드가 가지는 값을 표현하는 프로퍼티와 자식노드를 나타내는 프로퍼티가 존재하면 될 것 같습니다.

public class BinaryNode<Element> {
    public var value: Element
    public var leftChild: BinaryNode?
    public var rightChild: BinaryNode?
    
    public init(value: Element) {
        self.value = value
    }
}

이렇게 해주면 될 것 같습니다.

트리에는 세 가지 순회 방식이 있습니다. 전위 중위 후위 순회 방식이 대표적으로 있습니다.

전위는 root -> Left Child -> RightChild / 중위는 LeftChild - Root -> RightChild

후위는 LeftChild - RightChild - Root 이렇게 순회하는 방식을 말합니다.

위 사진 트리를 스위프트 코드로 만들보겠습니다.

var tree: BinaryNode<String> = {
    let d = BinaryNode(value: "D")
    let b = BinaryNode(value: "B")
    let f = BinaryNode(value: "F")
    let a = BinaryNode(value: "A")
    let c = BinaryNode(value: "C")
    let e = BinaryNode(value: "E")

    d.leftChild = b
    d.rightChild = f
    b.leftChild = a
    b.rightChild = c
    f.rightChild = e

    return d
}()

그럼 이걸로 전위 순회를 돌아보겠습니다.

먼저 아까 만들어둔 클래스에 다음과 같은 코드를 한 줄 추가합니다

public typealias Action = ((Element) -> Void)

그리고 나서 전위순회를 시작해보겠습니다.

extension BinaryNode {
    public func preOrder(action: Action) {
        action(value)
        leftChild?.preOrder(action: action)
        rightChild?.preOrder(action: action)
    }
}
tree.preOrder { str in
    print(str)
}
//출력
//D
//B
//A
//C
//F
//E

아까 이야기했듯이 루트 -> left -right 순입니다.

중위 순회를 한 번 살펴보겠습니다

extension BinaryNode {
    public func inOrder(action: Action) {
        leftChild?.inOrder(action: action)
        action(value)
        rightChild?.inOrder(action: action)
    }
}
tree.inOrder { str in
    print(str)
}
//출력
//A
//B
//C
//D
//F
//E

아까 이야기했듯이 Left -> Root -? Right 순입니다.

마지막으로 후위 순위도 어떻게 되는지 한 번 살펴보겠습니다.

extension BinaryNode {
    public func postOrder(action: Action) {
        leftChild?.postOrder(action: action)
        rightChild?.postOrder(action: action)
        action(value)
    }
}
tree.postOrder { str in
    print(str)
}
//출력
//A
//C
//B
//E
//F
//D

아까 이야기했듯이 Left -> Right -> Root 순입니다.

이상 끝입니다.