第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 （有几个直接后继就是几度，亦称“次数”）
6.1.2树的抽象数据类型数据集合：树的结点集合，每个结点由数据元素和构造数据元素之间关系的指针组成。操作集合：（1）双亲结点parentO：把当前结点的双亲结点置为当前结点。（2）左孩子结点leftChildO：把当前结点的左孩子结点置为当前结点。（3）右兄弟结点rightSiblingO：把当前结点的右兄弟结点置为当前结点。（4）遍历树traverse(vs）：按某种遍历方法访问树的每个结点，且每个结点只访问一次
数据集合 ：树的结点集合，每个结点由数据元素和构 造数据元素之间关系的指针组成。 操作集合： （1）双亲结点parent() ：把当前结点的双亲结点置为 当前结点。 （2）左孩子结点leftChild()：把当前结点的左孩子结 点置为当前结点。 （3）右兄弟结点rightSibling() ：把当前结点的右兄弟 结点置为当前结点。 （4）遍历树traverse(vs) ：按某种遍历方法访问树的 每个结点，且每个结点只访问一次。 6.1.2 树的抽象数据类型
6.1.3树的存储结构1.双亲表示法2.孩子表示法3.双亲孩子表示法4.孩子兄弟表示法
6.1.3 树的存储结构 1.双亲表示法 2.孩子表示法 3.双亲孩子表示法 4.孩子兄弟表示法
1双亲表示法双亲表示法就是用指针表示出每个结点的双亲结点。对于使用仿真指针的双亲表示法来说，每个结点应有两个域，一个是数据元素域，另一个是指示其双亲结点在数组中下标序号的仿真指针域
1 双亲表示法 双亲表示法就是用指针表示出每个结点的双亲结点。 对于使用仿真指针的双亲表示法来说，每个结点应 有两个域，一个是数据元素域，另一个是指示其双 亲结点在数组中下标序号的仿真指针域
树及其使用仿真指针的双亲表示法dataparent0A-1B0120C3D1BC4E15F1E6G27H4H184(b)(a)
树及其使用仿真指针的双亲表示法 A D E F G C H I B 0 1 2 3 4 5 6 7 8 A B C D E F G H I data parent -1 0 0 1 1 1 2 4 4 (a) (b)
2孩子表示法孩子表示法就是用指针表示出每个结点的孩子结点。root常规指针的孩子表示法
2 孩子表示法 孩子表示法就是用指针表示出每个 结点的孩子结点。 A D E F G C H I B A B C D E F G H I ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ root ∧ 常规指针的孩子表示法