第7章树和二叉树(Tree& Binary tree) 特点:非线性结构,一个直接前驱,但可能有多个 直接后继。(一对多或1n) 7.1树 72二叉树 73二叉树的设计与实现 74遍历二叉树和线索二叉树 7.5赫夫曼树及其应用 7.6树与二叉树的转换
1 第7章 树和二叉树（Tree & Binary Tree） 7.1 树 7.2 二叉树 7.3 二叉树的设计与实现 7.4 遍历二叉树和线索二叉树 7.5 赫夫曼树及其应用 7.6 树与二叉树的转换 特点：非线性结构，一个直接前驱，但可能有多个 直接后继。（一对多或1:n）
7.1 树 7.1.1树的定义 树是由n(20)个结点组成的有限集合T。n=0的树称为 空树;对n>0的树,有:(1)仅有一个特殊的结点称为根结点, 根结点没有前驱结点;(2)当n>1时,除根结点外其余的结点 分为mm>0个互不相交的有限集合T1T2,…,Tm,其中 每个集合T本身又是一棵结构和树类似的子树。 注1:树的定义具有递归性,即“树中还有树
2 7.1 树 7.1.1 树的定义 注1：树的定义具有递归性，即“树中还有树”。 树是由n(n≥0)个结点组成的有限集合T。n=0的树称为 空树；对n>0的树，有:(1)仅有一个特殊的结点称为根结点， 根结点没有前驱结点；(2)当n>1时，除根结点外其余的结点 分为m(m>0)个互不相交的有限集合T1,T2，…，Tm，其中 每个集合Ti本身又是一棵结构和树类似的子树
7.1.2若干术语 B 叶子结点即您端结点(有后罐)(D(① 森林 指m棵不相交的树的集 合(例如删除A后的子树个数)K F)图71 有序树 结点各子树从左至右有序,不能互换(左为第一) 无序树 结点各子树可互换位置。 双亲结点即上层的那个结点(直接前驱 孩子结点即下层结点的子树的根直接后继) 兄弟结点同一双亲下的同层结点(孩子之间互称兄弟) 祖先结点即从根到该结点所经分支的所有结点 子孙结点即该结点下层子树中的任一结点
3 7.1.2 若干术语 ——即上层的那个结点(直接前驱) ——即下层结点的子树的根(直接后继) ——同一双亲下的同层结点（孩子之间互称兄弟） ——即从根到该结点所经分支的所有结点 ——即该结点下层子树中的任一结点 A B C E G I D F H J K L F 根 叶子结点 森林 有序树 无序树 ——即根结点(没有前驱) ——即终端结点(没有后继) ——指m棵不相交的树的集 合(例如删除A后的子树个数) 双亲结点 孩子结点 兄弟结点 祖先结点 子孙结点 ——结点各子树从左至右有序，不能互换（左为第一） ——结点各子树可互换位置。 图7.1
B 结点 即树的数据元素 结点的度结点挂接的子树数 E F八(G 有几个直接后继就是几度,亦称“次数”)K F 结点的层次—从根到该结点的层数(根结点算第一层) 终端结点 即度为0的结点,即叶子 分支结点即度不为0的结点(也称为内部结点) 树的度 所有结点度中的最大值(Max{各结点的度}) 树的深度指所有结点中最大的层数(Max{各结点的层次}) (或高度) 问:右上图中的结点数=13树的度=3树的深度=4
4 ——即树的数据元素 ——结点挂接的子树数 结点 结点的度 结点的层次 终端结点 分支结点 树的度 树的深度 (或高度) A B C E G I D F H J K L F ——从根到该结点的层数（根结点算第一层） ——即度为0的结点，即叶子 ——即度不为0的结点（也称为内部结点） ——所有结点度中的最大值（Max{各结点的度}） ——指所有结点中最大的层数（Max{各结点的层次}） 问：右上图中的结点数＝13；树的度＝ 3；树的深度＝ 4 （有几个直接后继就是几度，亦称“次数”）
7.1.3树的抽象数据类型 数据集合:树的结点集合,每个结点由数据元素和构造数 据元素之间关系的指针组成 操作集合: (1)创建树 Maketre(T (2)撤消树 Destroy Tree( (3)查找树中当前结点的双亲结点 Parent(r,curr) (4)查找树中当前结点的左孩子结点 Left child(I,cur) (5)查找树中当前结点的右孩子结点 Rightsibling(,cur (6)遍历树 Traverse(T,isi()
5 7.1.3 树的抽象数据类型 数据集合: 树的结点集合，每个结点由数据元素和构造数 据元素之间关系的指针组成。 操作集合: (1)创建树 MakeTree(T) (2)撤消树 DestroyTree(T) (3)查找树中当前结点的双亲结点 Parent(T,curr) (4)查找树中当前结点的左孩子结点 LeftChild(T,curr) (5)查找树中当前结点的右孩子结点 RightSibling(T,curr) (6)遍历树 Traverse(T,Visit( ))
7.1.4树的存储结构 树的结点之间的逻辑关系主要有双亲-孩子关系, 兄弟关系。因此,从结点之间的逻辑关系分,树的存 储结构主要有:双亲表示法、孩子表示法、双亲孩子 表示法和孩子兄弟表示法四种组合
6 7.1.4 树的存储结构 树的结点之间的逻辑关系主要有双亲-孩子关系， 兄弟关系。因此，从结点之间的逻辑关系分，树的存 储结构主要有：双亲表示法、孩子表示法、双亲孩子 表示法和孩子兄弟表示法四种组合
1、双亲表示法 B D 100 C 0123456 dABCDEFGH (a)一棵树 (b)仿真指针的双亲表示法存储结构 图72树的双亲表示法存储结构
7 A -1 B 0 C 0 D 1 E 1 F 1 G 2 H 3 A B C E G D F H 1、双亲表示法 d p 0 1 2 3 4 5 6 (a)一棵树 （b)仿真指针的双亲表示法存储结构 图7.2 树的双亲表示法存储结构
2、孩子表示法 LOral 0 B 0 0∠C0 OIDNOIE11F1LG1 H□1[1I1 图73树的孩子法存储结构
8 0 A 0 0 B 0 0 C 0 0 1 E 1 1 F 1 1 G 1 D 0 1 H 1 1 I 1 2、孩子表示法 图7.3 树的孩子法存储结构
从上面看出,树的操作实现比较复杂。 解决思路:先研究最简单、最有规律的树,然 后设法把一般的树转化为简单树。 最简单的树一 又树
9 最简单的树———二叉树 先研究最简单、最有规律的树，然 后设法把一般的树转化为简单树。 解决思路： 从上面看出，树的操作实现比较复杂
补充:树的5种表示法: 心图形表示法 令嵌套集合表示法 广义表表示法 凹入表示法 令左孩子-右兄弟表示法
补充：树的5种表示法： ❖ 图形表示法 ❖ 嵌套集合表示法 ❖ 广义表表示法 ❖ 凹入表示法 ❖ 左孩子－右兄弟表示法