【C/C++笔记】:易错难点3 (二叉树)

选择题

🌈eg1

一棵有15个节点的完全二叉树和一棵同样有15个节点的普通二叉树,叶子节点的个数最多会差多少个()?

正确答案: C

A. 3      B. 5      C. 7       D. 9

解析:普通二叉树的叶子节点数最少为1 所以,而一棵完全二叉树最下面一层都是叶子节点,对于15个节点的完全二叉树,有 8 个叶子节点,因此最多会相差7个。

🌈eg2

一棵有 n 个结点的二叉树,按层次从上到下、同一层从左到右顺序存储在一维数组 A[1…n] 中,则二叉树中第 i 个结点(i从1开始用上述方法编号)的右孩子在数组 A 中的位置是( )

正确答案:D

A. A[2i](2i <= n)
B. A[2i + 1](2i + 1 <= n)
C. A[i - 2]
D. 条件不充分,无法确定

解析:

必须是完全二叉树才能确定,若是,选择B选项。图解如下:


根据二叉树的性质5:
1.对于具有n个结点的完全二叉树,如果按照从上至下从左至右的数组顺序对所有节点从0开始编号,则对于序号为i的结点有:
1.1 若i>0,i位置节点的双亲序号:(i-1)/2;i=0,i为根节点编号,无双亲节点
1.2 若2i+1<n,左孩子序号:2i+1,2i+1>=n否则无左孩子
1.3 若2i+2<n,右孩子序号:2i+2,2i+2>=n否则无右孩子
上述的性质的节点从0开始编号, 而题目当中是从1开始编号, 所有右孩子的序号为 2i+1

🌈eg3 

已知-算术表达式的中缀表达式为 a-(b+c/d)*e , 其后缀形式为( )

正确答案:D
A. -a+b*c/d
B. -a+b*cd/e
C. -+*abc/de
D. abcd/+e*-

解析:使用中缀表达式构建二叉树

  1. 第一个 “-”则将表达式分为左右子树, 左子树为“a”, 右子树为“(b+c/d)e”
  2. 在1.1中的右子树“(b+c/d)e”, 通过“”将再次分为左右子树, 左子树为“(b+c/d)”, 右子树为“e”
  3. 在1.2中的左子树“(b+c/d)”, 通过“+”将再次分为左右子树, 左子树为“b”, 右子树为“c/d”
  4. 在1.3中的右子树“c/d”, 通过“/”将再次分为左右子树, 左子树为“c”, 右子树为“d”
    所以构建出来的二叉树如下图所示, 后缀表达式也就不难求解, 先左, 再右, 再根, 即“abcd/+e-”

🌈eg4

将一棵有100个结点的完全二叉树从根这一层开始,开始进行层次遍历编号,那么编号最小的叶节点的编号为(),则编号为 98 的节点的父节点编号为()。 (根节点为1)

正确答案:51, 49

解析:

由题意可知最小编号的叶子一定是最后一个节点的父节点的右兄弟节点,最后节点编号100,父节点编号为50,所以答案是51。

根节点是i,那么子节点是2i,2i+1,那么98,99的父节点就是49,

🌈eg5

设二叉树的先序遍历序列和后序遍历序列正好相反,则该二叉树满足的条件是()。

正确答案:B

A. 空或只有一个结点   B. 高度等于其结点数

C. 任一结点无左孩子   D. 任一结点无右孩子

解析:

A.如果是空,或者是只有一个结点那么先序遍历和后序遍历得到的序列是一样的。
C.在任何一个结点没有左孩子的时候

D.与C同理
B.满足每一层只有一个结点,即树高等于结点的数目时题目条件成立

先序遍历:根左右;后续遍历:左右根

要满足题意,则只有,根左<----->左根,根右<--------->右根

所以高度一定等于节点数

🌈eg6

某二叉树共有 399 个结点,其中 有199个为 度为2的 结点 ,则该二叉树中的叶子节点数为()

正确答案:C

A. 198     B. 199      C. 200    D. 201

解析:

由二叉树的性质可知:n2 = n0 + 1

故度为0 及叶子节点 比 度为2 (199) 多一个 ,答案为 200个

🌈eg7

在一颗度为3的树中,度为3的结点有2个,度为2的结点有1个,度为1的结点有2个,则叶子结点有( )个

