二叉搜索树

2019-05-25  本文已影响0人  MoneyRobber

对于二叉树中的每一个节点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

上一篇 下一篇

猜你喜欢

热点阅读