이진트리의 순회.

이진트리는 분할정복 탐색 알고리즘으로 빠른 속도로 탐색이 가능하다는 장점이 있습니다.

그렇지만 어디까지나 이상적으로 설계가 되어 있을 경우의 이야기지만...

 

* 힙정렬은 이진트리를 이용해서 정렬을 수행합니다.

 

이진트리의 순회를 swift 스럽게 알고리즘으로 만들어보았습니다.

 

세가지 종류가 있는데요.

1. 전위 순회 (preorder) : Root -> Left -> RIght

2. 중위 순회 (inorder) : Left -> Root -> RIght

3. 후위 순회 (postorder) : Left -> Right -> Root

 

class Node {
    let data: Int
    var left: Node?
    var right: Node?
    
    init(data: Int) {
        self.data = data
    }
}

class Tree {    
    private var nodes = [Node]()
    
    init(size: Int) {
        for index in 0...size {
            let node = Node(data: index)
            nodes.append(node)
            
            guard index >= 2 else { continue }
            
            let root = index / 2
            if index % 2 == 0 {
                nodes[root].left = node
            } else {
                nodes[root].right = node
            }
        }
    }
    
    func traversal(with order: Order, root: Int = 1) -> String {
        return order.traversal(node: nodes[root])
    }
}

extension Tree {
    
    enum Order: Int {
        case pre
        case `in`
        case post
        
        func traversal(node: Node?) -> String {
            guard let node = node else { return "" }
            
            var buffer: [String] = [
                traversal(node: node.left),
                traversal(node: node.right)
            ]
            
            let data = "\(node.data)"
            buffer.insert(data, at: rawValue)
            
            return buffer
                .filter { !$0.isEmpty }
                .joined(separator: " ")
        }
    }
}

let tree = Tree(size: 20)
let preorder = tree.traversal(with: .pre)
print("preorder = \(preorder)")
let inorder = tree.traversal(with: .in)
print("inorder = \(inorder)")
let postorder = tree.traversal(with: .post)
print("postorder = \(postorder)")

// 결과
// preorder = 1 2 4 8 16 17 9 18 19 5 10 20 11 3 6 12 13 7 14 15
// inorder = 16 8 17 4 18 9 19 2 20 10 5 11 1 12 6 13 3 14 7 15
// postorder = 16 17 8 18 19 9 4 20 10 11 5 2 12 13 6 14 15 7 3 1

Tree의 구조는 만들어주고, 그것에 대한 Order를 enum으로 만들어서 타입에 따라서 동작할 수 있도록 하였습니다.