根据节点访问顺序的不同，常见的二叉树遍历方式有4种。
前序遍历（Preorder Traversal）
树状结构打印
- 先访问根节点，前序遍历左子树，前序遍历右子树
func PreorderTraversal(){
self .PreorderTraversalNote(note: root)
}
func PreorderTraversalNote(note:Note?){
// 打印当前值
print(note?.value ?? "")
// 先遍历左子树
if let leftNote = note?.leftNote {
PreorderTraversalNote(note: leftNote)
}
// 再遍历右子树
if let rightNote = note?.rightNote {
PreorderTraversalNote(note: rightNote)
}
// 无子树，中止调用
}
中序遍历（Inorder Traversal）
根节点在中间，左右子树的先后顺序可变
二叉搜索树按序处理节点
-
中序遍历左子树，根节点，中序遍历右子树（二叉搜索树的访问结果为从小到大）
-
中序遍历右子树，根节点，中序遍历左子树（二叉搜索树的访问结果为从大到小）
func InorderTraversal(){
InorderTraversalNote(note: root)
}
func InorderTraversalNote(note:Note?){
// 先遍历左子树
if let leftNote = note?.leftNote {
InorderTraversalNote(note: leftNote)
}
// 打印当前值
print(note?.value ?? "")
// 再遍历右子树
if let rightNote = note?.rightNote {
InorderTraversalNote(note: rightNote)
}
// 无子树，中止调用
}
后序遍历（Postorder Traversal）
根节点在最后
先子后父的操作
- 后序遍历左子树，后序遍历右子树，根节点
层序遍历（Level Order Traversal）
从上到下，从左到右，一层一层访问
计算二叉树高度、判断一棵树是否为完全二叉树
func LevelOrderTraversal(){
// 通过队列来实现，按层入队，节点出队，对应的子节点入队
let queue = NSMutableArray.init()
var tempNote:Note
queue.add(root!)
// 遍历，如果下一层还有元素，那就继续遍历
while(queue.count > 0){
tempNote = queue.firstObject as! BinarySearchTree.Note
print(tempNote.value)
// 打印出首个，入队它的子树
queue.removeObject(at: 0)
if let leftNote = tempNote.leftNote {
queue.add(leftNote)
}
if let rightNote = tempNote.rightNote {
queue.add(rightNote)
}
}
}
树的高度
// 通过递归获取树的高度
func recursionGetHeight()->Int {
return recursionGetHeightWithNote(note: root)
}
func recursionGetHeightWithNote(note:Note?)->Int{
if(note == nil){
return 0
}
// 当前节点的高度为最大子节点高度 + 1
return 1 + max(recursionGetHeightWithNote(note: note?.leftNote), recursionGetHeightWithNote(note: note?.rightNote))
}
// 通过层序遍历的方式获取树的高度
func height()->Int{
guard root != nil else { return 0 }
// 通过队列的方式来层序遍历
let queue = NSMutableArray.init()
queue.add(root!)
// 当前层数，因为以根节点开始，层数默认为1
var height = 1
// 当层节点个数
var levelOrderElement = 1
while(queue.count > 0){
// 移除第一个节点，将子节点添加
let note:Note = queue.firstObject as! Note
// 层序遍历
queue.removeObject(at: 0)
// 当前层数节点数 - 1
levelOrderElement -= 1
if let leftNote = note.leftNote {
queue.add(leftNote)
}
if let rightNote = note.rightNote {
queue.add(rightNote)
}
if(levelOrderElement == 0 && queue.count > 0){
// 当前层数节点遍历结束，并且还有下一层节点需要遍历
height += 1
// 此时队列中的节点数为下一层节点总数
levelOrderElement = queue.count
}
}
return height
}
判断是否为完全二叉树
层序遍历，确定每个节点都满足完全二叉树的特点
/// 判断是否为完全二叉树
/// - Returns: <#description#>
func isCompleteTree()->Bool{
// 空树非完全二叉树
guard root != nil else { return false }
// 通过队列的方式来层序遍历
let queue = NSMutableArray.init()
queue.add(root!)
/*
当左右子节点不为空，那么继续层序遍历
当左子节点不为空，右子节点为空，那么后面的所有节点都是叶子节点①
当左子节点为空，右子节点也为空，那么后面所有节点都是叶子节点①
当左子节点为空，右子节点不为空，直接返回失败②
*/
var allLastLeafNote = false// 后面的节点是否都是叶子节点
while(queue.count > 0){
// 移除第一个节点，将子节点添加
let note:Note = queue.firstObject as! Note
var leftNull = true// 为空
var rightNull = true
// 层序遍历
queue.removeObject(at: 0)
if let leftNote = note.leftNote {
if(allLastLeafNote == true){
return false // ①后面的节点应该都是叶子节点，但出现了子节点
}
queue.add(leftNote)
leftNull = false
}
if let rightNote = note.rightNote {
if(allLastLeafNote == true){
return false // ①后面的节点应该都是叶子节点，但出现了子节点
}
queue.add(rightNote)
rightNull = false
}
if(leftNull == true && rightNull == false){
return false // ②无左子节点，但是有右子节点
}else if(leftNull == true && rightNull == true){
allLastLeafNote = true//无左右子节点，后面都是叶子节点
}else if(leftNull == false && rightNull == true){
allLastLeafNote = true//有左子节点无右子节点，后面都是叶子节点
}
}
return true// 顺利遍历结束，全部满足条件
}
翻转二叉树
所有节点的左右子树交换，关键在于遍历到左右的子节点，且不要重复遍历，所以任何一种遍历方式都可以实现。
网友评论