有趣的 Swift 3 算法。

今天分享用swift3实现在二叉搜索树中递归搜索某一个特定的值！
这个算法没有什么难度，了解二叉搜索树的性质 + 递归搜索 + swift基础语法 即可完成！

准备

打开XCode，新建Playground，创建searchBinaryTreeDemo。

样例树

// 1.
//
//              9
//            /   \
//           6     10
//          / \     \
//         5   7     11
//

创建结点

// 2.
class Node {
    let value: Int
    var leftChild: Node?
    var rightChild: Node?

    init(value: Int, leftChild: Node?, rightChild:Node?) {
        self.value = value
        self.leftChild = leftChild
        self.rightChild = rightChild
    }
}

子结点为可选类型！

构建样例树

下面利用上面的Node结构创建样例树

// left branch

let fiveNode = Node(value: 5, leftChild: nil, rightChild: nil)
let sevenNode = Node(value: 7, leftChild: nil, rightChild: nil)
let sixNode = Node(value: 6, leftChild: fiveNode, rightChild: sevenNode)

// right branch
let elevenNode = Node(value: 11, leftChild: nil, rightChild: nil)

let tenNode = Node(value: 10, leftChild: nil, rightChild: elevenNode)

let nineRootNode = Node(value: 9, leftChild: sixNode, rightChild: tenNode)

实现算法

中序遍历～

//3 .
// 实现算法，在这棵树中寻找一个特定的值。
func search(_ node: Node?, _ searchValue: Int) -> Bool {
    if node == nil {
        return false
    }
    if node?.value == searchValue {
        return true;
    } else if (node?.value)! > searchValue {
        return search(node?.leftChild, searchValue)
    } else {
        return search(node?.rightChild, searchValue)
    }
}

结果

我们分别调用

search(inieRootNode, 5)
search(inieRootNode, 6)
search(inieRootNode, 11)
search(inieRootNode, 0)

可以观察到playground右侧面板中，函数的递归执行次数:
5->2次、6->1次、11->2次、0->3次。

分析

我们知道二叉树搜索的效率是log(n)。 可以通过在上述二叉搜索树的中序列表中搜索来比较。

// efficiency  
let list = [5, 6, 7, 9, 10, 11]
let index0 = list.index(where: {$0 == 0})
let index5 = list.index(where: {$0 == 5})
let index6 = list.index(where: {$0 == 6})
let index11 = list.index(where: {$0 == 11})

可以在右侧面板中看到对于不存在的元素，二叉搜索树需要搜索三次，而for循环则需要7次。对于元素11，二叉搜索树需要搜索2次，for循环依然需要11次。

本文除了帮助理解二叉搜索树，它的效率之外，还需要了解swift可选值的解析～