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

层序遍历