第5章树和二叉树

《第5章树和二叉树》由会员分享，可在线阅读，更多相关《第5章树和二叉树（95页珍藏版）》请在文档大全上搜索。

1、 Office: 西配楼西配楼304（软件教研室）（软件教研室）Email:北京林业大学信息学院北京林业大学信息学院北京林业大学信息学院北京林业大学信息学院线性结构一个对一个，如线性表、栈、队列树形结构一个对多个，如树集合数据元素间除“同属于一个集合”外，无其它关系图形结构多个对多个，如图逻辑结构逻辑结构北京林业大学信息学院北京林业大学信息学院第第5 5章树和二叉树章树和二叉树5.1 5.1 树和二叉树的定义树和二叉树的定义5.2 5.2 案例引入案例引入5.3 5.3 树和二叉树的抽象数据类型定义树和二叉树的抽象数据类型定义5.4 5.4 二叉树的性质和存储结构二叉树的性质和存储结构5.5

2、5.5 遍历二叉树和线索二叉树遍历二叉树和线索二叉树5.6 5.6 树和森林树和森林5.7 5.7 哈夫曼树及其应用哈夫曼树及其应用5.8 5.8 案例分析与实现案例分析与实现 北京林业大学信息学院北京林业大学信息学院1. 1. 掌握二叉树的基本概念、掌握二叉树的基本概念、性质性质和存储结构和存储结构2. 2. 熟练掌握二叉树的熟练掌握二叉树的前、中、后序遍历方法前、中、后序遍历方法3. 3. 了解了解线索化线索化二叉树的思想二叉树的思想4. 4. 熟练掌握熟练掌握：哈夫曼哈夫曼树树的实现方法、的实现方法、构造构造哈夫曼哈夫曼编码编码的方法的方法5. 5. 了解：森林与二叉树的转换，树的遍历方

3、法了解：森林与二叉树的转换，树的遍历方法教学目标教学目标北京林业大学信息学院北京林业大学信息学院5.1 5.1 树和二叉树的定义树和二叉树的定义树（树（TreeTree）是）是n n（n n0 0）个结点的有限集，它或为空树（）个结点的有限集，它或为空树（n n=0=0）；或为非空树，对于非空树；或为非空树，对于非空树T T：（1 1）有且仅有一个称之为根的结点；）有且仅有一个称之为根的结点；（2 2）除根结点以外的其余结点可分为）除根结点以外的其余结点可分为m m（m m0 0）个互不相交的）个互不相交的有限集有限集T T1 1, , T T2 2, , , , T Tm m, , 其中每一

