一、概述
二叉樹的結構一般是以二叉鏈表的形式來存儲的。二叉鏈表的結構類似于雙向鏈表，二叉鏈表的節點也是有兩個結點指針的，一個指向左子樹，一個指向右子樹。二叉樹主要有四種遍歷方式：先序遍歷、中序遍歷、后序遍歷、層次遍歷。關于二叉樹的內容網上有很多，這里不再做過多的陳述。
本文將用Swift去實現二叉樹的創建、四種遍歷方式等。下面的實現部分內容參考了青玉伏案和唐巧兩位大神相關的文章。
二、實現思路及代碼
以下面二叉樹為例：
先序遍歷：先遍歷根節點然后再遍歷左子樹，最后遍歷右子樹。
故上面先序遍歷的順序為： A B D E C F
不過為了看到更詳細的步驟可以把上面 C 結點的左子節點的 value 值打印為#號，類似的D、E、F也一樣，他們的左右子節點的 value 值都打印為#號，則打印結果為：A B D # # E # # C # F # #
中序遍歷：先遍歷左子樹，然后遍歷根節點，最后遍歷右子樹。
故上面先序遍歷的順序為：# D # B # E # A # C # F #
后序遍歷：后序遍歷是先遍歷左子樹，然后再遍歷右子樹，最后遍歷根節點
故上面先序遍歷的順序為：# # D # # E B # # # F C A
層次遍歷：層次遍歷相對上面的幾個遍歷實現起來要稍微復雜，層次遍歷就是圖中以二叉樹的根節點為起始節點的廣度搜索（BFS）
故上面先序遍歷的順序為：A B C D E # F # # # # # #
下面為上述幾種遍歷的Swift實現：
class BinaryTreeNote{
var value:String
var leftChild:BinaryTreeNote?
var rightChild:BinaryTreeNote?
init(_ value:String) {
self.value = value
}
}
class BinaryTreeHelper{
var array:[String]
var index = -1
init(_ array:[String]) {
self.array = array
}
//創建二叉樹
func createTree() -> BinaryTreeNote? {
self.index = self.index + 1
if index < self.array.count && index >= 0 {
let value = self.array[index]
if value == "" {
return nil
} else {
let note = BinaryTreeNote(value)
note.leftChild = createTree()
note.rightChild = createTree()
return note
}
}
return nil;
}
//先序遍歷二叉樹
func preOrderTraverse(_ note:BinaryTreeNote?){
if note == nil {
print("#")
return
}
print(note!.value)
preOrderTraverse(note!.leftChild)
preOrderTraverse(note!.rightChild)
}
//中序遍歷二叉樹
func inOrderTraverse (_ note: BinaryTreeNote?) {
if note == nil {
print("#")
return
}
inOrderTraverse(note!.leftChild)
print(note!.value)
inOrderTraverse(note!.rightChild)
}
//后序遍歷二叉樹
func afterOrderTraverse (_ note: BinaryTreeNote?) {
if note == nil {
print("#")
return
}
afterOrderTraverse(note!.leftChild)
afterOrderTraverse(note!.rightChild)
print(note!.value)
}
//層次遍歷二叉樹
func levelOrder(_ root: BinaryTreeNote?){
var result = [[BinaryTreeNote]]()
var level = [BinaryTreeNote]()
level.append(root!)
while level.count != 0 {
result.append(level)
var nextLevel = [BinaryTreeNote]()
for node in level {
if let leftNode = node.leftChild {
nextLevel.append(leftNode)
}
if let rightNode = node.rightChild {
nextLevel.append(rightNode)
}
}
level = nextLevel
}
let ans = result.map { $0.map { $0.value }}
print(ans)
}
}總結
以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者使用swift能帶來一定的幫助，如果有疑問大家可以留言交流，謝謝大家對html5模板網的支持。
【網站聲明】本站部分內容來源于互聯網,旨在幫助大家更快的解決問題，如果有圖片或者內容侵犯了您的權益，請聯系我們刪除處理，感謝您的支持！