【数据结构】二叉树性质巩固(二)

本文涉及的产品
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
云解析 DNS,旗舰版 1个月
全局流量管理 GTM,标准版 1个月
简介: 【数据结构】二叉树性质巩固(二)

例题5.


1ef7f34e64bd5ea6a830231b4b7c0fa3_c0f95787693441c18f013f1a7cc7b291.png


答案:C


解析:


前序确定根,中序找到根确定根的左右子树,最后还原二叉树为:


3763eda8d7966cab3d3134547d3fc528_3ab64a7805624885897933e60a895270.png


前: ABDEC 中:BDEAC


所以既不是满二叉树,也不是完全二叉树


例题6.


46af151b7673213eb6b947bdf1ad426b_8fdacbb0b79c46ed9b34dbecfe2d569d.png


答案:A


解析:


最大深度: 即每次只有一个节点,次数二叉树的高度为n,为最高的高度


最小深度: 此树为完全二叉树, 如果是完全二叉树


根据二叉树性质,完全二叉树的高低为 h = log(n+1)向上取整


故选择A


例题7.


ef287b2a8c27ab6699383b91fc48e4fb_c22f47b8361140bb9ee6b2db65e131d4.png


答案:D


解析:


BFS:

广度优先需要把下一步所有可能的位置全部遍历完,才会进行更深层次的遍历,广度优先一般使用队列。层序遍历就是一种广度优先遍历。


DFS:

深度优先是先遍历完一条完整的路径(从根到叶子的完整路径),才会向上层折返,再去遍历下一个路径,深度优先一般使用递归。前序遍历就是一种深度优先遍历。


例题8.


18a22b237fde91de8a2b3ea03f840822_2d5678669cc94ed1817dbb474f6d2e16.png


答案:B


解析:


首先这棵二叉树的高度一定在3~4层之间:


三层:


A(B(C,D),()), A((),B(C,D)), A(B(C,()),D), A(B((),C),D),


A(B,C(D,())), A(B,C((),D))


四层:


如果为四层,就是单边树,每一层只有一个节点,除过根节点,其他节点都有两种选择,在上层节点的左边还是右边,所以2 * 2 * 2共8种


总共为14种。


例题9.


a42565683483cb28bc320d0d1cff6187_c694f7f2b1134d90bdfafd8741d1f73b.png


答案:C


解析:


前序遍历:根 左 右


后序遍历:左 右 根


从二叉树 前序 和 后序遍历结果规则中可以看出,如果树中每个节点只有一个孩子时,遍历结果肯定是反的


比如下面这前序和中序序列所构成的树的结构:


12345


54321


7fcfb98256ced63be6bcac2fd529d9e8_f59f4bab54134f58bfbb530dc164a2b7.png

目录
相关文章
|
1月前
|
机器学习/深度学习 存储 算法
数据结构实验之二叉树实验基础
本实验旨在掌握二叉树的基本特性和遍历算法,包括先序、中序、后序的递归与非递归遍历方法。通过编程实践,加深对二叉树结构的理解,学习如何计算二叉树的深度、叶子节点数等属性。实验内容涉及创建二叉树、实现各种遍历算法及求解特定节点数量。
81 4
|
1月前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
131 8
|
2月前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
31 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
2月前
|
存储 算法 搜索推荐
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
35 0
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
|
2月前
|
Java
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(二)
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(二)
31 1
|
2月前
|
算法 Java C语言
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(一)
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(一)
29 1
|
2月前
|
存储
【数据结构】二叉树链式结构——感受递归的暴力美学
【数据结构】二叉树链式结构——感受递归的暴力美学
|
2月前
|
存储 算法
探索数据结构:分支的世界之二叉树与堆
探索数据结构:分支的世界之二叉树与堆
|
2月前
|
存储 算法
数据结构与算法学习十六:树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识,包括树的存储方式、二叉树的定义、遍历方法(前序、中序、后序、层次遍历),以及二叉树的查找和删除操作。
31 0
|
2月前
|
存储 算法
【数据结构】二叉树——顺序结构——堆及其实现
【数据结构】二叉树——顺序结构——堆及其实现