• 首页
  • 教育理念
  • 文章专题
  • 编程教程
    • – Scratch编程教程
    • – AppInventor编程
    • – Python编程教程
    • – NOIP信息学奥赛
    • – C/C++编程教程
    • – JS编程教程
  • 少儿编程学院
    • – 在线课程
    • – 学院名师
    • – 动态资讯
  • 少儿编程社区
    • – 在线编程
    • – 编程作品
    • – 专题创作
  • 更多
    • – APP客户端
    • – 关于我们
    • – 寻求合作
    • – 少儿编程联盟
投稿 登录 注册
  • 首页
  • 文章专题
  • 教育理念
  • 编程教程
  • 少儿编程学院
  • 微信公众号
  • APP客户端
少儿编程学院
少儿编程教育-微信公众号
首页 › 编程教程 › NOIP信息学奥赛 › 正文
NOIP信息学奥赛信息竞赛编程竞赛

NOIP初赛复习(四)二叉树的遍历和性质

主编主编 NOIP信息学奥赛 2017-08-24 9,549 54

1.二叉树的遍历

NOIP初赛复习(四)二叉树的遍历和性质-少儿编程教育网

(图1)

NOIP初赛复习(四)二叉树的遍历和性质-少儿编程教育网

(图2)

二叉树的遍历运算(递归定义)
(1) 先序遍历:  根,左子树,右子树  根在先

例如图1:271653894;图2:ABCKDEHFJG

(2) 中序遍历:  左子树,根,右子树   根在中

例如图1:175632849;图2:BKCAHEDHFG

(3) 后序遍历:  左子树,右子树,根  根在后

例如图1:153674982;图2:KCBHEJGFDA

NOIP初赛复习(四)二叉树的遍历和性质-少儿编程教育网

题型一:已知其中一些遍历结果,求其他遍历结果

题型二:统计n个不同的点可以构造多少棵不同的二叉树?  Catalan数=C(n,2*n)/(n+1)

题型三:中缀表达式向前缀和后缀表达式的转化


每日练习

注:题1已知先序和中序,二叉树是唯一的。

题2已知后序和中序,二叉树是唯一的。

题3已知先序和后序,二叉树不是唯一的。

1、已知先序:1 2 4 3 5 7 6,  中序:2 4 1 7 5 3 6,请画出整棵二叉树。

2、已知后序:4 5 2 6 7 3 1,  中序:4 2 5 7 6 3 1,请画出整棵二叉树。

3、已知先序:1 2 3 4 5 6,    后序:3 2 5 6 4 1,请画所有二叉树的情况。

4、如果只知道先序abc,画出所有可能二叉树形状,并且计算多少种?

5、如果只知道中序abc,画出所有可能二叉树形状,并且计算多少种?

6、如果只知道后序abc,画出所有可能二叉树形状,并且计算多少种?


往年真题

1. 一颗二叉树的前序遍历序列是ABCDEFG,后序遍历序列是CBFEGDA,则根结点的左子树的结点个数可能是(   )。

A.0         B.2         C.4         D. 6

2. 表达式a*(b+c)-d的后缀表达式是:

A) abcd*+-   B) abc+*d-   C) abc*+d-   D) -+*abcd

3. 二叉树T,已知其先序遍历是1 2 4 35 7 6(数字为节点编号,以下同),后序遍历是4 2 7 56 3 1,则该二叉树的中根遍历是(    )

A.4 2 1 7 5 3 6    B.2 4 1 7 5 3 6     C.4 2 1 75 6 3    D.2 4 1 57 3 6

4. 二叉树T,已知其先根遍历是1 2 4 35 7 6(数字为结点编号,以下同),中根遍历是2 4 1 57 3 6,则该二叉树的后根遍历是(     )

A. 4 2 5 7 6 3 1     B. 4 2 7 5 6 3 1     C. 7 4 2 5 6 3 1    D. 4 2 7 6 5 3 1

5. 已知7个节点的二叉树的先根遍历是1 2 4 5 6 3 7(数字为结点的编号,以下同), 后根遍历是4 6 5 2 7 3 1, 则该二叉树的可能的中根遍历是(      )
A. 4 2 6 5 1 7 3      B. 4 2 5 6 1 3 7   C. 4 2 3 1 5 6 7     D. 4 2 5 6 1 7 3

6. 已知7个节点的二叉树的先根遍历是1 2 4 5 6 3 7(数字为节点的编号,以下同),中根遍历是4 2 6 51 7 3,则该二叉树的后根遍历是(     )
A.4 6 5 27 3 1     B.4 6 5 2 1 3 7    C.4 2 3 1 5 4 7    D.4 6 5 3 1 7 2

