群组
Flutter,iOS,Android,Python等,闲聊工作&技术&问题;
个人主页:https://waitwalker.cn
telegram群链接:https://t.me/joinchat/Ej0o0A1ntlq5ZFIMzzO5Pw
二叉树的定义
二叉树(Binary Tree)是一棵树,其中每个节点都不能有多余两个的儿子.深度为k的二叉树的节点个数,最多为2^k - 1个节点.ni节点深度指的是从根r到ni的一条有效路径的长.深度为k的二叉树的深度指的是从根r到叶子节点一条最长路径的长.这条路径上最多节点个数也就是深度为k的二叉树的节点个数.
二叉树每个节点最多有两个儿子,我们可以用指针直接指向他们,左边的儿子称为左子树,右边的儿子称为右子树.
二叉树的声明有点类似于链表,一个节点有关键字信息加上两个指向其他节点的指针(Left和Right)组成的结构.因此,对于链表的一些操作逻辑也能应用于二叉树上,比如插入操作,需要先创建一个插入的节点,然后插入.
与普通树不同,普通树的节点个数至少为1,二叉树的节点个数可以为0;普通树节点的最大分支度没有限制,而二叉树节点的最大分支度为2;普通树的节点无左右次序之分,而二叉树节点有左右次序之分.
一颗深度为k,具有2^(k + 1) - 1个节点的二叉树称为满二叉树,也称为完全二叉树(Complete Binary Tree).具有n个节点的完全二叉树的深度为log2n + 1.
二叉树的存储
二叉树可以用数组或链表来存储,如果二叉树是完全二叉树则能紧密排列起来而不造成空间浪费.如果某个节点的索引为i,则它的左子树节点索引为2i+1,右子树节点索引为2i+2.而它的父亲节点索引为|(i - 1) / 2|.
使用数组来存储二叉树节点有利于紧密存储和更好的访问的局部性,然而如果一颗二叉树每个节点只有左二子或者只有右儿子将造成很大的空间浪费.
二叉树使用二叉链表来存储一定程度上能避免空间连续存储造成的浪费,但是由于缺乏父指针,在查找父亲节点的时候需要重新扫描树.
因此,二叉树通常用树节点结构来存储.
二叉树的遍历
深度优先遍历:
二叉树的深度遍历方法分为先序遍历,中序遍历,后序遍历,L,D,R分别表示左子树,根节点(父亲节点),右子树.
先序遍历:
访问节点的顺序是DLR,先根,然后左子树,然后右子树.访问根节点,然后左子树,接着访问左子树,直到最左子树,然后访问左子树对应的右子树,然后递归实现以上步骤.
中序遍历:
访问节点的顺序是LDR,先左子树,然后根,然后右子树.先最左子树,然后根节点(父亲节点),然后最左子树对应右子树的最左子树,然后根节点,右子树.
后序遍历:
访问节点的顺序是LRD,先左子树,然后右子树,然后根.先最左子树,然后右子树的最左子树,右子树,根.
广度优先遍历:
广度优先遍历会先访问离根节点最近的节点,二叉树的广度优先遍历又称为按层次遍历,这个算法实现要借助于队列来实现.
二叉树的实现
二叉树的定义实现
// MARK: - 二叉树的定义
class BinaryTree<T> {
// 节点value
var value:T
// 左子树
var leftChildNode:BinaryTree?
// 右子树
var rightChildNode:BinaryTree?
// MARK: - 构造方法
init(value:T) {
self.value = value
}
}
先序遍历递归实现
/// 先序遍历:先根节点,然后左子树,然后右子树
///
/// - Parameter binaryTree: 二叉树节点
/// - Returns: 二叉树节点总数
func traversePreOrder(binaryTree:BinaryTree?) -> Int {
guard let binaryTreeNode = binaryTree else {
return 0
}
print("当前节点值:",binaryTreeNode.value,separator: "",terminator: " \n")
let leftNodeCount = binaryTreeNode.traversePreOrder(binaryTree: binaryTreeNode.leftChildNode)
let rigthNodeCount = binaryTreeNode.traversePreOrder(binaryTree: binaryTreeNode.rightChildNode)
return leftNodeCount + rigthNodeCount + 1
}
中序遍历递归实现
/// 中序遍历 先左子树,然后根,然后右子树
///
/// - Parameter binaryTree: 二叉树节点
func traverseInOrder(binaryTree:BinaryTree?) -> Int {
guard let binaryTreeNode = binaryTree else { return 0}
let leftNodeCount = binaryTreeNode.traverseInOrder(binaryTree: binaryTreeNode.leftChildNode)
print("当前节点值:",binaryTreeNode.value,separator: "",terminator: " \n")
let rigthNodeCount = binaryTreeNode.traverseInOrder(binaryTree: binaryTreeNode.rightChildNode)
return leftNodeCount + rigthNodeCount + 1
}
后序遍历递归实现
/// 后序遍历 先左子树,然后右子树,然后根
///
/// - Parameter binaryTree: 二叉树节点
func traversePostOrder(binaryTree:BinaryTree?) -> Int {
guard let binaryTreeNode = binaryTree else { return 0 }
let leftNodeCount = binaryTreeNode.traversePostOrder(binaryTree: binaryTreeNode.leftChildNode)
let rigthNodeCount = binaryTreeNode.traversePostOrder(binaryTree: binaryTreeNode.rightChildNode)
print("当前节点值:",binaryTreeNode.value,separator: "",terminator: " \n")
return leftNodeCount + rigthNodeCount + 1
}
二叉树最大深度
/// 二叉树最大深度
///
/// - Parameter binaryTree: 二叉树节点
/// - Returns: 最大深度
func maxDepth(binaryTree:BinaryTree?) -> Int {
guard let binaryTreeNode = binaryTree else { return 0 }
let leftMaxDepth = maxDepth(binaryTree: binaryTreeNode.leftChildNode)
let rightMaxDepth = maxDepth(binaryTree: binaryTreeNode.rightChildNode)
return max(leftMaxDepth, rightMaxDepth) + 1
}
二叉树最小深度
/// 二叉树最小深度
///
/// - Parameter binaryTree: 二叉树节点
/// - Returns: 最小深度
func minDepth(binaryTree:BinaryTree?) -> Int {
guard let binaryTreeNode = binaryTree else { return 0 }
let leftMinDepth = binaryTreeNode.minDepth(binaryTree: binaryTreeNode.leftChildNode)
let rightMinDepth = binaryTreeNode.minDepth(binaryTree: binaryTreeNode.rightChildNode)
return min(leftMinDepth, rightMinDepth) + 1
}
先序遍历非递归实现
/***
先根,然后左子树,然后右子树 非递归实现:
1)用栈来存储当前节点,判断当前节点是否为空,不为空,将当前节点压栈操作.
2)判断当前节点的左子树是否为空,左子树不为空则将当前节点的左子树赋值给当前节点;若为空,则取出栈的元素,将栈顶元素的右子树赋值给当前节点,执行1)
3)直到当前节点为空并且栈为空,遍历结束
**/
/// 先序遍历
///
/// - Parameter binaryTree: 二叉树节点
/// - Returns: 二叉树节点总数
func traversePreOrderNonrecursive(binaryTree:BinaryTree?) -> Int {
var treeStack:[BinaryTree] = []
var currentNode = binaryTree
var count:Int = 0
while !treeStack.isEmpty || currentNode != nil{
if currentNode != nil {
treeStack.append(currentNode!)
currentNode = currentNode?.leftChildNode
count += 1
print(currentNode?.value as Any)
} else {
let lastTreeNode = treeStack.removeLast()
currentNode = lastTreeNode.rightChildNode
}
}
return count
}
源码地址
这里的实现代码已放到GitHub),测试用例详见DataStructureAlgorithmTests.swift文件
参考文献
《数据结构与算法分析C语言描述》(Data Structures and Algorithm Analysis in C:Second Edition)–译者: 冯舜玺
