singly-linked-list-and-bin-search-tree.swift

import UIKit

import Foundation

class LinkedList<T: CustomStringConvertible> {
    
    var head: Node<T>? = nil
    
    class Node<T> {
        var value: T
        var next: Node<T>?
        
        init(value: T) {
            self.value = value
        }
    }
    

    
    // 空かどうか判定
    var isEmpty: Bool {
        return head == nil
    }
    
    public var first: Node<T>? {
        return head
    }
    
    // 末尾へ追加
    public func append(_ element: T) {
        guard var ptr = head else {
            head = Node<T>(value: element)
            return
        }
        while let next = ptr.next {
            ptr = next
        }
        ptr.next = Node<T>(value: element)
    }
    
    public func remvove(_ index: Int) throws {
        if index < 0 || index > count() {
            throw NSError(domain: "out of range", code: -1, userInfo: nil)
        }
        if index == 0 {
            head = head?.next
        } else {
            var ptr = head
            for _ in 0..<index-1 {
                ptr = ptr?.next
            }
            ptr?.next = ptr?.next?.next
        }
    }
    
    public func get(at index: Int) -> Node<T>? {
        var cnt = 0
        var ptr = head
        while let next = ptr?.next, cnt < index {
            cnt += 1
            ptr = next
        }
        return ptr
    }
    
    
    public func insert(index: Int, element: T) throws {
        let node = Node<T>(value: element)
        if index < 0 || index > count() {
            throw NSError(domain: "out of range", code: -1, userInfo: nil)
        }
        
        if index == 0 {
            node.next = head
            head = node
        } else {
            var ptr = head
            for _ in 0..<index-1 {
                ptr = ptr?.next
            }
            node.next = ptr?.next
            ptr?.next = node
        }
    }
    
    // 要素数をカウント
    func count() -> Int {
        var cnt = 0
        var ptr = head
        while ptr != nil {
            cnt += 1
            ptr = ptr?.next
        }
        return cnt
    }
}

extension LinkedList: CustomStringConvertible {
    var description: String {
        var str = "["
        var ptr = head
        while ptr != nil {
            str += "\(ptr!.value.description)"
            ptr = ptr?.next
            if ptr != nil {
                str += ", "
            }
        }
        return str + "]"
    }
}

let list = LinkedList<Int>()
for i in 0..<10 {
    list.append(i)
}
//list.remvove(1)
list
list.get(at: 4)?.value
try! list.remvove(1)
list



class BinarySearchTree<T: Comparable & CustomStringConvertible> {
    var value: T
    var left: BinarySearchTree? = nil
    var right: BinarySearchTree? = nil
    var parent: BinarySearchTree? = nil
    
    init(_ v: T) {
        value = v
    }
    
    func add(_ v: T) {
        if v < self.value {
            if let left = left {
                left.add(v)
            } else {
                left = BinarySearchTree(v)
                left?.parent = self
            }
        } else {
            if let right = right {
                right.add(v)
            } else {
                right = BinarySearchTree(v)
                right?.parent = self
            }
        }
    }
    
    func preOrderPrint() {
        print(value.description)
        if let left = left {
            left.preOrderPrint()
        }
        if let right = right {
            right.preOrderPrint()
        }
    }
    
    func inOrderPrint() {
        if let left = left {
            left.inOrderPrint()
        }
        print(value.description)
        if let right = right {
            right.inOrderPrint()
        }
    }

    func postOrderPrint() {
        if let left = left {
            left.postOrderPrint()
        }
        if let right = right {
            right.postOrderPrint()
        }
        print(value.description)
    }
    
    func search(v: T) -> Bool {
        if v == value {
            return true
        } else if v < value {
            if let left = left {
                return left.search(v: v)
            } else {
                return false
            }
        } else {
            if let right = right {
                return right.search(v: v)
            } else {
                return false
            }

        }
    }
    
    func max() -> BinarySearchTree {
        if let right = right {
            return right.max()
        } else {
            return self
        }
    }
    
    func min() -> BinarySearchTree {
        if let left = left {
            return left.min()
        } else {
            return self
        }
    }
    
    func remove(v: T) {
        if v == value {
            if let left = left, let right = right { // branch
                let leftMax = left.max()
                self.value = leftMax.value
                leftMax.remove(v: leftMax.value)
            } else if let left = left, right == nil { // only left
                self.value = left.value
                self.left = left.left
                self.right = left.right
            } else if let right = right, left == nil { // only right
                self.value = right.value
                self.right = right.right
                self.left = right.left
            } else { // leaf
                self.parent = nil // 接続を切る
            }
        } else if v < value {
            left?.remove(v: v)
        } else {
            right?.remove(v: v)
        }
    }
}

let bst = BinarySearchTree(4)
bst.add(1)
bst.add(6)
bst.add(5)
bst.add(10)
bst.add(2)
bst.add(2)


bst.search(v: 2)
bst.inOrderPrint()
print("")
bst.remove(v: 2)
print("")
bst.inOrderPrint()

BinarySearchTreeはenumでやるべき