数据结构（严蔚敏版)课件PPT资源-CSDN文库

共11个文件

ppt：9个

doc：1个

docx：1个

数据结构课件PPT

需积分: 10 121 浏览量 2009-02-23 23:45:17 上传评论收藏 1.08MB RAR 举报

资源推荐

资源详情

资源评论

收起资源包目录

package

date struction.rar （11个子文件）

folder

date struction

第五章树.PPT 1.99MB

第一章绪论.PPT 362KB

第三章栈和队列.PPT 491KB

数据结构实验.docx 24KB

第四章数组和广义表.PPT 573KB

SJJGZY1.PPT 303KB

第二章线性表.PPT 478KB

第六章图.PPT 1.23MB

第八章排序.PPT 431KB

第七章查找.PPT 241KB

《数据结构》教学大纲B08010.doc 36KB

第五章树

树是一类重要的非线性数据结构，是以分

支关系定义的层次结构

§

5.1 树的定义



定义



定义：树 (tree) 是 n(n>0) 个结点的有限集 T ，其中：



有且仅有一个特定的结点，称为树的根 (root)



当 n>1 时，其余结点可分为 m(m>0) 个互不相交的有限集 T

1,T2,……Tm ，其中每一个集合本身又是一棵树，称为根的子

树 (subtree)



特点：



树中至少有一个结点——根



树中各子树是互不相交的集合

A

只有根结点的树

A

B C D

E F G H I J

K L M

有子树的树

根

子树



基本术语



结点 (node)—— 表示树中的元素，包括数据项及若干

指向其子树的分支



结点的度 (degree)—— 结点拥有的子树数



叶子 (leaf)—— 度为 0 的结点



孩子 (child)—— 结点子树的根称为该结点的孩子



双亲 (parents)—— 孩子结点的上层结点叫该结点的 ~



兄弟 (sibling)—— 同一双亲的孩子



树的度——一棵树中最大的结点度数



结点的层次 (level)—— 从根结点算起，根为第一层，

它的孩子为第二层……



深度 (depth)—— 树中结点的最大层次数



森林 (forest)——m(m0) 棵互不相交的树的集合

A

B C D

E F G H I J

K L M

结点 A 的度： 3

结点 B 的度： 2

结点 M 的度： 0

叶子： K ， L ， F ， G ， M ， I ， J

结点 A 的孩子： B ， C ， D

结点 B 的孩子： E ， F

结点 I 的双亲： D

结点 L 的双亲： E

结点 B ， C ， D 为兄弟

结点 K ， L 为兄弟

树的度： 3

结点 A 的层次： 1

结点 M 的层次： 4

树的深度： 4

结点 F ， G 为堂兄弟

结点 A 是结点 F ， G 的祖先

§

5.2 二叉树



定义



定义：二叉树是 n(n0) 个结点的有限集，它或为空

树 (n=0) ，或由一个根结点和两棵分别称为左子树和

右子树的互不相交的二叉树构成



特点



每个结点至多有二棵子树 ( 即不存在度大于 2 的结点 )



二叉树的子树有左、右之分，且其次序不能任意颠倒



基本形态

A

只有根结点

的二叉树



空二叉树

A

B

右子树为空

A

B

左子树为空

A

B C

左、右子树

均非空

内容反馈

fengxi138

粉丝: 1
资源: 6

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip