长春理工大学计算机应用基础课件：第4章(5).数据结构5――树.0..pptVIP

第 4 章　 数据结构 4.1 基本数据结构与算法 4.2 线性表 4.3 栈和队列 4.4 树和二叉树 4.5 查找 4.6 内部排序 1）在一棵二叉树上第4层的结点数最多是______。 A.4 B.8 C.32 D.12 2) 在深度为5的满二叉树中，叶子结点的个数为______。 A.32 B.31 C.16 D.15 3) 在深度为5的二叉树中，至多有______个结点。 A.32 B.31 C.16 D.15 4）在具有10 个结点的树中，其边的树目为______。 A.11 B.10 C.8 D.9 5）设一棵完全二叉树共有10个结点，则在该二叉树中的叶 子结点数为______。 A.9 B.5 C.2 D.4 6 设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数是______。 A.12 B.13 C.14 D.15 7.下面关于完全二叉树的叙述中，错误的是______。 A. 除了最后一层外，每一层上结点数均达到最大值 B. 可能缺少若干个左右叶子结点 C. 完全二叉数一般不是满二叉数 D. 具有结点的完全二叉树的深度为[log2n]+1 8.对于所示的二叉树，其后序遍历序列是______。 A. ABDECFG B. DEBAFCG C. DEBFGCA D. GFCEBDA 9. 在深度为7的满二叉树中， 叶子结点的个数为___。 (06.4月） A)32 B) 31 C) 64 D) 63 10.对如下二叉树，进行后序遍历的结果为______。（06.4月 ) A)ABCDEF B)DBEAFC C)ABDECF D)DEBFCA 12.对如下a图二叉树，进行中序遍历的结果为______。（06.9月) A)ACBDFEG B) ACBDFGE C) ABDCGEF D) FCADBEG 13.结论“__________”是正确的 A. 二叉树的度为2 B. 树中结点的度可以小于2 C. 二叉树中至少有一个结点的度为2 D. 二叉树中任何一个结点的度为2 15. 已知二叉树后序遍历序列是dabec， 中序遍历序列是debac，它的前序遍历序列是______。 A. cedba B. acbed C. decab D. deabc 二叉树在树结构的应用中起着非常重要的作用，因为对二叉树的许多操作算法简单，而任何树都可以与二叉树 相互转换，这样就解决了树的 存储结构及其运算中存在的复杂性。 二叉树在树结构的应用中起着非常重要的作用，因为对二叉树的许多操作算法简单，而任何树都可以与二叉树 相互转换，这样就解决了树的 存储结构及其运算中存在的复杂性。 在二叉树的一些应用中，常常要求在树中查找具有某 种特征的结点，或者对树中全部结点逐一进行某种处 理。这就引入了遍历二叉树的问题，即如何按某条搜 索路径巡访树中的每一个结点，使得每一个结点均被 访问一次，而且仅被访问一次。 遍历对线性结构是容易解决的，而二叉树是非线性的， 因而需要寻找一种规律，以便使二叉树上的结点能排 列在一个线性队列上，从而便于遍历。 在二叉树的一些应用中，常常要求在树中查找具有某 种特征的结点，或者对树中全部结点逐一进行某种处 理。这就引入了遍历二叉树的问题，即如何按某条搜 索路径巡访树中的每一个结点，使得每一个结点均被 访问一次，而且仅被访问一次。 遍历对线性结构是容易解决的，而二叉树是非线性的， 因而需要寻找一种规律，以便使二叉树上的结点能排 列在一个线性队列上，从而便于遍历。 * A B C D E F G 姓名 学号 成绩 班级 李红 9761059 95 机97.6 10 65 865 A C G T2 D H I T3 J M B E L K T1 F 树型结构是一类重要的非线性数据结构，元素结点间存在明显的分支和层次关系。现实世界中，能用树的结构表示的例子：学校的行政关系、书的层次结构、人类的家族血缘关系等。 4.4 树与二叉树 4.4.1 树的定义和基本术语 1.树的定义 概念：树是n（n≥0）个结点构成的有限集合。n=0为空树；n≠0时，树中结点应该满足两个条件