二叉搜索树（BST）

public class BinarySearchTree<T: Comparable> {
  private(set) public var value: T
  private(set) public var parent: BinarySearchTree?
  private(set) public var left: BinarySearchTree?
  private(set) public var right: BinarySearchTree?

  public init(value: T) {
      self.value = value
  }

  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 hasLeftChild: Bool {
      return left != nil
  }

  public var hasRightChild: Bool {
      return right != nil
  }

  public var hasAnyChild: Bool {
      return hasLeftChild || hasRightChild
  }

  public var hasBothChildre: Bool {
      return hasLeftChild && hasRightChild
  }

  public var count: Int {
      return (left?.count ?? 0) + 1 + (right?.count ?? 0)
  }


  ///插入节点
  public func insert(value: T) {
    
      if value < self.value {
        
          ///如果存在左节点
          if let left = left {
              left.insert(value: value)
          } else {
              left = BinarySearchTree(value: value)
              left?.parent = self
          }
      } else {
        
          ///如果存在右节点
          if let right = right {
              right.insert(value: value)
          } else {
              right = BinarySearchTree(value: value)
              right?.parent = self
          }
      }
  }


  ///查找
  public func search(value: T) -> BinarySearchTree? {
      if value < self.value {
         return left?.search(value: value)
      } else if value > self.value {
          return right?.search(value: value)
      } else {
          return self
      }
  }




  ///中序遍历
  public func traverseInOrder(process: (T)-> Void) {
      left?.traverseInOrder(process: process)
      process(value)
      right?.traverseInOrder(process: process)
  }


  ///前序遍历
  public func traversePreOrder(process: (T)-> Void) {
      process(value)
      left?.traversePreOrder(process: process)
      right?.traversePreOrder(process: process)
  }

  ///后序遍历
  public func traversePostOrder(process: (T)-> Void) {
      left?.traversePostOrder(process: process)
      right?.traversePostOrder(process: process)
      process(value)
  }


  ///映射函数
  public func map(formula: (T) -> T) -> [T] {
      var a = [T]()
      if let left = left {
          a += left.map(formula: formula)
      }
    
      a.append(formula(value))
    
      if let right = right {
          a += right.map(formula: formula)
      }
    
      return a
  }


  ///BST 转化数组
  public func toArray() -> [T] {
      return map { $0 }
  }


  ///删除节点  Note:删除节点很简单， 删除节点后，把当前的节点替换为它的左子树最大的节点或者又子树最小的节点。这样数在删除后还会保持原来的顺序。

  /*获取最大节点*/
public func maxinode() -> BinarySearchTree {
    var node = self
    while let next = node.right {
        node = next
    }
    return node
}


/*获取最小节点*/
public func mininode() -> BinarySearchTree {
    var node = self
    while let next = node.left {
        node = next
    }
    return node
}


/*重连父节点*/
public func reconnectParentTo(node: BinarySearchTree?) {
    if let parent = parent {
        if isLeftChild {
            parent.left = node
        } else {
            parent.right = node
        }
    }
    node?.parent = parent
}

@discardableResult
public func remove() -> BinarySearchTree? {
    let replacement: BinarySearchTree?
    
    ///当前节点的代替者要么是左边的最大值， 要么是右边的最小值，
    if let right = right {
        replacement = right.maxinode()
    } else if let left = left {
        replacement = left.mininode()
    } else {
        replacement = nil
    }
    
    ///删除要替换节点自己的关联
    replacement?.remove()
    
    ///把要替代的节点移到当前节点位置
    replacement?.right = right
    replacement?.left = left
    left?.parent = replacement
    right?.parent = replacement
    
    
    ///重连父节点
    reconnectParentTo(node: replacement)
    
    ///当前节点不在是树的一部分，因此可以清理删除了
    parent = nil
    left = nil
    right = nil
    
    return replacement
}



///某一节点的高度是它到最低叶子节点的距离。
public func height() -> Int {
    if isLeaf {
        return 0
    } else {
        return 1 + max(left?.height() ?? 0, right?.height() ?? 0)
    }
}


///某一节点的深度是指该节点到根节点的距离
public func depth() -> Int {
    var node = self
    var count = 0
    while let parent = node.parent {
        node = parent
        count += 1
    }
    return count
}


}