# 樹
> n 個結點的有限集，或為空樹(n=0)，或非空樹。
對于非空樹T：
- 有且只有一個根結點
- 除根結點以外的其余結點可分為m個互不相交的有限集T1, T2, ...
- 一棵樹中的任意兩個結點有且僅有唯一的路徑連通
-
### 樹的基本術語
- 結點
- 結點的度：結點擁有子樹數
- 樹的度：樹內各結點度的最大值
- 葉子：度為0的結點稱為葉子或終端結點
- 層次：結點的層次從根結點開始為第一層；任一結點的層次等于雙親的層次加1
- 深度：樹中結點的最大層次成為樹的深度或高度（上圖的定義似乎和《數據結構C語言版》中深度定義有出入）
### 二叉樹
> 由 n ( n >= 0 ) 個結點組成的集合。
對于非空二叉樹T：
- 有且只有一個根結點
- 除了根結點外，其余結點為兩個互不相交的子集T1、T2，稱為T的左右子樹，并且T1,T2本身也是二叉樹
#### 和樹的區別
- 二叉樹每個結點最多只有2棵子樹
- 子樹有左右之分，不可顛倒
#### 性質
- 二叉樹的第 ` i ` 層至多擁有`2^(i-1)`個結點
- 深度為 k 的二叉樹至多總共有 `2^k-1` 個節點
- 如果其葉子結點數為n0，度為2的結點數為n2，則n0 = n2 + 1
**滿二叉樹**
深度為k，且有2^k - 1 個結點的二叉樹
**完全二叉樹**
深度為k的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為k的滿二叉樹中編號從1至n的結點一一對應時，稱之為完全二叉樹。
也就是說，除了最后一層，其它層子結點是滿的，并且深度k那一層的子結點是滿的，或者在右邊缺少連續若干結點。
mermaid
圖如下：
```mermaid
graph TB
A-->B
A-->C
B-->D
B-->E
C-->F
```
**平衡二叉樹**
- 可以是一棵空樹
- 非空樹，左右子樹的高度差絕對值不超過1，并且左右兩棵子樹都是一棵平衡二叉樹
平衡二叉樹的常用實現方法有 **紅黑樹**，**AVL樹**，**替罪羊樹**， **加權平衡樹**， **伸展樹** 等
**二叉樹存儲**
- 鏈式存儲
- 順序存儲：如果存儲的不是完全二叉樹，會導致內存利用率低
**二叉樹的遍歷**
先序遍歷
> 二叉樹的先序遍歷，就是先輸出根結點，再遍歷左子樹，最后遍歷右子樹，遍歷左子樹和右子樹的時候，同樣遵循先序遍歷的規則，也就是說，我們可以遞歸實現先序遍歷
```mermaid
graph TB
node3-->node1
node3-->node2
```
```go
package main
import "fmt"
func main() {
node1 := TreeNode{data: "node1"}
node2 := TreeNode{data: "node2"}
node3 := TreeNode{data: "node3", left: &node1, right: &node2}
showMsg(&node3)
}
type TreeNode struct {
data string
left *TreeNode
right *TreeNode
}
func showMsg(node *TreeNode) {
if node != nil {
fmt.Println(node.data)
showMsg(node.left)
showMsg(node.right)
} else {
return
}
}
```
中序遍歷
> 二叉樹的中序遍歷，就是先遞歸中序遍歷左子樹，再輸出根結點的值，再遞歸中序遍歷右子樹，大家可以想象成一巴掌把樹壓扁，父結點被拍到了左子節點和右子節點的中間
```go
func showMsg(node *TreeNode) {
if node != nil {
showMsg(node.left)
fmt.Println(node.data)
showMsg(node.right)
} else {
return
}
}
```
后序遍歷
> 二叉樹的后序遍歷，就是先遞歸后序遍歷左子樹，再遞歸后序遍歷右子樹，最后輸出根結點的值
```go
func showMsg(node *TreeNode) {
if node != nil {
showMsg(node.left)
showMsg(node.right)
fmt.Println(node.data)
} else {
return
}
}
```
