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