定義二叉樹模型

class Tree {
    var value = 0
    var left: Tree?
    var right: Tree?
    
    var isVist = false
}

創(chuàng)建二叉樹：

let tree = createTree(0, 6)!

func createTree(_ index: Int, _ total: Int ) -> Tree? {
    if index >= total {
        return nil
    }
    let node = Tree.init()
    node.value = index + 1
    node.left = createTree(2 * index + 1, total)
    node.right = createTree(2 * index + 2, total)
    return node
}

創(chuàng)建的二叉樹如下：

二叉樹

這個(gè)二叉樹的遍歷分別為：

• 先序遍歷: 124536
• 中序遍歷：425163
• 后序遍歷：452631

遞歸實(shí)現(xiàn)

前序遍歷：

func firstRoot(_ tree: Tree?) {
    guard let t = tree else {
        return
    }
    print(t.value, terminator: "")
    firstRoot(t.left)
    firstRoot(t.right)
}

中序遍歷：

func midRoot(_ tree: Tree?) {
    guard let t = tree else {
        return
    }
    midRoot(t.left)
    print(t.value, terminator: "")
    midRoot(t.right)
}

后序遍歷:

func lastRoot(_ tree: Tree?) {
    guard let t = tree else {
        return
    }
    lastRoot(t.left)
    lastRoot(t.right)
    print(t.value, terminator: "")
}

非遞歸遍歷實(shí)現(xiàn)

首先绽慈，寫一個(gè)棧：

struct Stack<T> {
    var items = [T]()
    mutating func push(_ item: T) {
        items.append(item)
    }
    
    mutating func pop() -> T? {
        return items.popLast()
    }
    
    var isEmpty: Bool {
        items.isEmpty
    }
}

前序遍歷：

func normalFirstRoot(_ tree: Tree?) {
    var tree = tree
    var stack = Stack<Tree>.init()
    while tree != nil || !stack.isEmpty  {
        if tree != nil {
            print(tree!.value, terminator: "")
            stack.push(tree!)
            tree = tree?.left
        } else {
            tree = stack.pop()
            tree = tree?.right
        }
    }
}

中序遍歷：

func normalMidRoot(_ tree: Tree?) {
    var tree = tree
    var stack = Stack<Tree>.init()
    while tree != nil || !stack.isEmpty {
        if tree != nil {
            stack.push(tree!)
            tree = tree?.left
        } else {
            tree = stack.pop()
            if tree != nil {
                print(tree!.value, terminator: "")
            }
            tree = tree?.right
        }
    }
}

后序遍歷：
后序遍歷的非遞歸實(shí)現(xiàn)算是相對(duì)較難的一種遍歷了，需要用到節(jié)點(diǎn)的isVist屬性泳唠，實(shí)現(xiàn)如下：

func normalLastRoot(_ tree: Tree?) {
    var tree = tree
    var stack = Stack<Tree>.init()
    while tree != nil || !stack.isEmpty {
        if tree != nil {
            if tree!.left?.isVist == true, tree?.right?.isVist == true {
                if tree != nil {
                    print(tree!.value, terminator: "")
                }
                tree = stack.pop()
            } else if tree?.left?.isVist == true {
                stack.push(tree!)
                tree?.isVist = true
                tree = tree?.right
            } else {
                stack.push(tree!)
                tree?.isVist = true
                tree = tree?.left
            }
        } else {
            tree = stack.pop()
            if tree != nil {
                print(tree!.value, terminator: "")
            }
            tree = stack.pop()
        }
    }
}

附上二叉樹深度的遞歸與非遞歸算法：

二叉樹深度的遞歸算法：

func depth(_ tree: Tree?) -> Int {
    guard let t = tree else {
        return 0
    }
    let leftDepth = depth(t.left)
    let rightDepth = depth(t.right)
    let maxDepth = max(leftDepth, rightDepth) + 1
    return maxDepth
}

二叉樹深度的非遞歸算法：

func depth2(_ tree: Tree?) -> Int {
    guard let t = tree else {
        return 0
    }
    var d = 0
    var nodes = [Tree]()
    nodes.append(t)
    while(nodes.count > 0) {
        var subNodes = [Tree]()
        for (i, node) in nodes.enumerated() {
            if let left = node.left {
                subNodes.append(left)
            }
            if let right = node.right {
                subNodes.append(right)
            }
        }
        nodes.removeAll()
        nodes.append(contentsOf: subNodes)
        d += 1
    }
    return d
}