二叉树

一、认识

每个节点最多只能有两个子节点的一种形式称为二叉树。二叉树的子节点分为左节点和右节点。任何的树都可以使用二叉树模拟出来

每个节点的度最大为 2（最多拥有两颗子树）
左子树和右子树是有顺序的
即使某节点只有一颗子树，也要区分左右子树
非空二叉树的第 i 层，最多有 $2^{i - 1}$ 个节点
在高度为 h 的二叉树上最多有 $2^{h}$ - 1 个节点
对于任何一颗非空二叉树，如果叶子节点个数为 n0 , 度为 2 的节点个数为 n2, 则有：n0 = n2 + 1
- 假设度为 1 的节点个数为 n1 ,那么二叉树的节点总数 n = n0 + n1 + n2
- 二叉树的边数 T = n1 + 2*n2 = n-1= n0 + n1 + n2 - 1

真二叉树：所有节点的度都要么为 0，要么为 2

满二叉树：所有节点的度都要么为 0，要么为 2 ，且所有的叶子节点都在最后一层

完全二叉树：叶子节点只会出现在最后两层，且最后一层的叶子节点都靠左对齐

度为 1 的节点只有左子树
度为 1 的节点要么是 1 个，要么是 0 个
假设完全二叉树的高度为 h （h >= 1），那么
- 至少有 $2^{h - 1}$ 个节点
- 最多有 $2^{h}$ - 1 个节点（满二叉树）
- 总结点数量为 n $2^{h - 1}$ <= n < $2^{h}$ => h = Math.floor( $log_{}{2n}$ ) + 1
一颗有 n 个节点的完全二叉树 (n>0) , 从上到下，从左到右对节点从 1 开始进行编号，对任意第 i 个节点
- 如果有 i=1 ，它是根节点
- 如果 i>1,它的父节点编号为 Math.floor(i / 2)
- 如果 2*i <= n,它的左子节点编号为 2i,如果 2*i > n ,它无左子节点
- 如果 2i+1 <= n, 它的右子节点编号为 2i+1 ,如果 2i+1 > n ，它无右子节点
- 一颗有 n 个节点的完全二叉树 (n>0) , 从上到下，从左到右对节点从 0 开始进行编号，对任意第 i 个节点
- 如果有 i=0 ，它是根节点
- 如果 i>1,它的父节点编号为 Math.floor(（i-1） / 2)
- 如果 2*i+1 <= n-1,它的左子节点编号为 2i,如果 2*i+1 > n-1 ,它无左子节点
- 如果 2i+2 <= n-1, 它的右子节点编号为 2i+1 ,如果 2i+2 > n-1 ，它无右子节点

规则：
- 如果 n 为偶数,叶子节点个数为 n(叶子节点) = n / 2 非叶子节点个数 n(非叶子节点) = n /2
- 如果 n 为奇数,叶子节点个数为 n(叶子节点) = (n+1) / 2 , 非叶子节点 n (n-1)/2
公式：
- 叶子节点数量 = Math.floor((n+1)/2) 或者 = Math.ceil(n/2)
- 非叶子节点数量 = Math.floor(n/2) 或者 = Math.ceil((n-1)/2)