BinaryTree.md

二叉树的性质

1. 在二叉树的第 i 层最多有 $2^{k-1}$ 个结点，这个很好理解，第一层根节点就只有一个$2^{1-1} = 1$个元素，依次下来是 $2^{2-1} = 2,2^{3-1} = 4,2^{4-1} = 8...$ 。这个总结一下就是当在第 i 层的时候，那么这一层最多就是有 $2^{k-1}$ 个节点，满二叉树的时候才会有 $2^{k-1}$ 个结点。
2. 当二叉树的深度是 k 的时候，那么整个二叉树最多有 $2^k - 1$ 个结点。注意现在是整个二叉树上的所有结点，不是单纯的某一层上的结点。
3. 当一个完全二叉树的结点是 n 的时候，注意这里是指的完全二叉树，那么这棵树的深度是向下取整的 $\lfloor log2^n \rfloor + 1$，比如说有 6 个节点的完全二叉树，那么深度就是 $\lfloor log2^6 \rfloor + 1$ = 1 + $\lfloor 1.5xxx \rfloor + 1$ = 3

从上面的第三条可以看出来，同样是深度为 6 的节点，完全二叉树层高就只有三，而如果是退化成链表的二叉树的话，层高就是 6。二叉树的搜索效率和层高是成正比的，当层高越矮，效率就越高。 当是完全二叉树的时候，搜索的效率就是 $O(log2^n)$，当树退化成链表的时候，时间复杂度就是 $O(n)$，当一千个数据的时候， $\lfloor O(log2^1000) \rfloor$ = 10 而 $O(1000)$ = 1000，这之间差距是 100 倍。所以掌握数据结构是一个非常重要的技能。

二叉树的遍历

二叉树的遍历有很多种方案，使用递归方案的时候，有前序遍历，中序遍历，后序遍历。

type NodeTree struct {
    value  int
    left   *NodeTree
    right  *NodeTree
}

前序遍历，中序遍历，后序遍历，都是相对而言

前序：根 -> 左 -> 右 中序：左 -> 根 -> 右 后序：右 -> 根 -> 左

前序遍历

前序：根 -> 左 -> 右