二叉樹是比較基礎的資料結構，以前也知道，但是一直沒有細究，不明白它究竟有什么作用，這次學習資料結構，結合Go語言來動手實踐一個，只有動手做一做對它的理解才比較深一點，
二叉樹的定義
首先是二叉樹的定義，二叉樹顧名思義有兩個叉，左右各一個，最多兩個，
根節點
關于根節點，起初我還以為二叉樹的根節點會變，比如根據值的大小，改變根節點，這個理解是不對的，代碼實作的時候，第一個就作為根節點，后面來的，小的就往左放，大的就往右放，會調整改變的那個叫平衡二叉樹
下面用這個圖來說明一下
比如有四個數 13， 14， 15， 19
比如我按這樣的順序放樹就長這樣： 19 , 13, 14, 15
如果我們這樣的順序來放 14，13， 15，19， 樹就是這樣的
所以樹長什么樣子，跟我們放的順序有關，而不是說一個對于相同的數值，有固定的樹，
二叉樹的遍歷
二叉樹分為三種遍歷方式
中序遍歷（InOrder） 左子樹-> 樹根 -> 右子樹， 如下圖就是 abc
前序遍歷（PreOrder) 樹根 -> 左子樹 -> 右子樹 如下圖就是 bac
后序遍歷 (PostOrder) 左子樹 -> 右子樹 -> 樹根 如下圖就是 acb
這個前序中序后序是以樹根的位置來說的，記住這一點，就不怕混淆了，
我們可以看到前序遍歷就能達到排序的效果，abc，
下面通過go 語言來實作二叉樹，代碼其實非常簡單
type tree struct {
value int
left *tree
right *tree
}
func add(t *tree, value int) *tree {
if t == nil {
t = new(tree)
t.value = https://www.cnblogs.com/dk168/archive/2022/11/07/value
return t
}
if value < t.value {
t.left = add(t.left, value)
} else {
t.right = add(t.right, value)
}
return t
}
func inOrder(node *tree) {
if node != nil {
inOrder(node.left)
fmt.Printf(" [%d] ", node.value)
inOrder(node.right)
}
}
func main() {
values := []int{7, 4, 1, 5}
var tree *tree
for _, value := range values {
//fmt.Printf(" [%d] ", value)
tree = add(tree, value)
}
inOrder(tree)
}
代碼塊中我們定義了tree的結構體，它含有一個value，然后兩個指標一個指向左邊，一個指向右邊
定義了一個add方法，通過遞回呼叫，小的就放左邊，大的就放右邊，
然后inOrder方法也是遞回呼叫，先找左邊，再找右邊， 中間值列印出來，通過這個方法就達到了我們示例的排序效果，程式的輸出為 1 4 5 7，
通過Go 的代碼我們可以看出二叉樹實作起來代碼非常精簡，也很清晰，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/528808.html
標籤：其他