第五章 树与二叉树 一、树的定义与考点
一、定义
1.树是由n (n >= 0) 个节点组成的有限集合。
2.当n=0时，称为空树。
3.在非空树中，有且仅有一个节点没有前驱，其他节点都有且仅有一个前驱，称为根节点。
4.每个节点有零个或多个子节点，而每个子节点又有零个或多个自己的子节点，以此类推，形成了树状结构。
树有一些重要的概念：
- 节点的度：一个节点的子树个数称为该节点的度；
- 叶子节点：度为0的节点称为叶子节点；
- 父节点和子节点：若将节点x作为根节点的子树中的一个节点，那么x的父节点就是根节点，x的子节点为x的子树中的所有节点；
- 兄弟节点：具有相同父节点的节点互为兄弟节点；
- 路径：从节点x到y的路径是由节点x到节点y沿树边所经过的所有节点；
- 路径长度：路径上的边数称为路径长度；
- 节点的深度：从根节点到该节点所经过的路径长度称为该节点的深度；
- 树的深度：树中所有节点深度的最大值称为树的深度。
二、考点
1、结点数=总度数+1
2、度为m的树与m叉树的区别
3、度为m的树第i层最多有
个结点（i>=1）
m叉树第i层最多有个结点（i>=1）
4、高度为h的m叉树至多有
个结点 （用等比数列求和公式求和）
5、高度为h的m叉树至少有h个结点
高度为h、度为m的树至少有h+m-1个结点
