树的基本概念

一、树的定义
树是n(n>0)个结点的有限集合，n = 0时，称为空树，这是一种特殊情况。在任意一棵非空的树中应该满足:
1)有且仅有一个称为根的结点。
2）当n>1时，其余结点可分为m(m>0)个互不相交的有限集合。其中每个集合本身就是一棵树，并且称为根节点的子树。
树的特点：
1）树的根节点没有前驱结点，除根节点之外所有的结点有且只有一个前驱结点。
2）树中所有结点可以有零个或多个后继结点。

二、树的基本术语
1、祖先结点，双亲结点，兄弟结点，孩子结点。
2、度：树中一个结点的子结点个数称为该结点的度。树中最大度数称为树的度。
3、分支结点：度大于0的结点称为分支结点。
叶子结点：度为0的结点称为叶子结点。
4、结点的深度、高度和层次、
树的高度（深度）：树中结点的最大层数
5、有序树和无序树。
6、路径和路径长度。
7、森林。

三、树的性质
1）树中的结点数等于所有结点的度数加1。
2）度为m的树中第i层上至多有 $m^{i-1}$ 个结点（i $\geq$ 1）
3）高度为h的m叉树至多有( $m^h-1$ ）/(m - 1)个结点。
4）具有n个结点的m叉树的最小高度为 $\lceil \log_m(n(m-1)) + 1\rceil$ 向下取整。