Hello章喉，各位小伙伴大家好，我是小棧君纤房，今天給大家?guī)淼姆窒硎顷P(guān)于關(guān)于二叉樹相關(guān)的知識點(diǎn)，并用go語言實(shí)現(xiàn)一個二叉樹和對二叉樹進(jìn)行遍歷歌馍。
我們主要針對二叉樹的概念篙悯，go實(shí)戰(zhàn)實(shí)現(xiàn)二叉樹的前序遍歷唐瀑、中序遍歷隆夯、后序遍歷觉增。
二叉樹概念
在計算機(jī)科學(xué)領(lǐng)域內(nèi)兵拢，二叉樹代表的是具有兩個節(jié)點(diǎn)的樹形結(jié)構(gòu)，通常子樹被稱作為“左子樹”逾礁，右邊的被稱作為“右子樹”。二叉樹通常的應(yīng)用于實(shí)現(xiàn)二叉查找樹和二叉堆访惜。
例如上述圖片中嘹履，我們就制定了一個二叉樹，其中d债热、e砾嫉、f稱作a樹的葉子節(jié)點(diǎn)。
[葉子結(jié)點(diǎn)是離散數(shù)學(xué)中的概念窒篱。一棵樹當(dāng)中沒有子結(jié)點(diǎn)（即度為0）的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)焕刮，簡稱“葉子”。 葉子是指出度為0的結(jié)點(diǎn)墙杯，又稱為終端結(jié)點(diǎn)]
b和c 作為樹a的孩子結(jié)點(diǎn)配并，b和a因?yàn)樽鳛橐粋€根a的孩子，所以他們的稱呼為兄弟結(jié)點(diǎn)高镐。其實(shí)總結(jié)一點(diǎn)就是關(guān)于二叉樹各個結(jié)點(diǎn)的稱呼其實(shí)和我們在家庭中溉旋，對于各個親戚長輩的稱呼類似。
在百度百科中也歸納除了關(guān)于二叉樹的分類
一棵深度為k嫉髓，且有2^k-1個結(jié)點(diǎn)的二叉樹观腊，稱為滿二叉樹。這種樹的特點(diǎn)是每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)算行。而在一棵二叉樹中梧油，除最后一層外，若其余層都是滿的州邢，并且或者最后一層是滿的儡陨，或者是在右邊缺少連續(xù)若干結(jié)點(diǎn)，則此二叉樹為完全二叉樹偷霉。
具有n個結(jié)點(diǎn)的完全二叉樹的深度為floor(log2n)+1迄委。深度為k的完全二叉樹，至少有2k-1個葉子結(jié)點(diǎn)类少，至多有2k-1個結(jié)點(diǎn)叙身。
所以通過我們上面的理論基礎(chǔ)，我們結(jié)合代碼來實(shí)現(xiàn)一下我們的二叉樹結(jié)構(gòu)硫狞。
如圖所示 信轿，我們定義了一個樹treeNode的結(jié)構(gòu)體晃痴，關(guān)于結(jié)構(gòu)體的分享，小棧君會在下一期對大家進(jìn)行分享财忽。對于go語言專題分享已經(jīng)過了差不多三分之一倘核，接下來我們會開啟新的分享之旅，還請各位持續(xù)關(guān)注“IT干貨椉幢耄”紧唱。
閑話不多說，我們在結(jié)構(gòu)體中定義了三個參數(shù)隶校，一個是樹的名稱漏益，一個是樹的左節(jié)點(diǎn)和右節(jié)點(diǎn)。請各位小伙伴注意哦深胳，這里的用的是指針绰疤，因?yàn)樵趃o語言中如果說不用引用傳遞，在后續(xù)添加節(jié)點(diǎn)后是沒有任何效果的舞终，下面我會給大家進(jìn)行演示一下轻庆。
當(dāng)我們將節(jié)點(diǎn)定義為不是引用類型的時候，直接編譯器都通不過敛劝，報了一個無效的遞歸類型的錯誤余爆。
所以我們先初始化一個根節(jié)點(diǎn)名稱為“It干貨棧”的節(jié)點(diǎn)攘蔽，然后左節(jié)點(diǎn)名稱為It 龙屉，右節(jié)點(diǎn)為干貨。兩個子節(jié)點(diǎn)就都沒有左右節(jié)點(diǎn)满俗。為了后續(xù)二叉樹的遍歷提供更多的數(shù)據(jù)转捕，我們將增加方法進(jìn)行追加樹的節(jié)點(diǎn)。
// 定義一個樹的節(jié)點(diǎn) [IT干貨棧]
type treeNode struct {
name string // 定義樹的名稱
left *treeNode // 左節(jié)點(diǎn)
right *treeNode // 右節(jié)點(diǎn)
}
// It干貨棧
func main() {
var node = treeNode{name: "It干貨棧", left: &treeNode{name: "It", left: nil}, right: &treeNode{name: "干貨"}}
addLeftNode(&node, 2)
addLeftNode(node.left, 3)
addLeftNode(node.left.left, 4)
addLeftNode(node.left.left.left, 5)
node.addRightNode(2)
node.right.addRightNode(3)
node.right.right.addRightNode(4)
node.right.right.right.addRightNode(5)
fmt.Println(node)
}
// 增加二叉樹左節(jié)點(diǎn)
func addLeftNode(node *treeNode, value int) {
children := treeNode{name: fmt.Sprintf("子節(jié)點(diǎn)%s%d", "It干貨棧", value)}
node.left = &children
}
// 增加二叉樹右節(jié)點(diǎn)
func (node *treeNode) addRightNode(value int) {
children := treeNode{
name: fmt.Sprint("關(guān)注公眾號", value),
left: nil,
right: nil,
}
node.right = &children
}
以上代碼我們我們定義了一個樹節(jié)點(diǎn)唆垃，并且增加了相關(guān)的增加的節(jié)點(diǎn)的方法五芝，細(xì)心的小伙伴可能已經(jīng)看出來了，我們增加左節(jié)點(diǎn)和增加右節(jié)點(diǎn)的方法并不相同辕万，那是因?yàn)樵趃o語言中我們不僅可以寫通用方法枢步，比如增加二叉樹左節(jié)點(diǎn)addLeftNode 方法。
我們還可以指定僅為treeNode專屬方法addRightNode渐尿。
我們在添加了很多節(jié)點(diǎn)后醉途，如果是采用傳統(tǒng)的print打印出來的結(jié)果，如下圖所示
所以接下來小棧君將為大家分享關(guān)于二叉樹的前序砖茸、中序隘擎、后序遍歷。
二叉樹遍歷
遍歷是對樹的一種最基本的運(yùn)算凉夯，所謂遍歷二叉樹货葬，就是按一定的規(guī)則和順序走遍二叉樹的所有結(jié)點(diǎn)采幌，使每一個結(jié)點(diǎn)都被訪問一次，而且只被訪問一次震桶。由于二叉樹是非線性結(jié)構(gòu)休傍，因此，樹的遍歷實(shí)質(zhì)上是將二叉樹的各個結(jié)點(diǎn)轉(zhuǎn)換成為一個線性序列來表示蹲姐。
前序遍歷
二叉樹的前序遍歷磨取，又稱為先序遍歷。在二叉樹的前序的順序柴墩，首先訪問根寝衫，再先序遍歷左（右）子樹，最后先序遍歷右（左）子樹拐邪。
是不是很簡單的代碼就完成了我們關(guān)于二叉樹的前序遍歷。先訪問根節(jié)點(diǎn)隘截，然后依次遍歷右節(jié)點(diǎn)和左節(jié)點(diǎn)扎阶，當(dāng)然我們也可以交換順序進(jìn)行先遍歷左節(jié)點(diǎn)在繼續(xù)遍歷右節(jié)點(diǎn)。
中序遍歷
關(guān)于go語言中序遍歷的順序婶芭，首先中序遍歷左（右）子樹东臀，再訪問根，最后中序遍歷右（左）子樹犀农。
后序遍歷
go語言的后序遍歷順序是首先后序遍歷左（右）子樹惰赋，再后序遍歷右（左）子樹，最后訪問根呵哨。那么他的順序就應(yīng)該如圖所示：
以上就是關(guān)于二叉樹的遍歷的分享赁濒，關(guān)于二叉樹的講解我們就到這里，對于先序遍歷孟害，中序遍歷拒炎，后續(xù)遍歷，其實(shí)其實(shí)也就是遍歷的順序不同而已挨务，接下來就附上當(dāng)前測試用例的代碼击你。
// 定義一個樹的節(jié)點(diǎn) [IT干貨棧]
type treeNode struct {
name string // 定義樹的名稱
left *treeNode // 左節(jié)點(diǎn)
right *treeNode // 右節(jié)點(diǎn)l
}
// It干貨棧
func main() {
var node = treeNode{name: "It干貨棧", left: &treeNode{name: "It", left: nil}, right: &treeNode{name: "干貨"}}
addLeftNode(&node, 2)
addLeftNode(node.left, 3)
addLeftNode(node.left.left, 4)
addLeftNode(node.left.left.left, 5)
node.addRightNode(2)
node.right.addRightNode(3)
node.right.right.addRightNode(4)
node.right.right.right.addRightNode(5)
traversal(&node)
}
// 遍歷
func traversal(node *treeNode) {
if node == nil {
return
}
traversal(node.left)
traversal(node.right)
fmt.Println("名稱", node.name)
}
// 增加二叉樹左節(jié)點(diǎn)
func addLeftNode(node *treeNode, value int) {
children := treeNode{name: fmt.Sprintf("子左節(jié)點(diǎn)->%s%d", "It干貨棧", value)}
node.left = &children
}
// 增加二叉樹右節(jié)點(diǎn)
func (node *treeNode) addRightNode(value int) {
children := treeNode{
name: fmt.Sprint("子右節(jié)點(diǎn)->關(guān)注公眾號", value),
left: nil,
right: nil,
}
node.right = &children
}
以上就是今天的分享了，如果你喜歡我的分享麻煩分享谎柄、轉(zhuǎn)發(fā)或點(diǎn)擊好看丁侄，我們下期再見，我是小棧君朝巫，拜了個拜~
本文由博客一文多發(fā)平臺 OpenWrite 發(fā)布鸿摇！
