第五章 树与二叉树 一、树的定义与考点

一、定义

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个结点

 6、具有n个结点的m叉树的最小高度为