Hello，各位小夥伴大家好，我是小棧君，今天給大家帶來的分享是關於關於二叉樹相關的知識點，並用go語言實現一個二叉樹。我們主要針對二叉樹的概念，go實戰實現二叉樹的前序遍歷、中序遍歷、後序遍歷。
二叉樹概念
在計算機科學領域內，二叉樹代表的是具有兩個節點的樹形結構，通常子樹被稱作為“左子樹”，右邊的被稱作為“右子樹”。
二叉樹通常的應用於實現二叉查找樹和二叉堆。例如上述圖片中，我們就制定了一個二叉樹，其中d、e、f稱作a樹的葉子節點。
[葉子結點是離散數學中的概念。一棵樹當中沒有子結點（即度為0）的結點稱為葉子結點，簡稱“葉子”。 葉子是指出度為0的結點，又稱為終端結點]
b和c 作為樹a的孩子結點，b和a因為作為一個根a的孩子，所以他們的稱呼為兄弟結點。其實總結一點就是關於二叉樹各個結點的稱呼其實和我們在家庭中，對於各個親戚長輩的稱呼類似。
在百度百科中也歸納除了關於二叉樹概念,一棵深度為k，且有2^k-1個結點的二叉樹，稱為滿二叉樹。這種樹的特點是每一層上的結點數都是最大結點數。
而在一棵二叉樹中，除最後一層外，若其餘層都是滿的，並且或者最後一層是滿的，或者是在右邊缺少連續若干結點，則此二叉樹為完全二叉樹。具有n個結點的完全二叉樹的深度為floor(log2n)+1。
深度為k的完全二叉樹，至少有2k-1個葉子結點，至多有2k-1個結點。
所以通過我們上面的理論基礎，我們結合代碼來實現一下我們的二叉樹結構。
如圖所示 ，我們定義了一個樹treeNode的結構體，關於結構體的分享，小棧君會在下一期對大家進行分享。對於go語言專題分享已經過了差不多三分之一，接下來我們會開啟新的分享之旅，還請各位持續關注“IT乾貨棧”。
閒話不多說，我們在結構體中定義了三個參數，一個是樹的名稱，一個是樹的左節點和右節點。
請各位小夥伴注意哦，這裡的用的是指針，因為在go語言中如果說不用引用傳遞，在後續添加節點後是沒有任何效果的，下面我會給大家進行演示一下。
當我們將節點定義為不是引用類型的時候，直接編譯器都通不過，報了一個無效的遞歸類型的錯誤。
所以我們先初始化一個根節點名稱為“It乾貨棧”的節點，然後左節點名稱為It ，右節點為乾貨。兩個子節點就都沒有左右節點。
為了後續二叉樹的遍歷提供更多的數據，我們將增加方法進行追加樹的節點。
<code>//定義一個樹的節點[IT乾貨棧]type treeNode struct {name string // 定義樹的名稱left *treeNode // 左節點right *treeNode // 右節點} // 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)}//增加二叉樹左節點funcaddLeftNode(node*treeNode,valueint){ children:=treeNode{name:fmt.Sprintf("子節點%s%d","It乾貨棧",value)} node.left=&children}//增加二叉樹右節點 func(node*treeNode) addRightNode(valueint){ children:=treeNode{name:fmt.Sprint("關注公眾號",value),left:nil,right:nil,} node.right=&children }/<code>以上代碼我們我們定義了一個樹節點，並且增加了相關的增加的節點的方法，細心的小夥伴可能已經看出來了，我們增加左節點和增加右節點的方法並不相同，那是因為在go語言中我們不僅可以寫通用方法，比如增加二叉樹左節點addLeftNode 方法。
我們還可以指定僅為treeNode專屬方法addRightNode。
我們在添加了很多節點後，如果是採用傳統的print打印出來的結果，如下圖所示
所以接下來小棧君將為大家分享關於二叉樹的前序、中序、後序遍歷。
二叉樹遍歷
遍歷是對樹的一種最基本的運算，所謂遍歷二叉樹，就是按一定的規則和順序走遍二叉樹的所有結點，使每一個結點都被訪問一次，而且只被訪問一次。
由於二叉樹是非線性結構，因此，樹的遍歷實質上是將二叉樹的各個結點轉換成為一個線性序列來表示。
前序遍歷
二叉樹的前序遍歷，又稱為先序遍歷。在二叉樹的前序的順序，首先訪問根，再先序遍歷左（右）子樹，最後先序遍歷右（左）子樹。
是不是很簡單的代碼就完成了我們關於二叉樹的前序遍歷。先訪問根節點，然後依次遍歷右節點和左節點，當然我們也可以交換順序進行先遍歷左節點在繼續遍歷右節點。
中序遍歷
關於go語言中序遍歷的順序，首先中序遍歷左（右）子樹，再訪問根，最後中序遍歷右（左）子樹。
後序遍歷
go語言的後序遍歷順序是首先後序遍歷左（右）子樹，再後序遍歷右（左）子樹，最後訪問根。那麼他的順序就應該如圖所示：
以上就是關於二叉樹的遍歷的分享，關於二叉樹的講解我們就到這裡，對於先序遍歷，中序遍歷，後續遍歷，其實其實也就是遍歷的順序不同而已，接下來就附上當前測試用例的代碼
<code> // 定義一個樹的節點type treeNode struct {name string // 定義樹的名稱 left *treeNode // 左節點right*treeNode//右節點}//It乾貨棧funcmain(){ varnode=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)} //遍歷 functraversal(node*treeNode){ ifnode==nil{ return } traversal(node.left) traversal(node.right) fmt.Println("名稱",node.name)}//增加二叉樹左節點funcaddLeftNode(node*treeNode,valueint){ children:=treeNode{ name:fmt.Sprintf("子左節點->%s%d","It乾貨棧",value) } node.left=&children}//增加二叉樹右節點func(node*treeNode)addRightNode(valueint){ children:=treeNode{ name:fmt.Sprint("子右節點->關注公眾號",value), left:nil,right:nil, } node.right=&children}/<code>
閱讀更多 quadtree 的文章
