树
- 节点、根节点、父节点、子节点、兄弟节点
- 一棵树可以没有任何节点，称为空树
- 一棵树可以只有一个节点，也就是只有根节点
- 子树、左子树、右子树
- 节点的度：子树的个数
- 树的度：所有节点度中的最大值
- 叶子节点：度为0的节点
层数：根节点在第一层，根节点的子节点在第二层，以此类推
- 节点的深度：从根节点到当前节点的唯一路径上的节点总数
- 节点的高度：从当前节点到最远节点的路径上的节点总数
- 树的深度：所有节点深度中的最大值
- 树的高度：所有节点高度中的最大值
- 树的深度等于高度
有序树、无序树
-
二叉树 是一个有序树
（1） 每个节点的度最大为2
（2）左子树和右子树是有顺序的
（3）即使某节点只有一棵子树，也要区分左右子树 非空二叉树的第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，所有叶子节点在最后一层
完全二叉树：叶子节点只会出现最后2层，且最后1层的叶子结点都靠左对齐
度为1的节点只有左子树
度为1的节点要么是1个，要么是0个
同样节点的二叉树，完全二叉树的高度最小
-
设二叉树的 高度为h,h>=1,那么
（1）至少有2^(h-1)个节点
（2）最多有2^h-1个节点
（3）总结点为n,h-1<= log2(h)<h
h=floor(log2h)+1,floor向下取整，只取前面的整数。ceiling向上取整
总结点数量n=n0+n1+n2,而且n0=n2+1=>n=2n0+n1-1
-
完全二叉树的n1要么为0，要么为1
（1）n1为1时，n=2n0,n必然是偶数
叶子节点个数n0=n/2,非叶子节点个数n1+n2=n/2
（2）n1为0时，n=2n0-1,n必然是奇数
叶子节点个数n0=(n+1)/2,非叶子节点个数n1+n2=(n-2)/2 n如果是偶数 叶子节点数量n0=n/2
n如果是奇数 叶子节点数量n0=(n+1)/2
n0=floor((n+1)/2) n0=(n+1)>>1
注意：尽量避免使用乘、除/、模%、浮点数运算，效率低下
