BinarySearchTree.playground

import UIKit

indirect enum BinarySearchTree<Element: Comparable> {
    case Leaf
    case Node(BinarySearchTree<Element>, Element, BinarySearchTree<Element>)
}

extension BinarySearchTree {
    init() {
        self = .Leaf
    }
    
    init(_ value: Element) {
        self = .Node(.Leaf, value, .Leaf)
    }
}

extension BinarySearchTree {
    var count: Int {
        switch self {
        case .Leaf:
            return 0
        case let .Node(left, _, right):
            return left.count + 1 + right.count
        }
    }
}

/// 验证count
let node0 = BinarySearchTree(2)
let node1 = BinarySearchTree(3)
let tree0 = BinarySearchTree.Node(node0, 1, node1)
print(tree0.count)

extension BinarySearchTree {
    var elements: [Element] {
        switch self {
        case .Leaf:
            return []
        case let .Node(left, value, right):
            return left.elements + [value] + right.elements
        }
    }
}

/// 验证elements,验证了递归的顺序性
print(tree0.elements)

extension BinarySearchTree {
    var isEmpty: Bool {
        if case .Leaf = self {
            return true
        }
        return false
    }
}

/// 验证isEmpty
print(tree0.isEmpty)
print(BinarySearchTree<Int>.Leaf.isEmpty)

extension BinarySearchTree {
    var isBST: Bool {
        switch self {
        case .Leaf:
            return true
        case let .Node(left, x, right):
            return left.elements.allSatisfy { y in y < x }
                && right.elements.allSatisfy { y in y > x }
                && left.isBST
                && right.isBST
        }
    }
}

print(tree0.isBST)

let node2 = BinarySearchTree(2)
let node4 = BinarySearchTree(4)
var tree3 = BinarySearchTree.Node(node2, 3, node4)
print(tree3.isBST)

let aaa = [2, 3, 4].allSatisfy { y in y > 1 }
print(aaa)


extension BinarySearchTree {
    func contains(x: Element) -> Bool {
        switch self {
        case .Leaf:
            return false
        case let .Node(_, y, _) where x == y:
            return true
        case let .Node(left, y, _) where x < y:
            return left.contains(x: x)
        case let .Node(_, y, right) where x > y:
            return right.contains(x: x)
        default:
            fatalError("The impossible occurred")
        }
    }
}

print(tree3.contains(x: 2))
print(tree3.contains(x: 5))

extension BinarySearchTree {
    mutating func insert(x: Element) {
        switch self {
        case .Leaf:
            self = BinarySearchTree(x)
        case .Node(var left, let y, var right):
            if x < y { left.insert(x: x) }
            if x > y { right.insert(x: x) }
            self = .Node(left, y, right)
        }
    }
}

tree3.insert(x: 5)
print(tree3.elements)