上海交通大学:《离散数学》课程教学资源(PPT课件)第五章 树及二叉树 Algorithms and DataStrucstures

Algorithms and Datastrucstures:Trees 第五章树及二叉树 5.1树的定义和术语 5.2二叉树 5.3二叉树的遍历 5.4二叉树遍历的迭代器类 5.5中序穿线树(×) 5.6最优二叉树及其应用 5.7树和森林 1 ALDS
1 物料管理 ALDS 1 Algorithms and DataStrucstures:Trees 5.1 树的定义和术语 5.2 二叉树 5.3 二叉树的遍历 5.4 二叉树遍历的迭代器类 5.5 中序穿线树(×) 5.6 最优二叉树及其应用 5.7 树和森林 第五章 树及二叉树

Algorithms and Datastrucstures:Trees 5.1树的定义和术语 树是n(n≥1)个结点的有限集合T,并且满足: (1)有一个被称之为根(root)的结点; (2)其余的结点可分为m(m≥0)个互不相交的集合T1,T2,,Tm, 这些集合本身也是一棵树,并称它们为根结点的子树(Subree)。 每棵子树同样有自己的根结点。 D E M 2 ALDS
2 物料管理 ALDS 2 Algorithms and DataStrucstures:Trees 5.1 树的定义和术语 树是n (n≥1) 个结点的有限集合T,并且满足: (1)有一个被称之为根(root)的结点; (2)其余的结点可分为m(m≥0)个互不相交的集合Tl,T2,…,Tm, 这些集合本身也是一棵树,并称它们为根结点的子树(Subree)。 每棵子树同样有自己的根结点

D A K M 结点 兄弟结点 ·有序树 结点的度 祖先结点 ·无序树 ·叶子结点 ·子孙结点 森林 内部结点 ·结点所处层次 ·儿子结点 ·树的高度 ·父亲结点
•结点 •结点的度 •叶子结点 •内部结点 •儿子结点 •父亲结点 •兄弟结点 •祖先结点 •子孙结点 •结点所处层次 •树的高度 •有序树 •无序树 •森林

Algorithms and Datastrucstures:Trees 树的定义的形式化描述 树的定义还可形式化的描述为二元组的形式: T=(D,R) 其中D为树T中结点的集合,R为树中结点之间关系的集合。 D={Root}UDp 其中,Root为树T的根结点,D为树T的根Root的子树集合。D可由下式表示: Dp=D1UD2U.UDm且D:nD;=Φ(i≠j,1≤i≤m,1≤j≤m) 当树T中结点个数n=1时,R=Φ;当树T中结点个数n>1时有: R={,i=1,2,...m} 其中,Root为树T的根结点,r:是树T的根结点Root的子树T:的根结点。 4 ALDS
4 物料管理 ALDS 4 Algorithms and DataStrucstures:Trees 树的定义的形式化描述 树的定义还可形式化的描述为二元组的形式: T=(D,R) 其中D为树T中结点的集合,R为树中结点之间关系的集合。 D={Root}∪DF 其中,Root为树T的根结点,DF为树T的根Root的子树集合。DF可由下式表示: DF =D1∪D2∪…∪Dm且Di∩Dj =Φ(i≠j,1≤i≤m,1≤j≤m) 当树T中结点个数n=1时,R=Φ;当树T中结点个数n > 1时有: R={,i=1,2,…,m} 其中,Root为树T的根结点,ri是树T的根结点Root的子树Ti的根结点

Algorithms and Datastrucstures:Trees 树的数学定义 树:连通无回路的无向图 不是树 有回路 a 不是树 不连通 5 ALDS
5 物料管理 ALDS 5 Algorithms and DataStrucstures:Trees a b 不是树 有回路 a b 不是树 不连通 a b 树的数学定义 树:连通无回路的无向图

Algorithms and Datastrucstures:Trees 树的数学定义 有向树:有向图在不考虑边的方向时是一棵树,该有向图称为有向树。 根树:一颗有向树,如果恰有一个结点的入度为0,其余所有结点的入 度都为1,则称为根树。 R S T W X Z b ALDS
6 物料管理 ALDS 6 Algorithms and DataStrucstures:Trees 树的数学定义 有向树:有向图在不考虑边的方向时是一棵树,该有向图称为有向树。 根树:一颗有向树,如果恰有一个结点的入度为0,其余所有结点的入 度都为1,则称为根树。 R S T U V Y W X Z

