5.二叉搜索树

Binary Search Tree

特征：任意一个节点的值，大于左子树所有节点的值，小于右子树所有节点的值。这个值必须可以被比较。

/*
几个重要的属性：
节点个数、根节点
节点：左节点、右节点、父节点、值
add：判断是否有根节点->寻找到合适的子叶（确定子叶方向，且该方向上无节点）
*/
class BinarySearchTree {
    /// 节点个数
    var size:Int = 0
    /// 根节点
    var root:Note?
    
    func add(element:Int){
        // 判断根节点，如果没有根节点，那么生成根节点
        guard let note = root else {
            size += 1;
            // 如果没有根节点，那么生成根节点
            root = Note.init(parent: nil, value: element)
            return
        }
        var nextNote:Note? = note
        var tempNote:Note? = note
        while(tempNote != nil){
            nextNote = tempNote;
            // 如果已经有根节点了，那么根据比较方法，寻找合适的叶子节点
            let result = compareTwoElement(num1: tempNote!.value, num2: element)
            if(result == 1){
                // 当前节点值比新值大，放左子树
                tempNote = tempNote!.leftNote
            }else if(result == 2){
                // 当前节点值比新值小，放右子树
                tempNote = tempNote!.rightNote
            }else {
                // 相等，说明已经有值相同的节点，这里做忽略处理
                return
            }
        }
        // 循环结束，tempNote == nil 此时nextNote就是合适的叶子节点
        let result = compareTwoElement(num1: nextNote!.value, num2: element)
        let newNote = Note.init(parent: nextNote, value: element)
        if(result == 1){
            // 当前节点值比新值大，放左子节点
            size += 1;
            nextNote!.leftNote = newNote
        }else if(result == 2){
            // 当前节点值比新值小，放右子节点
            size += 1;
            nextNote!.rightNote = newNote
        }else {
            // 相等，说明已经有值相同的节点，这里做忽略处理
            return
        }
    }
    
    func compareTwoElement(num1:Int,num2:Int)->Int{
        if(num1 > num2){
            return 1
        }else if(num1 < num2){
            return 2
        }
        return 0
    }
    
    class Note {
        var leftNote:Note?
        var rightNote:Note?
        var parent:Note?
        
        var value:Int
        
        init(parent:Note?,value:Int) {
            self.parent = parent
            self.value = value
        }
    }
}