學(xué)習(xí)了二叉樹(shù)的概念及二叉樹(shù)算法習(xí)題后， 結(jié)合學(xué)習(xí)的知識(shí)通過(guò)代碼實(shí)現(xiàn)一些功能。

二叉樹(shù)說(shuō)白了是考驗(yàn)程序員的遞歸思維拢驾，通過(guò)自己調(diào)用自己來(lái)實(shí)現(xiàn)功能，廢話不多說(shuō)上代碼改基。

創(chuàng)建二叉樹(shù)類

創(chuàng)建BinaryTreeNode類繁疤，并分別創(chuàng)建value、leftNode秕狰、rightNode屬性嵌洼，導(dǎo)入數(shù)組創(chuàng)建二叉樹(shù)

class BinaryTreeNode: NSObject {
   // 值
   var value:Int = 0
   // 左節(jié)點(diǎn)
   var leftNode:BinaryTreeNode?
   // 右節(jié)點(diǎn)
   var rightNode:BinaryTreeNode?
   
   /// 創(chuàng)建二叉樹(shù)排序樹(shù)節(jié)點(diǎn)
   /// 左節(jié)點(diǎn)值全部小于根節(jié)點(diǎn)，右節(jié)點(diǎn)值全部大于根節(jié)點(diǎn)
   ///
   /// - Parameter values: 數(shù)組
   /// - Returns: 二叉樹(shù)根節(jié)點(diǎn)
   class func creatTree(values: [Int]) -> BinaryTreeNode {
        var root:BinaryTreeNode?
        for i in 0..<values.count {
            let value = values[i]
            root = BinaryTreeNode.addTreeNode(treeNode: root, value: value)
        }
        return root!
    }
    
   /// 向二叉排序樹(shù)添加一個(gè)節(jié)點(diǎn)
   ///
   /// - Parameters:
   ///   - treeNode: 根節(jié)點(diǎn)
   ///   - value: 值
   /// - Returns: 根節(jié)點(diǎn)
   private class func addTreeNode(treeNode: BinaryTreeNode?, value:Int) -> BinaryTreeNode? {
        var treeNode = treeNode
        if treeNode == nil {
            treeNode = BinaryTreeNode()
            treeNode?.value = value
            print("node: \(value)")
        } else if value <= treeNode!.value {
            print("to left")
            // 值小于根節(jié)點(diǎn)
            treeNode?.leftNode = BinaryTreeNode.addTreeNode(treeNode: treeNode?.leftNode, value: value)
        } else {
            print("to right")
            // 值大于根節(jié)點(diǎn)
            treeNode?.rightNode = BinaryTreeNode.addTreeNode(treeNode: treeNode?.rightNode, value: value)
        }
        return treeNode
   }
}      

在合適的地方調(diào)用方法創(chuàng)建二叉樹(shù)封恰，筆者為了清晰的看到樹(shù)的結(jié)構(gòu)麻养，通過(guò)笨方法打印了每層子節(jié)點(diǎn)：

let array = [1, 2, 10, 8, 3, 4, 5, 6, 7, 9]
let tree = BinaryTreeNode.creatTree(values: array)

print("<===============> 1層")
print(tree.value)

print("<===============> 2層")
print(tree.leftNode?.value)
print(tree.rightNode?.value)

print("<===============> 3層")
print(tree.rightNode?.leftNode?.value)
print(tree.rightNode?.rightNode?.value)

print("<===============> 4層")
print(tree.rightNode?.rightNode?.leftNode?.value)
print(tree.rightNode?.rightNode?.rightNode?.value)

print("<===============> 5層")
print(tree.rightNode?.rightNode?.leftNode?.leftNode?.value)
print(tree.rightNode?.rightNode?.leftNode?.rightNode?.value)

print("<===============> 6層")
print(tree.rightNode?.rightNode?.leftNode?.leftNode?.leftNode?.value)
print(tree.rightNode?.rightNode?.leftNode?.leftNode?.rightNode?.value)
print(tree.rightNode?.rightNode?.leftNode?.rightNode?.leftNode?.value)
print(tree.rightNode?.rightNode?.leftNode?.rightNode?.rightNode?.value)

print("<===============> 7層")
print(tree.rightNode?.rightNode?.leftNode?.leftNode?.rightNode?.leftNode?.value)
print(tree.rightNode?.rightNode?.leftNode?.leftNode?.rightNode?.rightNode?.value)

print("<===============> 8層")
print(tree.rightNode?.rightNode?.leftNode?.leftNode?.rightNode?.rightNode?.leftNode?.value)
print(tree.rightNode?.rightNode?.leftNode?.leftNode?.rightNode?.rightNode?.rightNode?.value)

print("<===============> 9層")
print(tree.rightNode?.rightNode?.leftNode?.leftNode?.rightNode?.rightNode?.rightNode?.leftNode?.value)
print(tree.rightNode?.rightNode?.leftNode?.leftNode?.rightNode?.rightNode?.rightNode?.rightNode?.value)

打印結(jié)果
<===============> 1層
1
<===============> 2層
nil
Optional(2)
<===============> 3層
nil
Optional(10)
<===============> 4層
Optional(8)
nil
<===============> 5層
Optional(3)
Optional(9)
<===============> 6層
nil
Optional(4)
nil
nil
<===============> 7層
nil
Optional(5)
<===============> 8層
nil
Optional(6)
<===============> 9層
nil
Optional(7)

獲取二叉樹(shù)的深度(層數(shù))

