树的定义：
树（Tree）是n（n≥0）个有限数据元素的集合。在任意一棵非空树T中：
- 有且仅有一个特定的无前趋结点, 称为树根（Root）
当n>1时，除根结点之外的其余结点被分成m（m>0）个互不相交的集合T1，T2，…，Tm，其中每一个集合Ti（1≤ i ≤m）本身又是一棵树，并且称为根的子树。
树的基本术语：
结点——树的结点包含一个数据元素及若干指向其子树的分支。
- 结点的度——结点所拥有的子树数称为该结点的度（Degree）。
- 树的度——树中各结点度的最大值称为该树的度。
- 叶子（终端结点）——度为零的结点称为叶子结点。
- 分枝结点——度不为零的结点称为分支结点。
- 兄弟结点——同一父亲结点下的子结点称为兄弟结点。
- 层数——树的根结点的层数为1，其余结点的层数等于它双亲结点的层数加1。
- 树的深度——树中结点的最大层数称为树的深度（或高度）。
-
二叉树的定义：
二叉树是有n（n>=0）个结点的有限集合。
该集合或者为空（n=0）；
- 或者由一个根结点及两个不相交的分别称为左子树和右子树组成的非空树；
- 左子树和右子树同样又都是二叉树。
在一棵非空的二叉树中，每个结点至多只有两棵子树，分别称为左子树和右子树，且左右子树的次序不能任意交换。所以，二叉树是特殊的有序树。
**
满二叉树：
- 一棵深度为h，且有2 h‐1个结点的二叉树称为满二叉树。
- 其特点是每一层上的结点都具有最大的结点数。
- 约定编号从根节点起,从上往下,自左向右—>完全二叉树的定义.
- 满二叉树如图：
完全二叉树：
- 深度为h，有n个结点的二叉树，当且仅当每一个结点都与深度为h的满二叉树中编号从1至n的结点一一对应时，称此二叉树为完全二叉树。
- 完全二叉树如图：
二叉树的性质：
- 性质一，一棵非空二叉树的第
i层上最多有2个结点（i ≥1）。- 一棵非空二叉树的第一层有1个结点，第二层最多有2个结点，第三层最多有4个结点……，利用归纳法即可证明第i层上最多有2 i–1个结点。
- 性质二，深度为
h的二叉树中最多具有2个结点（h ≥1）。 - 性质三，对于一棵有n个结点的完全二叉树，若按满二叉树的同样
方法对结点进行编号，则对于任意序号为i的结点，有：
- 若i>1，则序号为i的结点的父结点的序号为i/2； 若i＝1，则序号为i的结点是根结点。
- 若2i≤n，则序号为i的结点的左孩子结点的序号为2i； 若2i>n，则序号为i的结点无左孩子。
- 若2i＋1≤n，则序号为i的结点的右孩子结点的序号为2i＋1； 若2i＋1>n，则序号为i的结点无右孩子。
- 性质四，具有n（n>0）个结点的完全二叉树（包括满二叉树）的深度（h）为
(``log````n)+1。 - 性质五，对于一棵非空的二叉树，设n0、n1、n2分别表示度为0、1、2的结点个数，
则有:
n0＝n2＋1。
哈夫曼树：
- 路径长度——从树中的一个结点到另一个结点之间的分支构成两个结点间的路径，路径上的分支数目，称作路径长度。
- 树的路径长度——从树根到每个结点的路径长度之和称为树的路径长度。
- 结点的带权路径长度——从该结点到树根之间路径长度与该结点上权的乘积。
- 树的带权路径长度——树中所有叶子结点的带权路径长度 之和，称为树的带权路径长度。
若有收获，就点个赞吧
0 人点赞