Algorithms and Datastrucstures:Trees 树的ADT 数据及关系: 具有相同数据类型的数据元素或结点的有限集合。树T的二元组形式为: T=(D,R) 其中D为树T中结点的集合,R为树中结点之间关系的集合。 D={Root}UDp 其中,Root为树T的根结点,D为树T的根Root的子树集合。 R={,i=1,2,...m} 其中,r是树T的根结点Root的子树T,的根结点。 7 ALDS
7 物料管理 ALDS 7 Algorithms and DataStrucstures:Trees 树的ADT 数据及关系: 具有相同数据类型的数据元素或结点的有限集合。树T的二元组形式为: T=(D,R) 其中D为树T中结点的集合,R为树中结点之间关系的集合。 D={Root}∪DF 其中,Root为树T的根结点,DF为树T的根Root的子树集合。 R={,i=1,2,…,m} 其中,ri是树T的根结点Root的子树Ti的根结点

Algorithms and Datastrucstures:Trees 树的ADT 操作: Constructor: 前提:已知根结点的数据元素之值。 结果:创建一棵树。 Getroot: 前提:已知一棵树。, 结果:得到树的根结点。 FirstChild: 前提:已知树中的某一指定结点p。 结果:得到结点p的第一个儿子结点。 NextChild: 前提:已知树中的某一指定结点p和它的一个儿子结点u。 结果:得到结点p的儿子结点u的下一个兄弟结点V。 8 ALDS
8 物料管理 ALDS 8 Algorithms and DataStrucstures:Trees 树的ADT 操作: Constructor: 前提:已知根结点的数据元素之值。 结果:创建一棵树。 Getroot: 前提:已知一棵树。. 结果:得到树的根结点。 FirstChild: 前提:已知树中的某一指定结点 p。 结果:得到结点 p 的第一个儿子结点。 NextChild: 前提:已知树中的某一指定结点 p 和它的一个儿子结点 u。 结果:得到结点 p 的儿子结点 u 的下一个兄弟结点 v

Algorithms and Datastrucstures:Trees 树的ADT 操作: Retrieve: 前提:已知某一关键字key。 结果:检索具有关键字key的结点v。 InsertChild: 前提:已知某结点p及新结点的数据值value.。 结果:根据value值创建一个新结点q, 并将其插入作为结点p的儿子结点。 DeleteChild: 前提: 己知某结点p及它的儿子结点的序号k。 结果:删除结点p的第k个儿子结点。 IsEmpty: 结果:若树仍未创建,返回True,否则返回False。 9 ALDS
9 物料管理 ALDS 9 Algorithms and DataStrucstures:Trees 树的ADT 操作: Retrieve: 前提:已知某一关键字 key。 结果:检索具有关键字 key 的结点 v。 InsertChild: 前提:已知某结点 p 及新结点的数据值 value。 结果:根据 value 值创建一个新结点 q, 并将其插入作为结点 p 的儿子结点。 DeleteChild: 前提:已知某结点 p 及它的儿子结点的序号 k。 结果:删除结点 p 的第 k 个儿子结点。 IsEmpty: 结果:若树仍未创建,返回 True,否则返回 False

