二叉搜索树

对于二叉树中的每一个节点X，它的左子树中所有节点的关键字的值小于X关键字的值，它的右子树所有节点的关键字的值大于X关键字的值

public class Node {
    public var left: Node?
    public var right: Node?
    public var val: Int?
    public init(_ val: Int) {
        self.left = nil
        self.right = nil
    }
}

find

func find(x:Int,node:Node?) -> Node? {
    if x == node!.val || node == nil {
        return node
    }
    if x < node!.val! {
        return find(x: x, node: node!.left)
    } else {
        return find(x: x, node: node!.right)
    }
}

insert

func insert(x:Int,node:Node?) -> Void {
    if x == node!.val {
        return
    }
    var tmp:Node?
    var nodeTmp = node
    while nodeTmp != nil {
        tmp = node
        if x < (node?.val)! {
            nodeTmp = node?.left
        } else {
            nodeTmp = node?.right
        }
    }
    
    if x > (tmp?.val)! {
        tmp?.right = Node(x)
    } else {
        tmp?.left = Node(x)
    }
}

delete

• 要删除的节点没有儿子，直接删除
• 要删除的节点只有一个儿子，删除该节点，该节点的子节点代替该节点之前的位置
• 要删除的节点有两个儿子，用该节点右子树里面最小的节点替换该节点，这样子该节点就被替换到底部去，成为上面两种情况中的一种，用上面的策略删除它即可