正确答案:D

A. 7     B. 0      C. 7    D. 6

解析:

设度为i的节点个数为ni,则该树总共有n个节点
n = n0+n1+n2+n3.
有n个节点的树的总边数为 n-1条,根据度的定义,总边数与度之间的关系为
n-1 = 0n0+1n1+2n2+3n3
联立两个方程可得,n0 = n2 +2 n3+1, n0 =6.

🌈eg8

设一棵完全二叉树具有1000个结点,则此完全二叉树有()个度为2的结点。

正确答案:C

A. 497 B. 498 C. 499 D. 500

解析:

1、叶子结点:度为0的结点。
2、以n0代表度为0的结点,n2代表度为2的结点
3、则根据二叉树的性质有 n0 = n2 +1

  1. 1000个结点的完全二叉树有10层(2^9 - 1 < 1000 < 2 ^10 -1)

    其中前9层为满二叉树,共有512-1=511个结点。因此有1000-511=489,说明第10层有489个结点,且第10层的结点均为叶子结点(度为0的结点)

  2. 而489/2 = 244…1,说明第9层有244+1(245)个结点有子结点,而根据满二叉树第9层共有 2^8  = 256个结点,则第9层度为0的结点(叶子结点)个数为 256-245 = 11。
  3. 再由第一步所得叶子结点个数,可得二叉树中度为2的结点数为:
    n2=n0-1=500-1=499
    即:度为2的结点数有499个


编程题

🎈eg1

从根到叶的二进制数之和

解析:

  • 后序遍历的访问顺序为:左子树——右子树——根节点。我们对根节点 root 进行后序遍历:

  • 如果节点是叶子节点,返回它对应的数字 val。

  • 如果节点是非叶子节点,返回它的左子树和右子树对应的结果之和。
class Solution {
public:int dfs(TreeNode * root, int val){if(root == nullptr) return 0;val = (val << 1) | root->val; //二进制转10进制if(root->left == nullptr && root->right == nullptr) { //求叶子节点return val;}return dfs(root->left, val) + dfs(root->right, val);}int sumRootToLeaf(TreeNode* root) {return dfs(root, 0);}
};

🎈eg2 

二叉树的坡度

解析:dfs,在遍历每个结点时,累加其左子树结点之和与右子树结点之和的差的绝对值,并返回以其为根结点的树的结点之和。

  • 从根结点开始遍历

  • 遍历 root 的左子结点,得到左子树结点之和 sl;遍历 root 的右子结点,得到右子树结点之和 sr;

  • 将左子树结点之和与右子树结点之和的差的绝对值累加到结果变量 ans;
  • 返回以 root 作为根结点的树的结点之和 sl + sr + node.val
class Solution {
public:int ans = 0;int dfs(TreeNode* root){if(root == nullptr) return 0;int sl = dfs(root->left);int sr = dfs(root->right);ans += abs(sl - sr);return sl + sr + root->val;}int findTilt(TreeNode* root) {dfs(root);return ans;}
};

🎈eg3

奇偶树

解析:

        根据题意可知,我们需要根据 层 遍历这棵树,因此使用宽度优先搜索BFS遍历二叉树。

        首先可以将root放入队列中,由于root的level=0,所以从其出发的可以直接到达点的level=1,将root从队列中弹出,然后将level=1的点放入队列中,因此现在队列的所有节点的level=1。

        每次将下一层节点放入队列的时候,优先将左边先放入队列,这样就可以保证每一层是从左往右顺序的。

重复上面过程,所以从level=1出发的点,可以直接到达level=2。

在遍历每一层的时候,根据规则判断是否满足奇偶树的性质。

  • 如果当前 层是偶数,首先判断数字的奇偶性,设prev的默认值为0,根据数字大小判断是否满足严格递增,并修改pre

