二叉搜索树/BST

首先想沉重宣布一件事，因为我的信用卡在未收到通知的情况下被东亚注销了，导致我无法给 Digital Ocean 上的服务器续费，因此之前在老博客上的大量文章全都取不回来(ಥ_ಥ)……而由于我一时半会儿不想重办信用卡，所以可能要放弃迁移原来的博文了。

不过不要紧，虽然博文不见了，但是代码还在，脑子也基本还在╮(╯_╰)╭ 所以这些内容我还是会慢慢重新精炼po出来。

今天放一个之前没写过的，但算是二叉树这块内容的一个经典+精华内容——二叉搜索树。

概述

定义

二叉搜索树是一种常用的保持所有元素都有序的二叉树。

它是一个二叉树，每一个节点至多有两个子节点；
在每一个节点，所有左子树的节点值都小于/大于父节点，所有右子树的节点值都大于/小于父节点。

设计

BST 与 TreeNode 设计

如果我们认为树中的节点是一个独立的类型，那么诸如：

节点值;
子节点和父节点的引用;
和节点相关的所有操作；

都应该封装在这个独立的类型里。对于 BST 来说，它只保存一个属性，就是表示树根的 TreeNode 。

我们也可以淡化 TreeNode 的存在，把访问一个节点就理解为是直接访问由这个节点和它的子节点构成的BST。这样，关于节点值、子节点和父节点的信息，都直接保存在BST对象里。只是这样，我们就没有一个明确的“树根”概念了。当我们创建一个新BST时，新创建的对象就是“树根”。

插入操作

在 BST 中插入元素只要记住一点就好：我们一定能在所有的叶子节点中，给要插入的元素找到一个位置。插入操作永远不会发生在中间节点。

打印操作

自定义的打印效果：

每个叶子节点用小括号包围；
每个包含子树的节点用中括号包围；
每个非叶子子树用大括号包围；
左右箭头表示 left 和 right 。

过程

1. printNode(node: node!.left)之前：

打印每一个 BST 的起始情况。当节点为空时，直接返回，否则，我们就新建一个用于保存输出内容的字符串，如果当前节点不是 root 和 leaf ，就输出一个 { 到结果，表示开始输出一个新的子树；

2. printNode(node: node!.left) - printNode(node: node!.right)

从宏观上看，就是先打印一个节点的左子树部分，再打印节点本身，再打印节点的右子树部分。

而从微观看，整个过程一定会“下探”到某个叶子节点才真正开始执行输出。由于叶子节点没有左子树，所以直接输出了叶子节点本身，然后，这个叶子节点的右子树也为空，同样不需要做任何操作。这时，执行就返回到了叶子节点的父节点，输出这个父节点，然后，同理输出这个父节点的右子树部分。周而复始，整个 BST 就被输出成一个字符串了。

3. printNode(node: node!.right)之后：

每当输出完一个节点的右子树时（叶子和根节点除外），我们就可以输出一个 } 表示一个子树输出结束了。

遍历

包括 3 种遍历操作：前序，中序以及后序遍历，其区别就是在遍历过程中访问节点的顺序。

Preorder : 树根、左子树、右子树；
Inorder : 左子树、树根、右子树；
- 中序遍历结果即排序结果
- 代码请见我的 GitHub ：LeetCode 230. Kth Smallest Element in a BST
Postorder : 左子树、右子树、树根；

实现

完整代码可见我的 GitHub : BST ，下面是详细的实现介绍。

BST 与 TreeNode 定义

open class TreeNode<T: Comparable> {
    fileprivate var value: T
    fileprivate var parent: TreeNode?
    fileprivate var left: TreeNode?
    fileprivate var right: TreeNode?
}

open class BST<T: Comparable> {
    fileprivate(set) public var root: TreeNode<T>?
}

为了排序，放入 BST 的元素必须是可比较的；
在一个泛型类型内部使用类型自身时，可以省略掉泛型参数，表示它们的泛型参数类型和类对象是一样的；
在一个泛型类型内部使用其他类型时，不可以省略泛型参数；
在设计 TreeNode 和 BST 时，我们都希望它们之中的一些算法可以被更复杂的二叉树算法改写，因此，我们使用了 open 修饰这两个类型；
对于 TreeNode 的属性，我们希望只在定义它们的文件内被访问和修改，因此把它们定义为了 fileprivate 。而对于 BST ，我们通过 fileprivate(set) public 让 root 属性达到了只读的效果。

