电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

2025年高中信息技术竞赛班数据结构专项培训教程07树教案

2025年高中信息技术竞赛班数据结构专项培训教程07树教案_第1页
1/18
2025年高中信息技术竞赛班数据结构专项培训教程07树教案_第2页
2/18
2025年高中信息技术竞赛班数据结构专项培训教程07树教案_第3页
3/18
§7 树§7.1 树的概念【定义】 树(Tree)是 n(n>0)个结点的有限集合 T,它满足如下两个条件:(1) 有且仅有一种特定的称为根(Root)的结点;(2) 其他的结点可分为 m(m≥0)个互不相交的有限集合,其中每一种集合又都是一颗树,并称为根的子树(Sub Tree)。【基本术语】k1.树的结点包含一种数据元素及若干指向其子树的分支。 结点拥有的子树数称为结点的度(degree)。如图 7.1,A 的度为 3,C 的度为 1,F 的度为 0。2.度为 0 的结点称为叶子(leaf)或终端结点。例如 K、L、F、G、M、I、J。度不为 0 的结点称为分支结点或非终端结点。除根结点外,分支结点也称为内部结点。3.树的度是树内各结点的度的最大值,如图 7.1 中树的度为 3。4.结点的子树的根称为该结点的孩子(Child),该结点称为孩子的双亲(parent)。如图,B 为 A 的子树的根,则 B 是 A 的孩子,而 A 则是 B 的双亲。同一种双亲的孩子之间互称为兄弟(sibling),例如 B、C、D 互为兄弟。将这些关系深入推广,可认为 D 是 M 的祖父。结点的祖先是从根到该结点所经分支上的所有结点。例如,M 的祖先为 A、D、H。反之,结点的子树中的任一结点都称为该结点的子孙,如 B 的为 E、F、K、L。5. 结点的层次(level)是从根开始定义起,根为第一层,根的孩子为第二层。若某结点在第 x 层,则其子树的根就在 x+1 层。树中结点的最大层次称为树的高度或深度(depth)。如图 7.1 的树的深度为 4。6. 假如将树中的结点的各子树当作从左到右是有次序的(即不能互换),则称该树为 有序树,否则称为无序树。如图。 7.森林(forest)是 m(m≥0)棵互不相交的树的集合。§7.2 二叉树§ 二叉树的定义 图 图 两棵不一样的有序树 图二叉树(binary tree)是一种树型构造,它的每个结点至多只有二棵子树(即二叉树中不存在度不小于 2 结点),并且,二叉树的子树有左右之分,另一方面序不能任意颠倒。(如图) 满二叉树和完全二叉树是两种特殊形态的二叉树。 满二叉树是指深度为 k,且有 2k-1 个结点的二叉树。 完全二叉树是指深度为 k,有 n 个结点,当且仅当每一种结点都与深度为 k 的满二叉树中编号从 1 到 n 的结点一一对应时。§ 二叉树的性质性质 1:在二叉树的第 i 层上至多有 ① 个结点(i≥1)。性质 2:深度为 k 的二叉树至多有 ② 个结点(k≥1)。性质 3:对任意一棵二叉树,假如度...

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

2025年高中信息技术竞赛班数据结构专项培训教程07树教案

您可能关注的文档

确认删除?
VIP
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群
客服邮箱
回到顶部