swift创建查找二叉树

class TreeNode{
    var val : Int
    var left : TreeNode?
    var right : TreeNode?
    init(_ val : Int) {
        self.val = val
        right = nil
        left = nil
    }
}
class BTree {
    fileprivate var root : TreeNode?
    /// 是否为查找二叉树
    func isSearchBTree(_ node : TreeNode? , min : Int? , max :Int?) -> Bool {
        guard let node = node else{
            return true
        }
        if let min = min , node.val < min{
            return false
        }
        
        if let max = max , node.val > max{
            return false
        }
        
        return isSearchBTree(node.left , min: min , max: node.val) && isSearchBTree(node.right , min: node.val , max: max)
    }
    /// 树的深度
    func bTreeDepth(_ node : TreeNode?) -> Int{
        guard let node = node else{
            return 0
        }
        return max(bTreeDepth(node.left), bTreeDepth(node.right)) + 1
    }
    
    
    func addNode(_ val : Int) {
        if root == nil{
            root = TreeNode(val)
            return
        }
        var lastNode : TreeNode? = root
        var preNode : TreeNode?  = root
        while lastNode != nil{
            if val <= lastNode!.val {
                //遍历左节点
                preNode = lastNode
                lastNode = lastNode!.left
            }else{
                preNode = lastNode
                lastNode = lastNode!.right
            }
        }
        if val <= preNode!.val{
            preNode?.left = TreeNode(val)
        }else{
            preNode?.right = TreeNode(val)
        }
    }
    /// 先根遍历
    func preOrder() -> [Int]{
        var arr = [Int]()
        preOrderHelper(self.root, &arr)
        return arr
    }
    private func preOrderHelper(_ node : TreeNode?, _ arr : inout [Int]){
        if let node = node{
            arr.append(node.val)
            preOrderHelper(node.left, &arr)
            preOrderHelper(node.right, &arr)
        }
    }
    /// 中根遍历
    func inOrder() -> [Int]{
        var arr = [Int]()
        inOrderHelper(self.root,&arr)
        return arr
    }
    func inOrderHelper(_ node : TreeNode?, _ arr : inout [Int]) {
        if let node = node{
            inOrderHelper(node.left, &arr)
            arr.append(node.val)
            inOrderHelper(node.right, &arr)
        }
    }
    /// 后根遍历
    func postOrder() -> [Int]{
        var arr = [Int]()
        postOrderHelper(self.root,&arr)
        return arr
    }
    func postOrderHelper(_ node : TreeNode?, _ arr : inout [Int]) {
        if let node = node{
            postOrderHelper(node.left, &arr)
            postOrderHelper(node.right, &arr)
            arr.append(node.val)
        }
    }
    /// 栈的前根遍历
    func preOrderByStack() -> [Int]{
        var res = [Int]()
        var stacks = [TreeNode]()
        var node = self.root
        while stacks.count != 0 || node != nil {
            if node != nil{
                res.append(node!.val)
                stacks.append(node!)
                node =  node!.left
            }else{
                node = stacks.removeLast().right
            }
        }
        return res
    }
    /// 栈的中根遍历
    func inOrderByStack() -> [Int]{
        var res = [Int]()
        var stacks = [TreeNode]()
        var node = self.root
        while stacks.count != 0 || node != nil {
            if node != nil{
                stacks.append(node!)
                node =  node!.left
            }else{
                node = stacks.removeLast()
                res.append(node!.val)
                node = node?.right
                
            }
        }
        return res
    }
    /// 栈的后根遍历
    func postOrderByStack() -> [Int]{
        var res = [Int]()
        var stacks = [TreeNode]()
        var tagStacks = [Int]()
        var node = root
        while stacks.count > 0 || node != nil {
            while node != nil {
                tagStacks.append(0)
                //入栈
                stacks.append(node!)
                node = node?.left
            }
            while tagStacks.last == 1 {
                tagStacks.removeLast()
                res.append(stacks.removeLast().val)
            }
            if node == nil && tagStacks.count > 0{
                //出栈
                tagStacks.removeLast()
                tagStacks.append(1)
                node = stacks.last
                node = node?.right
            }
        }
        return res
    }
    /// 层次遍历
    func levelOrder() -> [[Int]] {
        var res = [[Int]]()
        var queue = [TreeNode]()
        if let node = root{
            queue.append(node)
        }
        while queue.count > 0 {
            var level = [Int]()
            for _ in 0..<queue.count{
                let node = queue.removeFirst()
                level.append(node.val)
                if let node = node.left{
                    queue.append(node)
                }
                if let node = node.right{
                    queue.append(node)
                }
            }
            res.append(level)
        }
        return res
    }
}

        let arr = [13,4,13,17,8,11,9,0,12,3]
        let bt = BTree()
        for item in arr {
            bt.addNode(item)
        }
        print("---先根遍历---")
        print(bt.preOrder())
        print("---中根遍历---")
        print(bt.inOrder())
        print("---后根遍历---")
        print(bt.postOrder())
        print("---树的层数---")
        print(bt.bTreeDepth(bt.root))
        print("--栈的先根遍历---")
        print(bt.preOrderByStack())
        print("--栈的中根遍历---")
        print(bt.inOrderByStack())
        print("--栈的后根遍历---")
        print(bt.postOrderByStack())
        print("---是否为查找二叉树---")
        print(bt.isSearchBTree(bt.root, min: nil, max: nil))
        print("---层次遍历二叉树---")
        print(bt.levelOrder())

结果:

---先根遍历---
[13, 4, 0, 3, 13, 8, 11, 9, 12, 17]
---中根遍历---
[0, 3, 4, 8, 9, 11, 12, 13, 13, 17]
---后根遍历---
[3, 0, 9, 12, 11, 8, 13, 4, 17, 13]
---树的层数---
6
--栈的先根遍历---
[13, 4, 0, 3, 13, 8, 11, 9, 12, 17]
--栈的中根遍历---
[0, 3, 4, 8, 9, 11, 12, 13, 13, 17]
--栈的后根遍历---
[3, 0, 9, 12, 11, 8, 13, 4, 17, 13]
---是否为查找二叉树---
true
---层次遍历二叉树---
[[13], [4, 17], [0, 13], [3, 8], [11], [9, 12]]

创建查找二叉树.jpeg