Go 數據結構和算法篇（十六）：二叉樹的遍歷
二叉樹的遍歷指的是從根節(jié)點出發(fā)，按照某種次序依次訪問二叉樹中的所有節(jié)點，使得每個節(jié)點被訪問一次且僅被訪問一次。
有多種方式可以遍歷二叉樹，如果按照從左到右的習慣方式，主要分為三種：前序遍歷、中序遍歷和后序遍歷。下面我們簡單介紹這幾種遍歷方式及對應實現算法，所謂的前序、中序和后序都是以根節(jié)點作為參照系。
一、前序遍歷
從根節(jié)點開始，先遍歷左子樹，再遍歷右子樹（對于子樹的子樹，依此類推），如果二叉樹為空，則返回空：
顯然，我們可以通過遞歸來實現二叉樹的前序遍歷邏輯，對應的 Go 實現代碼如下：
package main
import (
"fmt"
)
// Node 通過鏈表存儲二叉樹節(jié)點信息
type Node struct {
Data interface{}
Left *Node
Right *Node
}
func NewNode(data interface{}) *Node {
return &Node{
Data: data,
Left: nil,
Right: nil,
}
}
func (node *Node) GetData() string {
return fmt.Sprintf("%v", node.Data)
}
// 前序遍歷
func preOrderTraverse(treeNode *Node) {
// 節(jié)點為空則退出當前遞歸
if treeNode == nil {
return
}
// 否則先打印當前節(jié)點值
fmt.Printf("%s ", treeNode.GetData())
// 然后對左子樹和右子樹做前序遍歷
preOrderTraverse(treeNode.Left)
preOrderTraverse(treeNode.Right)
}
// 測試代碼
func main() {
// 初始化一個簡單的二叉樹
node1 := NewNode(0) // 根節(jié)點
node2 := NewNode("1")
node3 := NewNode(2.0)
node1.Left = node2
node1.Right = node3
// 前序遍歷這個二叉樹
fmt.Print("前序遍歷: ")
preOrderTraverse(node1)
fmt.Println()
}
這里，我們使用了鏈表結構來存儲二叉樹，并且通過 interface{} 空接口類型聲明二叉樹節(jié)點支持存儲任意類型數據。
執(zhí)行上述代碼，打印結果如下：
二、中序遍歷
中序遍歷會從左子樹最左側的節(jié)點開始，然后從左到右依次遍歷左子樹，根節(jié)點，最后是右子樹（依然是從最左側節(jié)點開始從左到右的順序遍歷），如果二叉樹為空，則返回空：
我們在上面的示例代碼中添加中序遍歷實現代碼：
package main
import (
"fmt"
)
...
// 中序遍歷
func midOrderTraverse(treeNode *Node) {
// 節(jié)點為空則退出當前遞歸
if treeNode == nil {
return
}
// 否則先從左子樹最左側節(jié)點開始遍歷
midOrderTraverse(treeNode.Left)
// 打印位于中間的根節(jié)點
fmt.Printf("%s ", treeNode.GetData())
// 最后按照和左子樹一樣的邏輯遍歷右子樹
midOrderTraverse(treeNode.Right)
}
func main() {
...
// 中序遍歷這個二叉樹
fmt.Print("中序遍歷: ")
midOrderTraverse(node1)
fmt.Println()
}
執(zhí)行上述代碼，打印結果如下：
三、后序遍歷
最后來看后序遍歷，后序遍歷也是從左子樹最左側的節(jié)點開始，不過會從左到右先遍歷完葉子節(jié)點，再遍歷父節(jié)點，遍歷完左子樹后，直接從右子樹最左側節(jié)點開始，按照和左子樹同樣的順序遍歷完右子樹，最后訪問根節(jié)點：
有了前面的基礎，編寫后序遍歷實現代碼就相當輕松了：
package main
import (
"fmt"
)
...
// 后序遍歷
func postOrderTraverse(treeNode *Node) {
// 節(jié)點為空則退出當前遞歸
if treeNode == nil {
return
}
// 否則先遍歷左子樹
postOrderTraverse(treeNode.Left)
// 再遍歷右子樹
postOrderTraverse(treeNode.Right)
// 最后訪問根節(jié)點
fmt.Printf("%s ", treeNode.GetData())
}
func main() {
...
// 后序遍歷這個二叉樹
fmt.Print("后序遍歷: ")
postOrderTraverse(node1)
fmt.Println()
}
執(zhí)行上述代碼，打印結果如下：
可以看到，不同的遍歷方式從不同維度將二叉樹這種非線性的結構變成了某種意義上的線性序列，從而方便計算機操作。
感興趣的同學還可以通過并發(fā)模式來編排二叉樹的上述遍歷行為。
（本文完）
推薦閱讀
評論
圖片
表情