4、个集合本身又是一棵树，并且称其中每一个集合本身又是一棵树，并且称为根的子树（为根的子树（SubTreeSubTree）。）。树的定义树的定义北京林业大学信息学院北京林业大学信息学院ACBGFEHIJDMKLA树是树是n n个结点的有限集个结点的有限集T1T2T3北京林业大学信息学院北京林业大学信息学院ACBGFEHIJDMKLAJIMHDGCFLKEB凹入表示凹入表示ABFEKLGCDHMIJ嵌套集合嵌套集合(A(B(E(K,L),F),C(G),D(H(M),I,J)广义表广义表树的其它表示方式树的其它表示方式北京林业大学信息学院北京林业大学信息学院 根根 叶子叶子 森林森林有序树有序树无序

5、树无序树即根结点即根结点(没有前驱没有前驱)即终端结点即终端结点(没有后继没有后继)指指m棵不相交的树的集合棵不相交的树的集合(例如删除例如删除A后的子树个数后的子树个数)结点各子树从左至右有序，不能互换（左为第一）结点各子树从左至右有序，不能互换（左为第一）结点各子树可互换位置。结点各子树可互换位置。ACBGFEHIJDMKL基本术语基本术语北京林业大学信息学院北京林业大学信息学院即上层的那个结点即上层的那个结点(直接前驱直接前驱)即下层结点的子树的根即下层结点的子树的根(直接后继直接后继)同一双亲下的同层结点（孩子之间互称兄弟）同一双亲下的同层结点（孩子之间互称兄弟）即双亲位于同一层的结点

6、（但并非同一双亲）即双亲位于同一层的结点（但并非同一双亲）即从根到该结点所经分支的所有结点即从根到该结点所经分支的所有结点即该结点下层子树中的任一结点即该结点下层子树中的任一结点双亲双亲孩子孩子兄弟兄弟堂兄弟堂兄弟祖先祖先子孙子孙ACBGFEHIJDMKL基本术语基本术语北京林业大学信息学院北京林业大学信息学院即树的数据元素即树的数据元素结点挂接的子树数结点挂接的子树数结点结点结点的度结点的度结点的层次结点的层次终端结点终端结点分支结点分支结点树的度树的度树的深度树的深度(或高度或高度)从根到该结点的层数（根结点算第一层）从根到该结点的层数（根结点算第一层）即度为即度为0的结点，即叶子的结点，

7、即叶子即度不为即度不为0的结点（也称为内部结点）的结点（也称为内部结点）所有结点度中的最大值所有结点度中的最大值指所有结点中最大的层数指所有结点中最大的层数ACBGFEHIJDMKL层次1234基本术语基本术语北京林业大学信息学院北京林业大学信息学院二叉树（二叉树（Binary TreeBinary Tree）是）是n n（n n0 0）个结点所构成的集合）个结点所构成的集合，它或为空树（，它或为空树（n n=0=0）；或为非空树，对于非空树）；或为非空树，对于非空树T T：（1 1）有且仅有一个称之为根的结点；）有且仅有一个称之为根的结点；（2 2）除根结点以外的其余结点分为两个互不相交的子

8、集）除根结点以外的其余结点分为两个互不相交的子集T T1 1和和T T2 2，分别称为，分别称为T T的左子树和右子树，且的左子树和右子树，且T T1 1和和T T2 2本身又本身又都是二叉树。都是二叉树。二叉树的定义二叉树的定义北京林业大学信息学院北京林业大学信息学院普通树（多叉树）若不转化为二叉树，则运算很难实现普通树（多叉树）若不转化为二叉树，则运算很难实现为何要重点研究每结点最多只有两个为何要重点研究每结点最多只有两个 “叉叉” 的树？的树？ 二叉树的结构最简单，规律性最强；二叉树的结构最简单，规律性最强； 可以证明，所有树都能转为唯一对应的二叉树，不可以证明，所有树都能转为唯一对应的

9、二叉树，不失一般性。失一般性。北京林业大学信息学院北京林业大学信息学院基本基本北京林业大学信息学院北京林业大学信息学院 练习练习5 5种种/2/2种种北京林业大学信息学院北京林业大学信息学院5.2 5.2 案例引入案例引入案例案例5.1 5.1 ：数据压缩问题：数据压缩问题将数据文件转换成由将数据文件转换成由0 0、1 1组成的二进制串，称之为编码。组成的二进制串，称之为编码。字符编码字符编码字符编码a00a0a0b01b10b01c10c110c010d11d111d111（a）等长编码方案）等长编码方案 （b）不等长编码方案）不等长编码方案1 （c）不等长编码方案）不等长编码方案2北京林业

10、大学信息学院北京林业大学信息学院案例案例5.2 5.2 ：利用二叉树求解表达式的值利用二叉树求解表达式的值以二叉树表示表达式的递归定义如下：以二叉树表示表达式的递归定义如下：（1 1）若表达式为数或简单变量，则相应二叉）若表达式为数或简单变量，则相应二叉树中仅有一个根结点，其数据域存放该表达树中仅有一个根结点，其数据域存放该表达式信息；式信息；（2 2）若表达式为）若表达式为“第一操作数第一操作数 运算符运算符 第二第二操作数操作数”的形式，则相应的二叉树中以左子的形式，则相应的二叉树中以左子树表示第一操作数，右子树表示第二操作数树表示第一操作数，右子树表示第二操作数，根结点的数据域存放运算符

11、（若为一元运，根结点的数据域存放运算符（若为一元运算符，则左子树为空），其中，操作数本身算符，则左子树为空），其中，操作数本身又为表达式。又为表达式。(a + b *(c-d)-e/f)的二叉树的二叉树北京林业大学信息学院北京林业大学信息学院5.3 5.3 树和二叉树的抽象数据类型定义树和二叉树的抽象数据类型定义ADT BinaryTree数据对象数据对象D:数据关系数据关系R:基本操作基本操作 P：ADT BinaryTree若若D=，则，则R= ；若若D，则，则R= H；存在二元关系：；存在二元关系： root 唯一唯一 /关于根的说明关于根的说明 DjDk= /关于子树不相交的说明关于子