/// 二叉樹(shù)的深度
///
/// - Parameter rootNode: 二叉樹(shù)根節(jié)點(diǎn)
/// - Returns: 二叉樹(shù)的深度
class func depthOfTree(rootNode: BinaryTreeNode?) -> Int {
    if rootNode == nil {
        return 0
    }
    if rootNode?.leftNode == nil && rootNode?.rightNode == nil {
        return 1
    }
    
    // 左子樹(shù)深度
    let leftDepth = depthOfTree(rootNode: rootNode?.leftNode)
    // 右子樹(shù)深度
    let rightDepth = depthOfTree(rootNode: rootNode?.rightNode)
    
    return max(leftDepth, rightDepth) + 1
}

在合適的地方調(diào)用：

print("二叉樹(shù)深度\(BinaryTreeNode.depthOfTree(rootNode: tree))")
打印結(jié)果：
二叉樹(shù)深度9

按層遍歷

/// 二叉樹(shù)中某個(gè)位置的節(jié)點(diǎn)（按層次遍歷）
///
/// - Parameters:
///   - index: 按層次遍歷的位置
///   - rootNode: 根節(jié)點(diǎn)
/// - Returns: tree
class func treeNodeAtIndex(index: Int, rootNode: BinaryTreeNode?) -> BinaryTreeNode? {
    var index = index
    if index == 0 && rootNode == nil {
        return nil
    }
    // 數(shù)組當(dāng)成隊(duì)列
    var queueArray = [BinaryTreeNode?]()
    // 壓入根節(jié)點(diǎn)
    queueArray.append(rootNode!)
    while queueArray.count > 0 {
        let node = queueArray.first as? BinaryTreeNode
        if index == 0 {
            return node
        }
        // 彈出最前面的節(jié)點(diǎn)，返照隊(duì)列先進(jìn)先出的原則
        queueArray.remove(at: 0)
        // 節(jié)點(diǎn)移除诺舔，index減少
        index -= 1
        if node?.leftNode != nil {
            queueArray.append(node?.leftNode)
        }
        if node?.rightNode != nil {
            queueArray.append(node?.rightNode)
        }
    }
    return nil
}

在合適的地方調(diào)用：

let indexNode = BinaryTreeNode.treeNodeAtIndex(index: 2, rootNode: tree)
print(indexNode?.value)

打印結(jié)果：
Optional(10)

前鳖昌、中、后遍歷

/// 前序遍歷
/// 先訪問(wèn)根低飒，再遍歷左子樹(shù)许昨，再遍歷右子樹(shù)，典型的遞歸思想
/// - Parameters:
///   - rootNode: 樹(shù)
///   - handler: 回調(diào)數(shù)值
class func preOrderTraverseTree(rootNode: BinaryTreeNode? ,handler:@escaping (BinaryTreeNode) -> Void) {
    if rootNode != nil {
        handler(rootNode!)
        BinaryTreeNode.preOrderTraverseTree(rootNode: rootNode?.leftNode, handler: handler)
        BinaryTreeNode.preOrderTraverseTree(rootNode: rootNode?.rightNode, handler: handler)
    }
}

/// 中序遍歷
/// 先遍歷左子樹(shù)褥赊，再訪問(wèn)根糕档，再遍歷右子樹(shù)
/// - Parameters:
///   - rootNode: 樹(shù)
///   - handler: 回調(diào)數(shù)值
class func inOrderTreverseTree(rootNode: BinaryTreeNode? ,handler:@escaping (BinaryTreeNode) -> Void) {
    if rootNode != nil {
        BinaryTreeNode.preOrderTraverseTree(rootNode: rootNode?.leftNode, handler: handler)
        handler(rootNode!)
        BinaryTreeNode.preOrderTraverseTree(rootNode: rootNode?.rightNode, handler: handler)
    }
}

/// 后序遍歷
/// 先遍歷左子樹(shù)，再遍歷右子樹(shù)拌喉，在訪問(wèn)根
/// - Parameters:
///   - rootNode: 樹(shù)
///   - handler: 回調(diào)數(shù)值
class func postOrderTreverseTree(rootNode: BinaryTreeNode? ,handler:@escaping (BinaryTreeNode) -> Void) {
    if rootNode != nil {
        BinaryTreeNode.preOrderTraverseTree(rootNode: rootNode?.leftNode, handler: handler)
        BinaryTreeNode.preOrderTraverseTree(rootNode: rootNode?.rightNode, handler: handler)
        handler(rootNode!)
    }
}

在合適的地方調(diào)用：

// 前序遍歷
var dataArr1 = [Int]()
BinaryTreeNode.preOrderTraverseTree(rootNode: tree) { (treeNode) in
    dataArr1.append(treeNode.value)
}
print(dataArr1)


// 中序遍歷
var dataArr2 = [Int]()
BinaryTreeNode.inOrderTreverseTree(rootNode: tree) { (treeNode) in
    dataArr2.append(treeNode.value)
}
print(dataArr2)

// 后序遍歷
var dataArr3 = [Int]()
BinaryTreeNode.postOrderTreverseTree(rootNode: tree) { (treeNode) in
    dataArr3.append(treeNode.value)
}
print(dataArr3)

打印結(jié)果：
// 前序遍歷
[1, 2, 10, 8, 3, 4, 5, 6, 7, 9]
// 中序遍歷
[1, 2, 10, 8, 3, 4, 5, 6, 7, 9]
// 后續(xù)遍歷
[2, 10, 8, 3, 4, 5, 6, 7, 9, 1]

持續(xù)更新中~