class BinarySearchTree
     
       {    private(set) var value:T    private(set) var parent:BinarySearchTree?    private(set) var leftChild:BinarySearchTree?    private(set) var rightChild:BinarySearchTree?        public init(value: T) {        self.value = value    }        public convenience init(array: [T]) {        // 将数组的第一个值赋给root，数组其他的值直接插入到binarySearchTree中                // precondition use as assert        precondition(array.count > 0)        self.init(value: array.first!)                // array.dropFirst()        // A subsequence starting after the first element of the sequence.        for value in array.dropFirst() {            insert(value: value)        }    }        public var isRoot: Bool {        return parent == nil    }        public var isLeftChild: Bool {        return parent?.leftChild === self    }        public var isRightChild: Bool {        return parent?.rightChild === self    }        public var isChild: Bool {        return isLeftChild || isRightChild    }        public var hasLeftChild: Bool {        return leftChild != nil    }        public var hasRightChild: Bool {        return rightChild != nil    }        public var isLeaf: Bool {        return (leftChild == nil) && (rightChild == nil)    }        public var hasAnyChild: Bool {        return hasLeftChild || hasRightChild    }        public var count: Int {        return (leftChild?.count ?? 0) + 1 + (rightChild?.count ?? 0)    }        public func insert(value: T) {        if value == self.value {            return        }                if value < self.value {            if let left = self.leftChild {                left.insert(value: value)            } else {                self.leftChild = BinarySearchTree(value: value)                self.leftChild?.parent = self            }        } else {            if let right = self.rightChild {                right.insert(value: value)            } else {                self.rightChild = BinarySearchTree(value: value)                self.rightChild?.parent = self            }        }    }        public func search(value: T) -> BinarySearchTree? {        if value < self.value {            return self.leftChild?.search(value: value)        } else if value > self.value {            return self.rightChild?.search(value: value)        } else {            return self        }    }        public func traverseInOrder(process: (T) -> Void) {        leftChild?.traverseInOrder(process: process)        process(value)        rightChild?.traverseInOrder(process: process)    }        public func traversePreOrder(process: (T) -> Void) {        process(value)        leftChild?.traversePreOrder(process: process)        rightChild?.traversePreOrder(process: process)    }        public func traversePostOrder(process: (T) -> Void) {        leftChild?.traversePostOrder(process: process)        rightChild?.traversePostOrder(process: process)        process(value)    }        public func minValue() -> BinarySearchTree {        var node = self                while let next = node.leftChild {            node = next        }                return node    }        public func maxValue() -> BinarySearchTree {        var node = self                while let next = node.rightChild {            node = next        }                return node    }        // height高度是当前节点到叶子结点的最大距离    public func height() -> Int {        if isLeaf {            return 0        } else {            return 1 + max(self.leftChild?.height() ?? 0, self.rightChild?.height() ?? 0 )        }    }        // depth 深度是当前到根结点的距离    public func depth() -> Int {        var node  = self        var edges = 0        while let parent = node.parent {            node = parent            edges += 1        }                return edges    }        // precede the current value in sorted order    public func predecessor() -> BinarySearchTree
      
       ? {        if let left = self.leftChild {            return left.maxValue()        } else {            var node = self            while let parent = node.parent {                if node.isRightChild {                    return parent                } else {                    node = parent                }            }        }        return nil    }        public func successor() -> BinarySearchTree
       
        ? {        if let right = self.rightChild {            return right.minValue()        } else {            var node = self            while let parent = node.parent {                if node.isLeftChild {                    return parent                } else {                    node = parent                }            }        }                return nil    }
       
      
     

 　　//判断插入一个值后当前是否还是BST

    public func isBST(min:T, max:T) -> Bool {

        if value < min || value > max {

            return false

        }

        let leftBST = self.leftChild?.isBST(min: min, max: value) ?? true

        let rightBST = self.rightChild?.isBST(min: value, max: max) ?? true

        

        return leftBST && rightBST

    }

private func reconnectParentToNode(node: BinarySearchTree?) {        if let parent = self.parent {            if isLeftChild {                parent.leftChild = node            } else {                parent.rightChild = node            }        }                node?.parent = self.parent    }}extension BinarySearchTree:CustomStringConvertible {    var description: String {        var text = "\(value): {
    "                if leftChild != nil {            text += "{ left: " + (leftChild?.description)! + "}"        }        if rightChild != nil {            text += "{ right: " + (rightChild?.description)! + "}"        }                text += "}"                return text    }}

测试：

let bst = BinarySearchTree
     
      (value: 5)bst.insert(value: 3)bst.insert(value: 8)bst.insert(value: 1)bst.insert(value: 9)bst.insert(value: 4)print(bst)let bstTwo = BinarySearchTree
      
       (array: [5, 3, 8, 1, 9, 4])print(bstTwo)bstTwo.search(value: 1)bstTwo.search(value: 6)print("PreOrder")bstTwo.traversePreOrder{value in print(value)}print("InOrder")bstTwo.traverseInOrder{value in print(value)}print("PostOrder")bstTwo.traversePostOrder{value in print(value)}bstTwo.minValue()bstTwo.maxValue()bstTwo.height()bstTwo.search(value: 9)?.depth()bstTwo.search(value: 8)?.predecessor()bstTwo.search(value: 4)?.successor()
      
     

bstTwo.search(value: 4)?.insert(value: 10)

bstTwo.isBST(min: Int.min, max: Int.max)  // false