第6章树和二叉树61和ppt课件.ppt

《第6章树和二叉树61和ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、复习回顾线性结构（线性表、栈、队列、串）特点：数据元素之间的逻辑结构是1:1数据元素之间相互独立（不存在依赖关系）除头结点和尾结点外每个结点都有且只有一个直接前驱和一个直接后继。张三李四提出问题数据元素之间是1：1关系吗？1:n数据元素之间是相互独立的吗？数据元素之间存在依赖关系数据结构课程的内容逻辑结构线性结构（线性表、栈、队、串、数组）非线性结构树结构图结构储存结构顺序结构链式结构数据运算插入运算删除运算查找运算修改运算......3第6章树和二叉树教学内容6.1树的定义和基本术语树和森林的概念（树的定

2、义、树的术语、性质及运算）6.2二叉树（★★★★★）二叉树的定义、性质及运算；二叉树的存储结构（顺序、链式表示）；6.3遍历二叉树和线索二叉树（★★★★★）6.4树和森林树的存储结构；树、森林与二叉树的转换；遍历树；遍历森林；6.6赫夫曼树及其应用（★★★★）哈夫曼树、哈夫曼编码。6.1树的定义和基本术语6.1.1树的定义6.1.2树的逻辑结构6.1.3树的若干术语66.1.1树的定义注:树的定义具有递归性，即“树中还有树”。树是由n个结点组成的有限集合（记为T）；若n=0，是一棵空树；若n>0，有且仅有一

3、个结点称为根（root），其余的结点分为m（m≥0）个互不相交的有限集T1，T2，…，Tm，每个集合本身又是棵树，称为根结点的子树。TiT2T1TmTroot76.1.2树的逻辑结构树是一种非线性数据结构（一对多，1:n)，每一结点可以有后继结点，但前驱结点（根结点除外）。树只有一个，且子树之间互不相交。零个或多个有且只有一个根结点8结点的度：结点拥有的子树数。度=0叶子终端结点度=3分支结点非终端结点树的度：树内各结点的度的最大值。双亲直接前驱孩子直接后继兄弟结点的祖先：从根到该结点所经分支上的所有结点。

4、结点的子孙：以某结点为根的子树中的任一结点。第1层第2层第3层树的深度/高度：树中结点的最大层次。有序树：树中结点的各子树从左至右有次序。无序树：树中结点的各子树无次序。结点：数据元素+指向子树的分支根结点：非空树中无前驱结点的结点EFGHIABCDJKLM第4层堂兄弟双亲在同一层的结点6.1.3树的若干术语6.1.3树的若干术语——课堂练习图中的结点数＝树的度＝树的深度＝133410自学：树的抽象数据类型定义（见教材P118-119）ADTTree{数据对象D:数据关系R:基本操作P：}ADTTreeD是

5、具有相同特性的数据元素的集合。若D为空集，则称为空树；//允许n=0若D中仅含一个数据元素，则R为空集；其他情况下的R存在二元关系：①root唯一//关于根的说明②Dj∩Dk=Φ//关于子树不相交的说明③……//关于数据元素的说明//至少有15个，如求树深，求某结点的双亲116.2二叉树颤抖吧，程序猿，真实的野生二叉树！为何要重点研究每结点最多只有两个“叉”的树？二叉树的结构最简单，规律性最强；可以证明，所有树都能转为唯一对应的二叉树，不失一般性。6.2二叉树6.2.1二叉树的定义6.2.2二叉树的性质6.

6、2.3二叉树的存储结构136.2.1　二叉树的定义是n（n≥0）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。一对二（1:2）①每个结点最多只有两棵子树（不存在度大于2的结点）；②左子树和右子树次序不能颠倒。问：具有3个结点的二叉树可能有几种不同形态？有5种基本形态：定义：逻辑结构：基本特征：14二叉树的抽象数据类型定义（见教材P121-123）ADTBinaryTree{数据对象D:数据关系R:基本操作P：}ADTBinaryTreeD是具有相同特性的数据元素的集合

7、。若D=Φ，则R=Φ；若D≠Φ，则R={H}；存在二元关系：①root唯一//关于根的说明②Dj∩Dk=Φ//关于子树不相交的说明③……//关于数据元素的说明④……//关于左子树和右子树的说明//至少有20个，如返回某结点的左孩子，或中序遍历，等等156.2.2　二叉树的性质（3+2）讨论1：第i层的结点数最多是多少？（利用二进制性质可轻松求出）性质1:在二叉树的第i层上至多有2(i-1)个结点（i>0）。性质2:深度为k的二叉树至多有2k-1个结点（k>0）。再提问：第i层上至少有个结点？1讨论2：深度为

8、k的二叉树，最多有多少个结点？（利用二进制性质可轻松求出）2i-1个2k-1个166.2.2　二叉树的性质（3+2）讨论3：二叉树的叶子数和度为2的结点数之间有关系吗？性质3:对于任何一棵二叉树，若2度的结点数有n2个，则叶子数（n0）必定为n2＋1（即n0=n2+1）物理意义：叶子数＝2度结点数＋1分支数记为d，结点数为0的结点个数记为n0，结点数为1的结点个数记为n1，结点数为2的结点个数记为n2n0+n1+