Algorithms and Datastrucstures:Trees 5.2二叉树 二叉树在树结构的应用中起着非常重要的作用,因为对二叉树的 许多操作算法简单,而任何树都可以与二叉树相互转换,这样就解决 了树的存储结构及其运算中存在的复杂性。 5.2.1二叉树的定义 定义:二叉树(Binary Tree)是结点的有限集合,它或者为空,或者 由一个根结点及两棵互不相交的左、右子树构成,而其左、右子树又都 是二叉树。 这也是一个递归定义。二叉树可以为空,根的左、右子树都可以为 空。必须注意的是,二叉树不是树的特殊情况,它们是两种不同的数据 结构。若将二叉树的左、右子树颠倒,就成为另一棵不同的二叉树。 即使二叉树中的根结点只有一棵子树,也要说明该子树是左子树,还是 右子树。这是二叉树与树的最主要的差别。 10 ALDS
10 物料管理 ALDS 10 Algorithms and DataStrucstures:Trees 5.2 二叉树 二叉树在树结构的应用中起着非常重要的作用,因为对二叉树的 许多操作算法简单,而任何树都可以与二叉树 相互转换,这样就解决 了树的存储结构及其运算中存在的复杂性。 5.2.1 二叉树的定义 定义:二叉树(Binary Tree)是结点的有限集合,它或者为空,或者 由一个根结点及两棵互不相交的左、右子树构成,而其左、右子树又都 是二叉树。 这也是一个递归定义。二叉树可以为空,根的左、右子树都可以为 空。必须注意的是,二叉树不是树的特殊情况,它们是两种不同的数据 结构。 若将二叉树的左、右子树颠倒,就成为另一棵不同的二叉树。 即使二叉树中的根结点只有一棵子树,也要说明该子树是左子树,还是 右子树。这是二叉树与树的最主要的差别
按次数下载不扣除下载券;
注册用户24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
- 上海交通大学:《离散数学》课程教学资源(PPT课件)第七章 图.ppt
- 上海交通大学:《离散数学》课程教学资源(试卷习题)历届考试试题_试卷(A卷)答案.doc
- 上海交通大学:《离散数学》课程教学资源(试卷习题)历届考试试题_试卷(A卷)试卷.doc
- 上海交通大学:《离散数学》课程教学资源(讲义)第五章 谓词逻辑的等值和推理演算.pdf
- 上海交通大学:《离散数学》课程教学资源(讲义)第二章 题逻辑的等值与推理演算.pdf
- 上海交通大学:《离散数学》课程教学资源(讲义)第一章 命题逻辑的基本概念.pdf
- 上海交通大学:《离散数学》课程教学资源(讲义)第一章 命题逻辑的基本概念.pdf
- 清华大学计算机系列教材:《离散数学——数理逻辑与集合论》教学资源(石纯一、王家廞).pdf
- 上海交通大学:《离散数学》课程教学资源(讲义)图论——第二章 道路与回路.pdf
- 上海交通大学:《离散数学》课程教学资源(讲义)图论——第三章 树.pdf
- 上海交通大学:《离散数学》课程教学资源(讲义)图论——第一章 图的基本概念.pdf
- 《离散数学》教学资源(图论与代数系统)PDF电子教学资料.pdf
- 上海交通大学:《离散数学》课程教学资源(讲义)第四章 谓词逻辑的基本概念.pdf
- 上海交通大学:《离散数学》课程教学资源(讲义)第五章 谓词逻辑的等值和推理演算.pdf
- 上海交通大学:《离散数学》课程教学资源(讲义)第二章 命题逻辑的等值与推理.pdf
- 上海交通大学:《离散数学》课程教学资源(讲义)图论——第二章 道路与回路.pdf
- 上海交通大学:《离散数学》课程教学资源(讲义)图论——第三章 树.pdf
- 上海交通大学:《离散数学》课程教学资源(讲义)图论——第一章 基本概念.pdf
- 上海交通大学:《离散数学》课程教学资源(讲义)错误汇总(补充2,主讲:刘胜利).doc
- 上海交通大学:《离散数学》课程教学资源(讲义)图论——第四章(平面图与图的着色).pdf
- 上海交通大学:《离散数学》课程教学资源(PPT课件)第二章 命题逻辑的等值和推理演算.ppt
- 上海交通大学:《离散数学》课程教学资源(PPT课件)第5章 谓词逻辑的等值和推理演算.ppt
- 上海交通大学:《离散数学》课程教学资源(PPT课件)Introduction(主讲:陈玉泉).ppt
- 上海交通大学:《离散数学》课程教学资源(PPT课件)命题逻辑的推理.pdf
- 上海交通大学:《离散数学》课程教学资源(PPT课件)第四章 平面图与图的着色.ppt
- 《离散数学》课程教学资源(线性代数 linear algebra)英文教材PDF电子版.pdf
- 上海交通大学:《线性规划与非线性规划》教学资源_ILOG实验指导_ILOG ODMS上机实验指导.ppt
- 上海交通大学:《线性规划与非线性规划》教学资源_ILOG实验指导_优化软件ILOG_OPL.ppt
- 上海交通大学:《线性规划与非线性规划》教学资源_ILOG实验指导_接受实验报告邮箱地址.pptx
- 上海交通大学:《线性规划与非线性规划》教学资源_ILOG实验指导_注册激活我们的ILOG方法.pptx
- 上海交通大学:《线性规划与非线性规划》教学资源_ILOG实验指导_运筹学实验指导书(2012-10).doc
- 上海交通大学:《线性规划与非线性规划》教学资源_Matlab优化函数_linprog.pdf
- 上海交通大学:《线性规划与非线性规划》教学资源_Matlab优化函数_MATLAB初步_优化2003.doc
- 上海交通大学:《线性规划与非线性规划》教学资源_Matlab优化函数_NLP-ex.pdf
- 上海交通大学:《线性规划与非线性规划》教学资源_非线性规划、无约束问题.pdf
- 上海交通大学:《线性规划与非线性规划》教学资源_第1章 线性规划与单纯形法 第1节 线性规划问题及其数学模型.pdf
- 上海交通大学:《线性规划与非线性规划》教学资源_第1章 线性规划与单纯形法 第2节 线性规划问题的几何意义.pdf
- 上海交通大学:《线性规划与非线性规划》教学资源_第1章 线性规划与单纯形法 第3节 单纯形法.pdf
- 上海交通大学:《线性规划与非线性规划》教学资源_第1章 线性规划与单纯形法 第4节 单纯形法的计算步骤.pdf
- 上海交通大学:《线性规划与非线性规划》教学资源_第1章 线性规划与单纯形法 第5节 单纯形法的进一步讨论.pdf