4.2 二叉树的基本操作（分层作业）信息技术浙教版2019选择性必修1

4.2二叉树的基本操作 1课时（分层作业） 【基础达标】 1.二叉树也可以采用 来实现，用任意一组存储单元来存储二叉树的 ，用指向节点的指针来表示节点之间的关系。 2.二叉树的节点可能有两个孩子，即 和 ，因此二叉树的节点至少需要 个域： 和 。两个指针域分别指向节点的左孩子和右孩子，这两个指针分别称为 和 ，这样得到的链表也称为 。 3.二叉树节点可以看成一个 ，元素是 和 。 4.前序遍历的规则是：若二叉树为空，则空操作返回；否则，先访问根节点，再访问 ，最后访问 。 5.中序遍历的规则是：若二叉树为空，则空操作返回；否则，先访问 ，再访问根节点，最后访问 。 6.后序遍历的规则是：若二叉树为空，则空操作返回；否则，先访问 ，再访问 ，最后访问 。 7.层序遍历的规则：若二叉树为空，则空操作返回；否则，从 开始，自 而 ，从 往 遍历。 8.一棵二叉树的中序遍历序列为“dbgehafic"，后序遍历序列为“dghebifca"，则该二叉树的前序遍历序列是 。 9.一棵二叉树的前序遍历序列为“abdgecf'，中序遍历序列为“gdbeacf'，则该二叉树的后序遍历序列是 。 10.某二叉树如下图所示,请回答下列问题。 (1)该二叉树的深度为 。 (2)写出该二叉树的前序遍历、中序遍历和后序遍历。 前序遍历序列为: 。 中序遍历序列为: 。 后序遍历序列为: 。 【巩固提升】 1.某二叉树如下图所示，请用链表来实现。 2.观察如图所示的树形结构示意图,请回答下列问题: (1)该树共有 个节点， 条边。 (2)根节点的名称是 ，它有 个孩子节点,节点E (选填：是/不是)根节点的孩子节点。 (3)节点A和节点B的度分别是 ，整棵树的度是 。 (4)该树的分支节点的数量是 ，叶子节点的数量是 。 (5)节点C的层数是 ，树的深度是 。 (6)节点D的父节点是 ，兄弟节点是 ，孩子节点是 。 3.某二叉树的树形结构如下图所示，后序遍历结果为“WUSVTR”，则该二叉树的前序遍历结果为（   ） A．RSTUVW B．RTSVUW C．RTSUWV D．RSUWTV 4.某二叉树的树形结构如第8题图所示，其后序遍历结果为“物技化数英语”，则中序遍历结果为() A.语数英物化技 B.物数技化语英 C.语数物化技英 D.化物技英数语 5.某二叉树的前序遍历为+*a-bc/df，中序遍历为a*b-c+d/f，下列说法正确的是（   ） A．该二叉树的叶子节点有2个 B．该二叉树为完全二叉树 C．该二叉树的后序遍历是abc-*df/+ D．若abcdf的值分别为3、2、5、6、3，则该表达式的运算结果为4 6.已知某二叉树的前序遍历结果为ABCDEF中序遍历结果为CBDAEF，则下列说法正确的是( ) A.其后序遍历结果为DCBFEA B.该二叉树为完全二叉树 C.该二叉树深度为3，叶子节点数为3 D.该二叉树用一维数组实现需要6个节点的存储空间才能表示 7.前序遍历与后序遍历得到的序列相同的二叉树为 A.只有左子树的二叉树 B.只有右子树的二叉树 C.满二叉树 D.只有根节点的二叉树 8.某二叉树对应的一维数组表示如图所示: 1 2 3 4 5 6 A B C D E 下列关于该二叉树的说法正确的是() A.该二叉树的度为3 B.该二叉树有2个叶子节点 C.该二叉树是一棵完全二叉树 D.该二叉树前序遍历结果为ABCDE 9.已知一棵完全二叉树共有5个节点，前序遍历为ABCDE，下列说法正确的是（   ） A.该二叉树的高度为3 B.该二叉树中只有1个度为2的节点 C.节点C的父节点是A D.该二叉树共有2个叶子节点 10.某二叉树从根节点开始，按从上到下、自左往右的顺序用A -G字母表示，若补全为完全二叉树后，用一维数组表示如图所示。 0 1 2 3 4 5 6 7 8 9 10 A B C D E F G 下列关于该二叉树的说法，正确的是( ) A.该二叉树的深度为3 B.节点E的父节点是B C.该二叉树的中序遍历结果为BFDGACE D.该二叉树的叶子节点为D、E、F、G 11.已知一棵完全二叉树共有200个节点，下列说法正确的是() A.该完全二叉树的高度为7 B.该完全二叉树有99个叶子节点 C.该完全二叉树有100个度为2的节点 D.该完全二叉树有1个度为1的节点 12.已知某二叉树的后序遍历为GDBEHFCA，中序遍历为DGBAECHF，下列说法正确的是(） A.该二叉树中叶子节点有3个 B.该二叉树的前序遍历为ABDGCEHF C.该二叉树是一棵完全二叉树，树的高度为4 D.该二叉树中度为1的节点有2个 13.有一棵二叉树，如第下图所示，下列说法正确的是( ) A.此二叉树是完全二叉树 B.此二叉树的叶子节点有3个 C.此二叉树的后序遍历为F-D-B-E-C-A D.此二叉树用一维数组表示为['A’，’B，'E，'F’] 【链接高考】 1.用数组表示二叉树的示意图如下所示: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 B D A E F C 下列说法正确的是() A.该二叉树的深度为3 B.该二叉树是完全二叉树 C.该二叉树有4个叶子节点 D.该二叉树后序遍历的结果为DCEFAB 2.某二叉树如图所示，下列说法正确的是() A.该二叉树是完全二叉树 B.该二叉树有4个叶子节点 C.该二又树的中序遍历结果为BDACFE D.该二又树用一维数组表示为['A', 'B', 'C', 'D','E','F'] 3.某二叉树的树形结构如图所示，其中序遍历结果为FDGBAEC。若补全为完全二叉树后按从上到下、自左往右的顺序用一维数组a存储，其中根节点存储于元素a[0]中，则元素a[6]的值为（   ） A．D B．F C．G D．C 4.已知某二叉树的前序遍历结果为ABCDEP中序遍历结果为CBDAEF，则下列说法正确的是() A.其后序遍历结果为DCBFEA B.该二叉树为完全二叉树 C.该二叉树深度为3，叶子节点数为3 D.该二叉树用一维数组实现需要6个节点的存储空间才能表示 5.如图所示，一个数学表达式可以用一棵表达式树来表示。关于该表达式树，下列描述正确的是（   ） A．该表达式树不是一棵满二叉树 B．该表达式树中度为2的节点比叶子节点多一个 C．该表达式树的中序遍历序列为1 + 6 - 2 * 3 D．该表达式树的后序遍历序列为1 6 + - 2 3 * 6.某二叉树如下图所示,用数组来表示为 A. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 a b c d e f g h B. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 a b c d e f g h C. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 a b c d e f g h D. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 a b c d e f g h 7.某二叉树用一维数组来表示如表所示。该二叉树从根节点开始，按照从上到下，从左到右的顺序依次用A-H字母表示，该二叉树的中序遍历为() 下标 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 元素 A B C D E F G H A.DBGEACFH B.DBGEACHF C.DBEGACHF D.ABCDEFGH 8.若一棵二叉树的中序遍历序列为BIGDHAECF，后序遍历序列为IGHDBEFCA，则该二叉树的前序遍历序 列为（ ） A.ABCDEFCHI B.ABDCHICEF C.ABDHGICEF D.ABDGIHCEF 9.完全二叉树的节点个数为4*N+3,则它的叶子节点个数为 A.2*N C. 2*N+1 B.2*N-1 D.2*N+2 参考答案 【基础达标】 1.链表、节点、 2.左孩子、右孩子、3、一个数据域、两个指针域、左指针、右指针、二叉链表 3.三元组、左.右子树、本节点数据 4.左子树右子树 5.左子树、右子树 6.左子树、右子树、根节点 7.根节点、上、下、左、右 8.【答案】abdeghcfi [解析]根据后序遍历序列为“dghebica”,中序遍历序列为“dbgehafe”可知,二叉树的根节点为a,在中序遍历序列中找到节点a,a节点前面部分为左子树的节点(dbgeh),a节点后面部分为右子树的节点(fe)。分析可得二叉树如下图所示: 根据前序遍历的规则容易得到该二叉树的前序遍历序列:abdeghcfi 。 9.【答案】gdebfca [解析]根据前序遍历序列abdgecf可知，该二叉树的根节点为a,然后在中序遍历序列中找到根节点a，根节点a前面部分为左子树的节点序列(gdbe)，后面部分为右子树的节点序列(cf)。然后对左子树进行处理，在前序遍历中找到左子树序列为bdge,可知左子树中的根节点为b,在中序遍历中找到b节点，可知gd为b节点的左子树，在前序遍历序列中d结点在g结点前面，因此b节点的左孩子节点为d,在中序遍历中的序列为gd,可知g为d节点的左孩子，用同样的方法再对右子树进行处理，这样就可以得到它的后序遍历的序列。 10.【答案】(1)5(2)abdhecfijkg、hdbeaifkcg、hdebikjfgca [解析]（1）本题主委考查的是二叉树的深度和遮历。(1)谊二叉树共有5层,根节点的深度为1,因此该二义树的深度为5。 (2)二叉树的前序遍历的規则是先访问穗节点,然后访问左子树,最后访问右子树,对左子树和右子树仍按上述规则访问,因此前序透历序列为“sbdhecfikg”；中序遍历的规则是先访问左子树,然后访问粮节点,最后访问右子树,因北中序遍历序列为“hdbcaifkcg”；后序遍历的规则是先访问左子树,然后访问右子树,最后访问根节点,因此后序遍历序列为"hdebikjfgca"。 【巩固提升】 1.【答案】 [解析]实现二叉树的链表需要三个域,一个数据域和两个指针域，左指针指向左孩子，右指针指向右孩子。 2.【答案】(1)10；9(2)A；3；不是(3)3、3；3 (4)4；6(5)2；3(6)A；BC；IJ [解析](1)该树共有10个节点,9条边。(2)根节点的名称是A,它共有BC、D3个孩子节点,因为节点E与 节点A没有直接相连,故节点E不是根节点A的孩子节点,但可以称节点E为节点A的子孙节点,相应地可以称节点A为节点E的祖先节点。(3)节点A和节点B的度均为3.树的度也是3。(4)树的分支节点为节点A、B.CD,共4个;叶子节点为节点E、FGHIJ,共6个。(5)节点C的层数是2,树的深度是3。(6)节点D的父节点是A.兄弟节点是B和C,孩子节点是1和J。 3.【答案】D [解析]后序遍历就是左子树--->右子树>根结点，根据这一规则，书写规则为 故其前序遍历序列为:RSUWTV，故选D。 4.【答案】B [解析]后续就是左子树--->右子树--->根结点，所以根节点为语，可排除选项AC，由于右子树只有一个节点，所以为英，可排除选项D。故选:B。 5.【答案】C [解析]本题主要考查二叉树的遍历。由前序遍历以及中序遍历，可画出该二叉树，由二叉树可知，该二叉树的叶子节点有5个;不是完全二叉树;该二叉树的后序遍历是abc-*df+;若abcdf的值分别为3、2、5、6、3，则该表达式的运算结果为3.0，故本题选C选项。 6.【答案】C [解析]某二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBDAEF，某其后序遍历结果为CBDFEA;该二叉树不是完全二叉树;该二叉树深度为3，叶子节点数为3，所以选项C符合题意。故选:C。 7.【答案】D [解析]根据前序遍历与后序遍历的规则可知,前序遍历与后序遍历得到的序列相同的二叉树,只有一种情况,就是只有根节点的二叉树。 8.【答案】B [解析]二叉树的度是指树中所有节点的度的最大值，此二叉树中节点的最大度为2，4错误;叶子节点是度为0的节点，这里只有节点D和B是叶子节点，有2个，B正确;完全二叉树是指除最后一层外，每一层上的节点数均达到最大值，且在最后一层上只缺少右边的若干节点，此二又树不符合完全二叉树定义，C错误;前序遍历应该是先访问根节点4，然后是左子树B，再是右子树C，D是B的子节点，E是D的子节点，所以前序遍历结果为ABDCE，D错误。故选:B。 9.【答案】A [解析]一棵完全二叉树共有5个节点，前序遍历为ABCDE，所以该二叉树的高度为3，该二叉树中只有2个度为2的节点;该二叉树共有3个叶子节点，所以选项A说法正确。故选:A。 10.【答案】C [解析]该二叉树如下，由图可知，该二又树的深度为4;节点卫的父节点是C;该二叉树的中序遍历结果为BFDGACE;该二叉树的叶子节点为E、F、G。 故选C。 11.【答案】D [解析]完全二叉树的性质可以知道:叶子节点肯定在最后两层上，所以先计算出树的深度为8，前七层一共有127个节点，所以第8层有73个节点且都为叶节点，第七层有64个节点，第八层的13个节点的父节点在第七层，占据37个，所以总共叶节点为:73+(64-37)=100个;根据二叉树的性质:对于一棵非空的二叉树，如果叶子节点数为n0，度为2的结点数为n2，则no=n2十1，所以度为2的节点有100-1=99个;所以选项D符合意。故选:D。 12.【答案】A [解析]根据题意，可以构建出二叉树。该二叉树的前序遍历为ABDGCEFH。不是完全二叉树，该二叉树中度为1的节点有3个，所以选项A说法正确。故选:A。 13.【答案】C [解析]4选项，观察此图，结合完全二叉树的定义发现该二叉树不是完全二叉树，A错误;该二又树的叶子节点有2个，不是3个，B错误;C选项，按照后序遍历(左右根)规则，该二叉树后序遍历序列为:FDBECA，正确。D选项，观察一维数组可以发现，B节点的孩子为D、E节点，这不符合二叉树图示，D错误。故选:C。 【链接高考】 1.【答案】D [解析]依据题意可知二叉树为: 故其深度为4;不是完全二叉树;该二叉树有3个叶子节点;该二叉树后序遍历的结果为DCEFAB。故选:D。 2.【答案】C [解析]一棵完全二叉树至多只有最下面两层的结点的度数可以小于2，并且最下层的结点都集中在该层最左边的若干位置上，故选项A说法错误;叶子节点有2个，选项B说法错误;该树用数组表示为['A'，B’，'℃，None，'D',None,'E',None, None, None, None,None，None，'F]，选项D说法错误。故选:C。 3.【答案】D [解析]根据中序遍历，补全二叉树: 可知a=[B，G，E“，A，C，“，D。故a6]的值为:C.故选:D。 4.【答案】C [解析]某二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBDAEF，某其后序遍历结果为CBDFEA;该二叉树不是完全二叉树;该叉树深度为3，叶子节点数为3，所以选项C符合题意。故选:C。 5.【答案】C [解析] 解析:读表达式树是一棵满二叉树,因此A选项错误;该表达式树中度为2的节点比叶子节点少一个,因此B选项错误;该表达式树的后序遍历序列为16+23*-,因此D选项错误;该表达式树的中序遍历序列为1十6-2*3,因此答案为C。 6.【答案】B [解析][本题主要考查的是二叉树的数组表示。图中的二叉树为非完全二叉树,方法为:先将它补全为一棵完全二叉树，即补全c节点的左孩子节点,d节点的左右孩子节点,f节点的左孩子节点，然后按照完全二叉树的方法来表示，因此,答案为B。 7.【答案】A [解析]中序遍历的顺序为左子树，根节点，右子树，所以中序遍历为DBGEACFH，所以选项A符合题意。 故选:A。 8.【答案】D [解析]后序遍历为IGHDBEFCA可以得到根节点为A;中序遍历可知左子树为BIGDH，右子树为BCF，依次类推可以得到该二叉树的前序遍历为ABDGIHCEF。故选:D。 9.【答案】D [解析]完全二又树的节点个数为4"N十3,则最后一个叶子节点的编号为 4*N+3,其父节点的编号为2*N十1,即度为2的节点数为2*N+1,因此它的叶子节点个数为4*N+3-(2*N+1)=2"N+2,故答案为D。 原创精品资源学科网独家享有版权，侵权必究！ 学科网（北京）股份有限公司 学科网（北京）股份有限公司 $$