Binary Search Tree example

binarytree.swift

//Tree
class Tree {
    var root: Node?
    public func addValue(_ val: Int) {
        let newNode = Node(value: val)
        if self.root == nil {
            print("root value is \(val)")
            self.root = newNode
        }else{
            root?.addNode(newNode)
        }
    }
    
    public func traverse(_ traversalType: DFStraversal) {
        switch traversalType {
        case .InOrder:
            print("Traveral In-Order:")
            root?.InOrderVisit()
        case .PreOrder:
            print("Traveral Pre-Order:")
            root?.PreOrderVisit()
        case .PostOrder:
            print("Traveral Post-Order:")
            root?.PostOrderVisit()
        default:
          print("Nothing")
        }
    }
    
    public enum DFStraversal {
        case InOrder,PreOrder,PostOrder
    }
}
//nodes
class Node {
    var value: Int
    var leftChild: Node?
    var rightChild: Node?
    
    init(value: Int) {
        self.value = value
    }
    
    public func addNode(_ n: Node) {
        
        if n.value < self.value {
            if self.leftChild == nil {
                self.leftChild = n
            }else{
                self.leftChild?.addNode(n)
            }
            
        }else if (n.value > self.value){
            
            if self.rightChild == nil {
                self.rightChild = n
                
            }else{
                self.rightChild?.addNode(n)
            }
            
        }
    }
    
    public func InOrderVisit(){
        if self.leftChild != nil {
            self.leftChild?.InOrderVisit()
        }
        print(self.value)
        if self.rightChild != nil {
            self.rightChild?.InOrderVisit()
        }
        
    }
    public func PreOrderVisit(){
        print(self.value)
        if self.leftChild != nil {
            self.leftChild?.PreOrderVisit()
        }
        if self.rightChild != nil {
            self.rightChild?.PreOrderVisit()
        }

    }
    public func PostOrderVisit(){
        if self.leftChild != nil {
            self.leftChild?.PostOrderVisit()
        }
        if self.rightChild != nil {
            self.rightChild?.PostOrderVisit()
        }
        print(self.value)
    }
    
}

//return tree's height, if no node return -1
func BFS(_ SourceTree:Tree) -> Int {
    var q = Queue<Node>()
    var Level = -1
    if SourceTree.root == nil {
        return Level
    }else{
        //level 0
        q.enqueue(SourceTree.root!)
       
        while (!q.isEmpty){
            let n = q.dequeue()
            print("n: \(n!.value)")
            
            
            if n?.leftChild != nil {
                q.enqueue(n!.leftChild!)
            }
            
            if n?.rightChild != nil {
                q.enqueue(n!.rightChild!)
            }
            //count height
            if n?.leftChild != nil || n?.rightChild != nil {
                Level += 1
            }
            
        }
        
    }
    
    return Level
    
}
private struct Queue<T> {
    private var array: [T]
    
    public init() { array = [] }
    public var isEmpty: Bool {
        return array.isEmpty
    }
    
    public mutating func enqueue(_ element: T) {
        array.append(element)
    }
    
    public mutating func dequeue() -> T? {
        if isEmpty { return nil }else{
            return array.removeFirst()
        }
    }
}
//******** Create Tree *******
let newTree = Tree()
//Use random to add nodes if you want
//for _ in 0...10 {
//    let randomNum:UInt32 = arc4random_uniform(100)
//    newTree.addValue(Int(randomNum))
//}

newTree.addValue(12)
newTree.addValue(81)
newTree.addValue(24)
newTree.addValue(27)
newTree.addValue(59)
newTree.addValue(37)
newTree.addValue(71)
newTree.addValue(33)
newTree.addValue(38)

//Traverse tree
newTree.traverse(.InOrder)
newTree.traverse(.PostOrder)
newTree.traverse(.PreOrder)

//BFS search, return tree's height
BFS(newTree)