[Data Structures] Binary Trees

Binary Tree

용어 설명

바이너리 트리는 기존 트리에서도 모든 노드의 최대 자식이 둘인 트리를 말한다.

Binary Tree 구현해보기

자식이 둘(left, right)인 BinaryNode를 생성하면 된다.

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

Traversal Algorithms

var tree: BinaryNode<Int> = {
    let zero = BinaryNode(value: 0)
    let one = BinaryNode(value: 1)
    let five = BinaryNode(value: 5)
    let seven = BinaryNode(value: 7)
    let eight = BinaryNode(value: 8)
    let nine = BinaryNode(value: 9)
    
    seven.leftChild = one
    one.leftChild = zero
    one.rightChild = five
    seven.rightChild = nine
    nine.leftChild = eight
    
    return seven
}()

로 생성한 바이너리 트리를 in-order, pre-order, post-order로 돌아본다.

In-order traversal

• 만약 현재 노드가 left child를 가진다면 recursive 하게 그 child를 방문.
• 그 다음에 원래의 현재노드 방문
• 만약 현재 노드가 right child를 가진다면 recursive 하게 그 child를 방문

BinaryNode에 아래 코드를 넣는다.

func traverseInOrder(visit: (T) -> Void) {
        leftChild?.traverseInOrder(visit: visit)
        visit(value)
        rightChild?.traverseInOrder(visit: visit)
    }

왼쪽 자식부터 재귀로 돌고 그 다음 현재 노드를 방문, 마지막에 오른쪽 자식들을 모두 방문하는 코드이다.

그림으로 보면 이렇다.

Pre-order traversal

• 현재 노드를 먼저 방문한다. 그 이후에 차례로 왼쪽과 오른쪽 자식을 방문한다.

func traversePreOrder(visit: (T) -> Void) {
        visit(value)
        leftChild?.traverseInOrder(visit: visit)
        rightChild?.traverseInOrder(visit: visit)
    }

재귀호출의 순서만 바뀌었는데 결과가 아래처럼 나온다

아까와 순서가 다르다.

Post-order traversal

• 왼쪽, 오른쪽 자식을 방문한 뒤 현재 노드를 마지막에 방문한다. 코드로 보면 visit(value)가 가장 마지막으로 내려간다.

func traversePostOrder(visit: (T) -> Void) {
        leftChild?.traverseInOrder(visit: visit)
        rightChild?.traverseInOrder(visit: visit)
        visit(value)
    }

루트 노드가 가장 마지막에 찍힌다.