7. 已知6个结点的二叉树的先根遍历是1 2 3 4 5 6(数字为结点的编号,以下同),后根遍历是3 2 5 64 1,则该二叉树的可能的中根遍历是(     )

A. 3 2 1 46 5       B. 3 21 5 4 6      C. 2 3 1 5 4 6       D. 2 31 4 6 5


2.二叉树的性质

性质1:二叉树第i层上的结点数目最多为NOIP初赛复习(四)二叉树的遍历和性质-少儿编程教育网。

性质2:深度为k的二叉树至多有NOIP初赛复习(四)二叉树的遍历和性质-少儿编程教育网个结点(k≥1)。

NOIP初赛复习(四)二叉树的遍历和性质-少儿编程教育网

性质3:二叉树中,叶子节点数为n0,度为2的结点数为n2,则n0=n2+1。

满二叉树

定义:一棵深度为k且有NOIP初赛复习(四)二叉树的遍历和性质-少儿编程教育网个结点的二又树称为满二叉树。

特点:每层都饱满NOIP初赛复习(四)二叉树的遍历和性质-少儿编程教育网。

完全二叉树

定义:除了最下层,其他每层都饱满,最下层的结点都集中在该层最左边的若干位置上。

特点:

① 满二叉树是完全二叉树,完全二叉树不一定是满二叉树;

② 在满二叉树的最下层上,从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。

③ 在完全二叉树中,若某个结点没有左孩子,则它一定没有右孩子,即该结点必是叶结点。④若I为结点编号则 如果I<>1,则其父结点的编号为I/2;若2*I<=N,则其左儿子(即左子树的根结点)的编号为2*I;若2*I>N,则无左儿子若2*I+1<=N,则其右儿子的结点编号为2*I+1;若2*I+1>N,则无右儿子。

例题1:画一个深度为4的满二叉树。画一个深度为4的完全二叉树。

例题2:具有3个结点的完全二叉树的深度为(   )

具有6个结点的完全二叉树的深度为(   )

具有8个结点的完全二叉树的深度为(   )

具有125个结点的完全二叉树的深度为(   )

具有1024个结点的完全二叉树的深度为(   )

例题3:完全二叉树的结点数为n,求该完全二叉树的深度(层数)。

解:设所求完全二叉树的深度为k。

深度为k得完全二叉树的前k-1层是深度为k-1的满二叉树,一共有2^(k-1)-1个结点。

由于完全二叉树深度为k,故第k层上还有若干个结点,因此该完全二叉树的结点个数: n>2^(k-1)-1。

另一方面,假设节点最多,NOIP初赛复习(四)二叉树的遍历和性质-少儿编程教育网

由此可推出:NOIP初赛复习(四)二叉树的遍历和性质-少儿编程教育网

又因k-1和k是相邻的两个整数,故有NOIP初赛复习(四)二叉树的遍历和性质-少儿编程教育网。


 每日练习

1.完全二叉树对每个节点从上往下,从左往右编号,第i层的第j个节点的编号是( )

A 2^i+j    B 2^i+j-1     C 2^(i-1)+j        D 2^(i-1)+j-1

2.一棵有n个节点的完全二叉树的高度是(  )

NOIP初赛复习(四)二叉树的遍历和性质-少儿编程教育网

3.二叉树是重要的数据结构,5个点的不同的二叉树有(  )个。

A22        B 30         C  40         D 42

4.完全二叉树的结点个数为4 * N + 3,则它的叶结点个数为(  )。

A  2*N   B 2*N-1   C 2*N+1   D  2*N-2   E  2*N+2

5.满二叉树的叶结点个数为N,则它的结点总数为(  )。

A  N      B 2*N      C 2*N–1    D  2*N+1    E  2N–1

6.在有N个叶子节点的哈夫曼树中,其节点总数为( )

A  不确定  B  2N-1     C  2N+1     D  2N

7.一棵二叉树高度为h,所有结点的度为0,或为2,则此树最少有( )个结点

A2^(h-1)      B 2^h-1      C 2^h+1      D h+1

8.按照二叉树的定义,具有3个结点的二叉树有(    ) 种。

A  3      B  4      C  5       D 6

9、[多选题]对一个满二叉树,m个树叶,K个分枝结点,n个结点,则:(   )

A.n=K+m    B.K+m=2n   C.m=K-1   D.n=2K-1

10. [多选题]关于二叉树的正确说法是(  )。

A 完全二叉树一定是满二叉树     B 满二叉树一定是完全二叉树

C 深度为h的二叉树最多有2^h-1个结点(h>=1),最少有h个结点

D 对于任意一棵二叉树,如果其叶结点数为N0,而度数为2的结点总数为N2,则N0=N2+1

