二叉树 for iOS (Swift篇)

学习了二叉树的概念及二叉树算法习题后， 结合学习的知识通过代码实现一些功能。

二叉树说白了是考验程序员的递归思维，通过自己调用自己来实现功能，废话不多说上代码。

创建二叉树类

创建BinaryTreeNode类，并分别创建value、leftNode、rightNode属性，导入数组创建二叉树

class BinaryTreeNode: NSObject {
   // 值
   var value:Int = 0
   // 左节点
   var leftNode:BinaryTreeNode?
   // 右节点
   var rightNode:BinaryTreeNode?
   
   /// 创建二叉树排序树节点
   /// 左节点值全部小于根节点，右节点值全部大于根节点
   ///
   /// - Parameter values: 数组
   /// - Returns: 二叉树根节点
   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!
    }
    
   /// 向二叉排序树添加一个节点
   ///
   /// - Parameters:
   ///   - treeNode: 根节点
   ///   - value: 值
   /// - Returns: 根节点
   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")
            // 值小于根节点
            treeNode?.leftNode = BinaryTreeNode.addTreeNode(treeNode: treeNode?.leftNode, value: value)
        } else {
            print("to right")
            // 值大于根节点
            treeNode?.rightNode = BinaryTreeNode.addTreeNode(treeNode: treeNode?.rightNode, value: value)
        }
        return treeNode
   }
}

在合适的地方调用方法创建二叉树，笔者为了清晰的看到树的结构，通过笨方法打印了每层子节点：

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)

打印结果
<===============> 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)

获取二叉树的深度(层数)

/// 二叉树的深度
///
/// - Parameter rootNode: 二叉树根节点
/// - Returns: 二叉树的深度
class func depthOfTree(rootNode: BinaryTreeNode?) -> Int {
    if rootNode == nil {
        return 0
    }
    if rootNode?.leftNode == nil && rootNode?.rightNode == nil {
        return 1
    }
    
    // 左子树深度
    let leftDepth = depthOfTree(rootNode: rootNode?.leftNode)
    // 右子树深度
    let rightDepth = depthOfTree(rootNode: rootNode?.rightNode)
    
    return max(leftDepth, rightDepth) + 1
}

在合适的地方调用：

print("二叉树深度\(BinaryTreeNode.depthOfTree(rootNode: tree))")
打印结果：
二叉树深度9

按层遍历

/// 二叉树中某个位置的节点（按层次遍历）
///
/// - Parameters:
///   - index: 按层次遍历的位置
///   - rootNode: 根节点
/// - Returns: tree
class func treeNodeAtIndex(index: Int, rootNode: BinaryTreeNode?) -> BinaryTreeNode? {
    var index = index
    if index == 0 && rootNode == nil {
        return nil
    }
    // 数组当成队列
    var queueArray = [BinaryTreeNode?]()
    // 压入根节点
    queueArray.append(rootNode!)
    while queueArray.count > 0 {
        let node = queueArray.first as? BinaryTreeNode
        if index == 0 {
            return node
        }
        // 弹出最前面的节点，返照队列先进先出的原则
        queueArray.remove(at: 0)
        // 节点移除，index减少
        index -= 1
        if node?.leftNode != nil {
            queueArray.append(node?.leftNode)
        }
        if node?.rightNode != nil {
            queueArray.append(node?.rightNode)
        }
    }
    return nil
}

在合适的地方调用：

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

打印结果：
Optional(10)

前、中、后遍历

/// 前序遍历
/// 先访问根，再遍历左子树，再遍历右子树，典型的递归思想
/// - Parameters:
///   - rootNode: 树
///   - handler: 回调数值
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)
    }
}

/// 中序遍历
/// 先遍历左子树，再访问根，再遍历右子树
/// - Parameters:
///   - rootNode: 树
///   - handler: 回调数值
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)
    }
}

/// 后序遍历
/// 先遍历左子树，再遍历右子树，在访问根
/// - Parameters:
///   - rootNode: 树
///   - handler: 回调数值
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!)
    }
}

在合适的地方调用：

// 前序遍历
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)

打印结果：
// 前序遍历
[1, 2, 10, 8, 3, 4, 5, 6, 7, 9]
// 中序遍历
[1, 2, 10, 8, 3, 4, 5, 6, 7, 9]
// 后续遍历
[2, 10, 8, 3, 4, 5, 6, 7, 9, 1]

持续更新中~

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

相关阅读更多精彩内容

  • 疯狂java笔记之树和二叉树
    树的概述 树是一种非常常用的数据结构，树与前面介绍的线性表，栈，队列等线性结构不同，树是一种非线性结构 1.树的定...
    Jack921阅读 4,879评论 1赞 31
  • 数据结构-二叉树的存储结构与遍历
    定义 一个有穷的结点集合，可以为空。若不为空，则它是由根结点和称为其左子树和右子树的两个互不相交的二叉树组成。 二...
    IAM四十二阅读 2,736评论 0赞 2
  • 二叉树知识点回忆以及整理
    二叉树 在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”，左子树和右子...
    静默加载阅读 2,313评论 0赞 3
  • 二叉树-你可能需要知道这些
    一直以来，我都很少使用也避免使用到树和图,总觉得它们神秘而又复杂，但是树在一些运算和查找中也不可避免的要使用到，那...
    24K男阅读 6,891评论 5赞 14
  • 工作在一个有点偏的的地方
    九月这是个过分凉爽的九月，可气的，一号到现在了感冒还没好。每每同事劝说吃药的时候，总会以“是药三分毒啊”这样的“真...
    Youhoo丶阅读 285评论 0赞 0

友情链接更多精彩内容