BST 与 TreeNode 创建/初始化

open class TreeNode<T: Comparable> {
    // Omitted..
    public init(value: T,
                parent: TreeNode? = nil,
                left: TreeNode? = nil,
                right: TreeNode? = nil) {
        self.value = value
        self.parent = parent
        self.left = left
        self.right = right
    }
    
open class BST<T: Comparable> {
    // Omitted...   
    public init(_ value: T) {
        self.root = TreeNode<T>(value: value)
    }
    
    public init(_ array: [T]) {
        precondition(array.count > 0)
        
        self.root = TreeNode<T>(value: array[0])
        
        for value in array[1 ..< array.count] {
            insert(value: value)
        }
    }

BST 初始化应该接受两种情况：

只有一个值；
通过数组初始化。

第 2 种情况涉及结点的插入，如上面所提，通过 extension 来增加一个辅助的 insert 方法。

结点插入

extension BST {
    fileprivate func insert(value: T, under parent: TreeNode<T>) {
        if value < parent.value {
            // If left child existed, continue to traverse
            if let left = parent.left {
                insert(value: value, under: left)
            }
            else {
                let node = TreeNode<T>(value: value)
                parent.left = node
                node.parent = parent
            }
        }
        else if value > parent.value {
            // If right child existed, continue to traverse

            if let right = parent.right {
                insert(value: value, under:right)
            }
            else {
                let node = TreeNode<T>(value: value)
                parent.right = node
                node.parent = parent
            }
        }
    }
}

记得还要在 BST 的定义中添加 insert 方法（相当于 API 接口，并且注意 extension 中的方法有 fileprivate 关键字）：

open func insert(value: T) {
   self.insert(value: value, under: self.root!)
}

打印

在 TreeNode 中添加判断用 Computed property

open class TreeNode<T: Comparable> {
    // Omitted...
    public var isRoot: Bool {
        return parent == nil
    }
    
    public var isLeaf: Bool {
        return left == nil && right == nil
    }
    
    public var isLeftChild: Bool {
        return parent?.left === self
    }
    
    public var isRightChild: Bool {
        return parent?.right === self
    }
    
    public var hasSingleLeftChild: Bool {
        return left != nil && right == nil
    }
    
    public var hasSingleRightChild: Bool {
        return left == nil && right != nil
    }
    
    public var hasAnyChild: Bool {
        return left != nil || right != nil
    }
    
    public var hasBothChild: Bool {
        return left != nil && right != nil
    }
}

注意 isLeftChild 和 isRightChild 中用 === 判断是否为同一对象。

在 extension 中添加输出字符串的辅助方法

extension BST {
    // Omitted...
    fileprivate func printNode(node: TreeNode<T>?) -> String {
        guard node != nil else {
            return ""
        }
        
        var sPrintResult = ""
        
        if !node!.isLeaf && !node!.isRoot {
            sPrintResult += "{"
        }
        
        sPrintResult += printNode(node: node!.left)
        
        let nodeValue = node!.value
        
        if node!.isLeaf {
            sPrintResult += "(\(nodeValue))"
        }
        else if node!.hasSingleLeftChild {
            sPrintResult += " <- [\(nodeValue)]"
        }
        else if node!.hasSingleRightChild {
            sPrintResult += "[\(nodeValue)] -> "
        }
        else if node!.hasBothChild {
            sPrintResult += " <- [\(nodeValue)] -> "
        }
        
        sPrintResult += printNode(node: node!.right)
        
        if !node!.isLeaf && !node!.isRoot {
            sPrintResult += "}"
        }
        
        return sPrintResult
    }
}

自定义输出

extension BST: CustomStringConvertible {
    open var description: String {
        return self.printNode(node: self.root)
    }
}

CustomStringConvertible 是一个 protocol ，实现它就可以直接调用 print 方法输出 BST 。

码趣