?
用數(shù)組來存儲(chǔ)二叉樹如何遍歷的呢？
如果父節(jié)點(diǎn)的數(shù)組下表是i，那么它的左孩子就是i * 2 + 1，右孩子就是 i * 2 + 2。
?二叉樹的遍歷方式：
二叉樹有三種基本遍歷方式，分別是前序遍歷、中序遍歷和后序遍歷。遍歷的原理是從根節(jié)點(diǎn)開始，按照特定方式遞歸遍歷左子樹和右子樹，每次對(duì)訪問到的節(jié)點(diǎn)進(jìn)行操作。
- 前序遍歷：先訪問根節(jié)點(diǎn)再訪問左子樹，最后訪問右子樹。
- 中序遍歷：先訪問左子樹再訪問根節(jié)點(diǎn)，最后訪問右子樹。
- 后序遍歷：先訪問左子樹再訪問右子樹，最后訪問根節(jié)點(diǎn)
這里前中后，其實(shí)指的就是中間節(jié)點(diǎn)的遍歷順序，只要記住 前中后序指的就是中間節(jié)點(diǎn)的位置就可以了
看如下中間節(jié)點(diǎn)的順序，就可以發(fā)現(xiàn)，中間節(jié)點(diǎn)的順序就是所謂的遍歷方式
- 前序遍歷：中左右
- 中序遍歷：左中右
- 后序遍歷：左右中
前序遍歷
對(duì)每顆子樹，均遵循根節(jié)點(diǎn)–>左節(jié)點(diǎn)–>右節(jié)點(diǎn)
遞歸前序
func preShowTree(head *Node) {
if head == nil {
return
}
fmt.Println(head.V)//第一次來到節(jié)點(diǎn)的時(shí)候打印
showTree(head.Left)
showTree(head.Right)
}
中序遍歷
中序:對(duì)每顆子樹，均遵循左節(jié)點(diǎn)–>根節(jié)點(diǎn)–>右節(jié)點(diǎn)
遞歸中序
func midShowTree(head *Node) {
if head == nil {
return
}
showTree(head.Left)
fmt.Println(head.V)//第二次來到節(jié)點(diǎn)的時(shí)候打印
showTree(head.Right)
}
后序遍歷
后序:對(duì)每顆子樹，均遵循左節(jié)點(diǎn)–>右節(jié)點(diǎn)–>根節(jié)點(diǎn)
遞歸后序文章來源：http://www.zghlxwxcb.cn/news/detail-413995.html
func afterShowTree(head *Node) {
if head == nil {
return
}
showTree(head.Left)
showTree(head.Right)
fmt.Println(head.V)//第三次來到節(jié)點(diǎn)的時(shí)候打印
}
參考：二叉樹入門知識(shí)——一篇了解二叉樹_我永遠(yuǎn)信仰的博客-CSDN博客文章來源地址http://www.zghlxwxcb.cn/news/detail-413995.html
到了這里，關(guān)于go數(shù)據(jù)結(jié)構(gòu)(二叉樹的遍歷)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
