树和二叉树
树和二叉树
树和森林
树的基本概念
树的定义
树是一种逻辑结构
树是n（n≥0）个结点的有限集合，n=0时，称为空树。
而任意非空树应满足： 1）有且仅有一个特定的称为根的结点。 2）当n>1时，其余结点可分为m（m>0）个互不相交的有限集合，其中每一个集合本身又是一棵树，称为根结点的子树。
树的特点之一：n个结点的树中只有n-1条边
树基本术语
祖先节点和子孙节点
双亲节点和孩子节点
兄弟节点
节点的度：树中一个结点的子结点的个数
树的度：树中最大的节点度数称为树的度
分支结点：度大于0的结点（子节点个数大于0的节点）
叶子结点：度为0的结点
节点的层次：从根节点开始数，根为第一层（也有的教材中定为0层）
节点的高度：节点到叶子节点所有路径上包含节点个数的最大值。
节点的深度：从根节点到该节点唯一的路径上包含的节点个数，根节点深度为1
树的高度（深度）：树中结点的最大层数
有序树和无序树
路径：树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的。路径是有方向的，从上到下；不同兄弟树中节点不存在路径。
路径长度：路径上所经历边的个数。
森林：m（m≥0）棵互不相交的树的集合
树的性质
- 树中的结点数等于所有结点的度数加1
- 度为m的树中第层上至多有\(m^{i-1}\)个结点（i≥1）
- 高度为h的m叉树至多有\((m^h-1)/(m-1)\)个结点(由等比数列前n项和公式获得)
- 具有n个结点的m叉树的最小高度为\(\left\lceil\log _{\mathrm{m}}(\mathrm{n}(m-1)+1)\right\rceil\)，这是由上一条性质反推出来的