  • 如果当前 层是技术,首先判断数字的奇偶性,设prev的默认值为106+1,根据数字大小判断是否满足严格递减,并修改pre
class Solution {
public:bool isEvenOddTree(TreeNode* root) {queue<TreeNode*> q;q.push(root);int level = 0;while(!q.empty()){int sz = q.size();int pre = level == 0 ? 0 : 1e6 + 1;for(int i = 0; i < sz; i++){TreeNode* next = q.front();q.pop();// 偶数递减 奇数递增if((level == 0 && next->val <= pre) || (level == 1 && next->val >= pre)) return false;//奇偶if((level == 0 && next->val % 2 == 0) || (level == 1 && next->val % 2 == 1)) return false;pre = next->val;if(next->left) q.push(next->left);if(next->right) q.push(next->right);}level ^= 1;}return true;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/394162.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

WPF学习笔记

WPF WPF&#xff08;Windows Presentation Foundation&#xff0c;Windows呈现基础&#xff09;是微软推出的基于Windows 的用户界面框架&#xff0c;属于.NET Framework 3.0的一部分。它提供了统一的编程模型、语言和框架&#xff0c;真正做到了分离界面设计人员与开发人员的…

C语言----计算开机时间

计算开机时间 实例说明 编程实现计算开机时间&#xff0c;要求在每次开始计算开机时间时都能接着上次记录的结果向下记录。 实现过程&#xff1a; 1. 在TC中创建一个C文件。 2. 引用头文件&#xff0c;代码如下: #include <stdio.h> 3. 定义结构体time&#xff0c;用来…

如何在Chrome、Edge、360、Firefox等浏览器查看网站SSL证书信息?

在如今的网络环境中&#xff0c;保障网络安全、数据安全尤其重要&#xff0c;市面上大部分网站都部署了SSL证书以实现HTTPS加密保护数据传输安全以及验证网站身份&#xff0c;确保网站安全可信。那么如何查看网站的SSL证书信息&#xff1f;接下来&#xff0c;我们将详细介绍如何…

【Android】网络技术知识总结之WebView,HttpURLConnection,OKHttp,XML的pull解析方式

文章目录 webView使用步骤示例 HttpURLConnection使用步骤示例GET请求POST请求 okHttp使用步骤1. 添加依赖2. 创建OkHttpClient实例3. 创建Request对象构建请求4. 发送请求5. 获取响应 Pull解析方式1. 准备XML数据2. 创建数据类3. 使用Pull解析器解析XML webView WebView 是 An…

【Nacos无压力源码领读】(三) Nacos 配置中心与热更新原理详解 敢说全网最细

本文将从 Nacos 配置中心的基本使用入手, 详细介绍 Nacos 客户端发布配置, 拉取配置, 订阅配置的过程以及服务器对应的处理过程; 配置订阅以及热更新原理相关的部分, 我看了主流的博客网站, 绝对没有比这更详细的讲解; 如果在阅读过程中对文中提到的 SpringBoot 启动过程以及…

Milvus与Zilliz Cloud:向量数据库高可用性的双重飞跃

向量数据库高可用性的重要性及其在现代数据分析中的关键作用 在数据爆炸式增长的今天,企业对于高效、准确地处理和分析大规模数据集的需求日益迫切。尤其是在人工智能、机器学习、图像识别、自然语言处理等领域,向量数据库因其对高维数据的高效存储与检索能力,成为了不可或…

Elasticsearch未授权访问漏洞

步骤一:使用以下Fofa语法进行Elasticsearch产品搜索.. fofa语法"Elasticsearch" && port"9200" 步骤二:存在未授权访问则直接进入到信息页面...不需要输入用户密码登陆. http://localhost:9200/_plugin/head/web管理界面 http://localhost:9200/…

【JavaEE】线程池

目录 前言 什么是线程池 线程池的优点 ThreadPollExecutor中的构造方法 corePoolSize && maximumPoolSize keepAliveTime && unit workQueue threadFactory 如何在java中使用线程池 1.创建线程池对象 2.调用submit添加任务 3.调用shutdown关闭线程池…

【Python】requests的response.text 和 urllib.request 的 response.read()的区别

刚写代码的时候&#xff0c;我经常会把requests 和 urllib下的request 包搞混&#xff0c;这两个请求响应的方法看起来很相似&#xff0c;但是写获取的方法是不一样的。 前者requests 是用response.text 来获取源码&#xff0c;而 urllib.request是用 response.read() 来获取h…

数学建模--智能算法之免疫算法

目录 基本原理 应用实例 代码示例 总结 免疫算法在免疫系统研究中的应用和进展是什么&#xff1f; 如何量化评估免疫算法在不同优化问题中的性能和效率&#xff1f; 免疫算法与其他智能优化算法&#xff08;如遗传算法、粒子群优化&#xff09;相比有哪些独特优势和局限性…

【C++】C++11的新特性 — 线程库 ,原子操作 , 条件变量

勇敢就是接受发生在你身上的事&#xff0c;并把它尽力做到最好。 -- 约翰・欧文 -- C11的新特性 1 线程1.1 线程概念1.2 C中的线程1.3 线程并行1.4 锁 2 原子操作3 条件变量Thanks♪(&#xff65;ω&#xff65;)&#xff89;谢谢阅读&#xff01;&#xff01;&#xff01;下…

编译和汇编的区别

一、编译 编译是将高级语言&#xff08;如C、C、Java等&#xff09;编写的源代码转换成计算机可以直接执行的低级语言&#xff08;通常是机器语言或汇编语言&#xff09;的过程 编译 —— 将人类可读的源代码转换为计算机可执行的指令集 编译过程 通常包括词法分析、语法分…

正点原子imx6ull-mini-Linux驱动之Linux 网络驱动实验

网络驱动是 linux 里面驱动三巨头之一&#xff0c;linux 下的网络功能非常强大&#xff0c;嵌入式 linux 中也常 常用到网络功能。前面我们已经讲过了字符设备驱动和块设备驱动&#xff0c;本章我们就来学习一下 linux 里面的网络设备驱动。 1&#xff1a;嵌入式网络简介 1.1…

如何给源代码加密?这款加密软件教给你操作步骤

给源代码加密是保护软件知识产权和商业机密的重要手段。以这款加密软件安企神为例&#xff0c;给源代码加密的过程可以概述为以下几个方面。 一、安企神软件概述 安企神是一款功能强大的企业安全加密软件&#xff0c;它提供了全面的源代码防泄漏解决方案。该软件通过透明文件加…

扩散模型系列笔记(一)——DDPM

直观理解 扩散模型分为前向过程&#xff08;扩散过程&#xff0c;Data → \to →Noise&#xff09;和后向过程&#xff08;生成过程或逆扩散过程&#xff0c;Noise → \to →Data&#xff09;。在前向过程中&#xff0c;对于每一个观测样本&#xff0c;不断向样本中添加少量噪…

Leetcode每日刷题之字符串中的第一个唯一字符(C++)

在学习的过程中对代码的熟练运用至关重要&#xff0c;练习解决实际问题就可以很好的锻炼自己的编程能力&#xff0c;接下来让我们练习这道 387.字符串中的第一个唯一字符 思路解析 根据题意我们可以知道这个字符串只有小写字母&#xff0c;并且可能包含多个唯一字符&#xff0…

Java---字符串string练习

目录&#xff1a; 1.将数字转换成罗马数字 2.键盘输入任意字符串&#xff0c;打乱里面的内容 3.返回字符串中最后一个单词长度 4.调整A字符串 看是否可与B字符串匹配 一&#xff1a; //键盘录入一个字符串// 长度小于等于9 只能是数字// -将内容变成罗马数字// Ⅰ Ⅱ Ⅲ Ⅳ…

智慧水务项目(二)django(drf)+angular 18 创建通用model,并对orm常用字段进行说明

一、说明 上一篇文章建立一个最简单的项目&#xff0c;现在我们建立一个公共模型&#xff0c;抽取公共字段&#xff0c;以便于后续模块继承&#xff0c;过程之中会对orm常用字段进行说明&#xff0c;用到的介绍一下 二、创建一个db.py 目录如下图 1、代码 from importlib im…

基于QT实现的简易WPS(已开源)

一、开发工具及开源地址&#xff1a; 开发工具&#xff1a;QTCreator &#xff0c;QT 5 开源地址&#xff1a; GitHub - Whale-xh/WPS_official: Simple WPS based on QTSimple WPS based on QT. Contribute to Whale-xh/WPS_official development by creating an acc…

推荐 3个实用且完全免费的在线工具,每天都会用到,无需登录打开即用

100font 100font是一个专业的免费商用字体下载网站&#xff0c;专注于收集、整理和分享各种免费无版权的商用字体。用户可以在这个平台上找到并下载简体中文、繁体中文、英文、日文、韩文等多种语言类型的字体。 该网站的特点包括清晰的分类和直观的下载流程&#xff0c;用户可…