树遍历图

说句实话,看图就够

  1. 前序遍历
    1
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
       func breadthFirstSearch(node Node) []string {
    var result []string
    var nodes []Node = []Node{node}

    for len(nodes) > 0 {
    node := nodes[0]
    nodes = nodes[1:]
    result = append(result, node.data)
    if (node.left != nil) {
    nodes = append(nodes, *node.left)
    }
    if (node.right != nil) {
    nodes = append(nodes, *node.right)
    }
    }
    return result
    }
    ```

    2. 中序遍历
    ![2](/assets/img/trees/2.png)
    3. 后序遍历
    ![3](/assets/img/trees/3.png)
    4. 广度遍历
    ![4](/assets/img/trees/4.png)

    中序遍历和后序遍历有一种简单的递归方法:

func preOrderRecursive(node Node) {
fmt.Println(node.data)
if node.left != nil {
preOrderRecursive(node.left)
}
// 在这里输出就是中序
if node.right != nil {
preOrderRecursive(
node.right)
}
// 在这里输出是后序
`

Mysql? 树?

其实 mysql 和树沾边的地方在 mysql 所采用的索引结构,
其用到了 B-tree 和 B+Tree。(Balanced tree)

平衡树这玩意除了长得像树,别的还真不一样。
bt 有个 key 和 value 的概念,每个节点都可以有这两个东西,也不限制个数。像下图:
bt1
图中根节点,7,16就是这个节点的值,下面有三个点,就是 key,分别代表 小于7、大于7小于16、大于16。
每个节点会有个 degree 的概念,其实就是允许的最大 key
数量。
bt的值呢~是会分布在所有叶子和根的(有别于 b+t)。

B+tree

mysql 索引采用了一个改进版,称之为B+tree。
b+

b+树他只在叶子节点存放数据,其余的节点只做 key。
也就是说,所有根节点的索引的数据,最终也是映射在叶子节点的。

红黑树

AVL树