E 在二叉树中,第i层的结点总数不超过2^(i-1);

11. 完全二叉树的结点个数为11,则它的叶结点个数为( )

A.4    B.3   C.5    D.2    E. 6

12. 一个高度为h 的二叉树最少结点数目是(         )。

A  2^h+1     B h    C 2^h-1    D  2^h    E  2^(h-1)

13. 设有一棵k叉树,其中只有度为0和k两种结点,设n0,nk分别表示度为0和度为k的结点个数,试求出n0,nk之间的关系(n0=数学表达式,数学表达式仅含nk,k和数字)

14. 如果一棵m度树中有n1个度为1的结点,n2个度为2的结点,…….有nm个度为m的结点,则该树中叶结点的的个数=______________.


二叉树的遍历往年真题参考答案:
1.B 2.B 3.ABD 4.B 5.ABD 6.A 7.BC

二叉树的性质每日练习参考答案:
1.D 2.B 3.D 4.E 5.C 6.B 7.A 8.C 9.AC 10.BCE 11.E 12.B
13. n0=nk*(k-1)+1
14. n1+n2+……=nm

喜欢 (54)
打赏
  • 打赏支付宝扫一扫
  • 打赏微信扫一扫
微博 微信 QQ

微信扫一扫,分享到朋友圈

微信公众号
编程少年Scratch实物积木
少儿编程教育-微信公众号
上一篇

NOIP初赛复习(三)栈与卡特兰数

下一篇

少儿编程教育该怎么教?我们看看美国CSTA计算机教育标准!

猜你喜欢

  • 第二届全国中学生网络安全竞赛即将在西安电子科大举办!

    第二届全国中学生网络安全竞赛即将在西安电子科大举办!

  • 严查违规竞赛,29项全国中小学生竞赛活动名单公布!

    严查违规竞赛,29项全国中小学生竞赛活动名单公布!

  • 教育部:2019年度中小学生全国性竞赛活动名单公示

    教育部:2019年度中小学生全国性竞赛活动名单公示

  • 第二十届全国中小学电脑制作活动通知

    第二十届全国中小学电脑制作活动通知

  • 2018年全国青少年创意编程大赛,终评活动即将开启!

    2018年全国青少年创意编程大赛,终评活动即将开启!

  • STEAM教育专题 | 源自硅谷的机器人教育机构萝卜太辣

    STEAM教育专题 | 源自硅谷的机器人教育机构萝卜太辣

主编
主编官方

我真的不是自黑!

中国STEAM教育2018年度风云榜

微信公众号

推荐专题

  • 有趣的少儿编程游戏推荐

    查看专题
  • 国外优秀的少儿编程教育

    查看专题
  • S科学-T技术-E工程-M数学

    查看专题

猜你喜欢

  • 这份1000万人收藏的计算机科学速成课,快来免费领取吧!
    2019-10-31

    这份1000万人收藏的计算机科学速成课,快来免费领取吧!

  • 他说超6成未来工作还未出现,我们该培养孩子哪些能力?

    他说超6成未来工作还未出现,我们该培养孩子哪些能力?

    2017-06-11
  • 【NOIP专栏】我应不应该参加信息学竞赛?

    【NOIP专栏】我应不应该参加信息学竞赛?

    2017-09-17
  • STEAM教育专题 | 鲨鱼公园致胜未来的STEAM学习方式

    STEAM教育专题 | 鲨鱼公园致胜未来的STEAM学习方式

    2018-09-19
  • 九、无任何奖项,做好这样依然可以完胜自主招生!

    九、无任何奖项,做好这样依然可以完胜自主招生!

    2018-08-03

热门文章

  • 新型冠状病毒肺炎,儿童真的不易感?专家组组长:论据尚不充分!
    2020-01-24 57,488

    新型冠状病毒肺炎,儿童真的不易感?专家组组长:论据尚不充分!

  • 9个青少儿防疫问题,北京大学国际医院儿科专家权威解答!
    2020-02-08 45,189

    9个青少儿防疫问题,北京大学国际医院儿科专家权威解答!

热门标签

鲨鱼公园高考改革高考加分青橙创客青少儿防疫阿部和广错误观念逻辑思维费米科学贝尔科教谷歌教育计算机科学计算机思维解决方案西瓜创客

微信公众号

热门文章 热门标签 年度归档 少儿编程教育联盟

Copyright © 2021 少儿编程教育网 粤ICP备17057575号 · Designed by shaoerbc.org

大家都在搜

  • Scratch教程
  • scratch2下载
  • Scratch编程
  • 编程思维
  • 信息学奥赛
  • STEM教育
  • 编程一小时
  • 自主招生
  • 少儿编程竞赛

关注我们的公众号

微信公众号