第6章 树和二叉树6.1 树6.2 二叉树6.3以结点类为基础的二叉树设计6.4二叉树类6.5线索二叉树6.6哈夫曼树6.7树与二叉树的转换6.8树的遍历
第6章 树和二叉树 6.1 树 6.2 二叉树 6.3 以结点类为基础的二叉树设计 6.4 二叉树类 6.5 线索二叉树 6.6 哈夫曼树 6.7 树与二叉树的转换 6.8 树的遍历
6.1 树6.1.1树的定义树是由n(n≥0)个结点组成的有限集合T。n=0的树称为空树；对n>0的树，有：(1)仅有一个特殊的结点称为根结点根结点没有前驱结点：（2)当n>1时，除根结点外其余的结点分为m(m>0)个互不相交的有限集合T1,T2，.，Tm，其中每个集合T：本身又是一棵结构和树类似的子树。注意：树的定义具有递归性，即“树中还有树
6.1 树 6.1.1 树的定义 注意：树的定义具有递归性，即“树中还有树”。 树是由n(n≥0)个结点组成的有限集合T。n=0的树称为 空树；对n>0的树，有:(1)仅有一个特殊的结点称为根结点， 根结点没有前驱结点；(2)当n>1时，除根结点外其余的结点 分为m(m>0)个互不相交的有限集合T1,T2，.，Tm，其中 每个集合Ti本身又是一棵结构和树类似的子树
树的示例：BEFHK(b)(a)一般的树只有根结点的树
树的示例： A B C D E F G H I J K L A (a) (b) 只有根结点的树 一般的树
若干术语根即根结点（没有前驱叶子结点即终端结点（没有后继）森林指m棵不相交的树的集合（例如删除A后的子树个数有序树结点各子树从左至右有序，不能互换（左为第一）无序树结点各子树可互换位置双亲结点即上层的那个结点（直接前驱）孩子结点即下层结点的子树的根（直接后继兄弟结点同一双亲下的同层结点（孩子之间互称兄弟）祖先结点即从根到该结点所经分支的所有结点子孙结点即以该结点为根的子树中的所有结点
若干术语 ——即上层的那个结点(直接前驱) ——即下层结点的子树的根(直接后继) ——同一双亲下的同层结点（孩子之间互称兄弟） ——即从根到该结点所经分支的所有结点 ——即以该结点为根的子树中的所有结点 A B C E G I D F H J K L F 根 叶子结点 森林 有序树 无序树 ——即根结点(没有前驱) ——即终端结点(没有后继) ——指m棵不相交的树的集 合(例如删除A后的子树个数) 双亲结点 孩子结点 兄弟结点 祖先结点 子孙结点 ——结点各子树从左至右有序，不能互换（左为第一） ——结点各子树可互换位置
结点即树的数据元素结点的度结点挂接的子树数（有几个直接后继就是几度，亦称“次数结点的层次从根到该结点的层数（根结点算第0层）终端结点即度为0的结点，即叶子分支结点即度不为0的结点（也称为内部结点）树的度所有结点度中的最大值（Max各结点的度）树的深度指所有结点中最大的层数（Max各结点的层次）(或高度)3问：右上图中的结点数=13树的度=3树的深度=
——即树的数据元素 ——结点挂接的子树数 结点 结点的度 结点的层次 终端结点 分支结点 树的度 树的深度 (或高度) A B C E G I D F H J K L F ——从根到该结点的层数（根结点算第0层） ——即度为0的结点，即叶子 ——即度不为0的结点（也称为内部结点） ——所有结点度中的最大值（Max{各结点的度}） ——指所有结点中最大的层数（Max{各结点的层次}） 问：右上图中的结点数＝13；树的度＝ 3；树的深度＝ 3 （有几个直接后继就是几度，亦称“次数”）