二叉树说白了是考验程序员的递归思维，通过自己调用自己来实现功能，废话不多说上代码。
创建二叉树类
创建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]
持续更新中~
