树遍历图

说句实话,看图就够

  1. 前序遍历 1
    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
  3. 后序遍历 3
  4. 广度遍历 4

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

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树

Table of Contents