1.树（Tree）的基本概念
1.节点，根节点，父节点，子节点，兄弟节点
2.一棵树可以没有任何节点，称为空树
3.一棵可以只有1个节点，也就是只有根节点
4.子树，左子树，右子树
5.节点的度：子树的个数
6.树的度：所有节点度中的最大值
7.叶子节点：度为0的节点
8.非叶子节点：度不为0的节点
9.节点的深度：从根节点到当前节点的唯一路径上的节点总数
10.节点的高度：从当前节点到最远叶子节点的路径上节点总数
11.树的深度：所以节点深度中的最大值
12.树的高度：所以节点高度中的最大值
13.树的深度等于树的高度
2.有序树，无序树，森林
有序树
树中任意节点的子节点之间有顺序关系
无序树
树中任意节点的子节点之间没有顺序关系，也称自由树
森林
由n(n>=0)棵互不相交的树组成的集合
3.二叉树
二叉树的特点
每个节点的度最大为2（最多拥有2颗子树）
左子树和右子树是由顺序的（二叉树是有序树）
即使某节点只有一棵子树，也要区分左右子树
二叉树的性质
非空二叉树的第i层，最多有
个节点（i>=1）
在高度为h的二叉树上最多有
个节点（h>=1）
对于任何一棵非空二叉树，如果叶子节点个数为n0，度为2的节点个数为n2，则有：n0 = n2+1
假设度为1的节点个数为n1，那么二叉树的节点总数 n = n0+n1+n2
二叉树的边数T = n1+2*n2 = n -1 = n0+n1+n2-1
因此 n0 = n2+1
4.真二叉树
真二叉树：所有节点的度要么为0，要么为2
5.满二叉树
满二叉树：最后一层节点的度为0，其他节点的度为2
假设满二叉树的高度为h(h>=1),那么
第i层的节点数量为：
叶子节点数量：
总节点数量n
n=
h =
在同样高度的二叉树中，满二叉树的叶子节点数量最多，总节点数量最多
满二叉树一定是真二叉树，真二叉树不一定是满二叉树
6.完全二叉树
完全二叉树：对节点从上到下，左到右开始编号，其所有编号都能和相同高度的满二叉树中的编号对应
叶子节点只会出现在最后2层，最后1层的叶子节点都靠左对齐
完全二叉树丛根节点至倒数第2层是一棵满二叉树
满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树
完全二叉树的性质
度为1的节点只有左子树
度为1 的节点要么1个，要么0个
同样节点的数量的二叉树，完全二叉树的高度最小
假设完全二叉树的高度为h(h>=1),那么
至少有
个节点（
）
最多有
）
节点总数为n
<= n <
h-1 <=
< h
h = floor(
)+1
floor向下取整，ceiling向上取整
（经典题目）如果一棵完全二叉树有768个节点，求叶子节点的个数
假设叶子节点个数为n0,度为1的节点个数为n1，度为2的节点个数为n2
总节点个数为n= n0+n1+n2,而且n0 = n2+1
n = 2*n0+n1-1
完全二叉树的n1要么为0，要么为1
n1为1的时候，n = 2n0,n必为偶数
叶子节点个数n0 = n/2,非叶子点个数为 n1+n2 = n/2
n1为0的时候 n = 2*n0-1,n必为奇数
叶子节点个数n0 = (n+1)/2,非叶子节点个数n1 + n2 = (n-1)/2
叶子节点个数n0 = floor((n+1)/2) = ceiling(n/2)
非叶子节点个数n1+n2 = floor(n/2) = ceiling((n-1)/2)
因此叶子节点个数为384
7.二叉树的遍历
根节点访问顺序的不同，二叉树的常见遍历方式有4种
前序遍历
根节点，前序遍历左子树，前序遍历右子树
7-4-2-1-3-5-9-8-11-10-12
中序遍历
中序遍历左子树，根节点，中序遍历右子树
1-2-3-4-5-6-7-8-9-10-11-12
二叉搜索树的中序遍历结果是升序或者降序
后序遍历
后序遍历左子树，后序遍历右子树，根节点
1-3-2-5-4-9-10-12-11-9-7
层序遍历
丛上到下，丛左到右依次访问每一个节点
7-4-9-2-5-8-11-1-3-10-12
