二叉树相关OJ题

                                                       创作不易,感谢三连!! 

一、选择题

1、某二叉树共有 399 个结点,其中有 199 个度为 2 的结点,则该二叉树中的叶子结点数为( )
A.不存在这样的二叉树
B.200
C.198
D.199
解析:选B,根据n0=n2+1的结论(这个结论不清楚的看博主的关于二叉树概念的文章有证明),就是度为0的节点始终比度为2的节点多一个,所以这题就很显然选B了!!

2、在具有 2n 个结点的完全二叉树中,叶子结点个数为( )

A n
B n+1
C n-1
D n/2
解析:选A ,原因如下

3、一棵完全二叉树的节点数位为531个,那么这棵树的高度为( )
A 11
B 10
C 8
D 12
解析:选B,根据结论——满二叉树的节点N数量=2^h-1,如果高度为8,那么节点最多有255个,当高度为10时,节点最多有1023个,所以高度只能是10

4、一个具有767个节点的完全二叉树,其叶子节点个数为()
A 383
B 384
C 385
D 386
解析:选B,因为度为2的节点数肯定并度为0的节点数少1个,所以n0和n2一个是奇数一个是偶数,所以n1只能是偶数,又因为完全二叉树n1只有可能是0或者1,所以n1只能取0,所以n0=384,n2=383

5、一组记录排序码为(5 11 7 2 3 17),则利用堆排序方法建立的初始堆为()。
A(11 5 7 2 3 17)
B(11 5 7 2 17 3)
C(17 11 7 2 3 5)
D(17 11 7 5 3 2)
E(17 7 11 3 5 2)
F(17 7 11 3 2 5)

解析:选C 先画出来,再不断向下调整

6、最小堆[0,3,2,5,7,4,6,8],在删除堆顶元素0之后,其结果是()
A[3,2,5,7,4,6,8]
B[2,3,5,7,4,6,8]
C[2,3,4,5,7,8,6]
D[2,3,4,5,6,7,8]
 解析:选C,还是画出来再调整

二、单值二叉树

OJ:单值二叉树

bool isUnivalTree(struct TreeNode* root)
{
   if(root==NULL)//a==b,a==c,->b==c
   return true;
   if(root->left&&root->left->val!=root->val)
   return false;
   if(root->right&&root->right->val!=root->val)
   return false;
   return isUnivalTree(root->left)&&isUnivalTree(root->right);
}

三、检查两棵树是否相同

OJ:判断两棵树是否相同

这个在博主讲解二叉树链式存储中有仔细分析过了!!

bool isSameTree(struct TreeNode* p, struct TreeNode* q) 
{
    if(p==NULL&&q==NULL)
    return true;
    if(p==NULL||q==NULL)
    return false;
    if(p->val!=q->val)
    return false;
    //此时得到的节点存在,且节点值相同的情况
    return isSameTree(p->left, q->left) &&
           isSameTree(p->right, q->right);
}

四、对称二叉树

 OJ:对称二叉树

 

bool _isSymmetric(struct TreeNode* leftroot,struct TreeNode* rightroot)
{
    //都为空,对称
    if(leftroot==NULL&&rightroot==NULL)
    return true;
    //一个为空一个不为空,不对称
    if(leftroot==NULL||rightroot==NULL)
    return false;
    //都不为空,就可以看值了,如果值不相等,不对称
    if(leftroot->val!=rightroot->val)
    return false;
    //此时都不为空,且值相等,就走递归找下一个
    //左树的左子树要跟右树的右子树相比
    //左树的右子树要跟右树的左子树相比
    return _isSymmetric(leftroot->left,rightroot->right)&&
           _isSymmetric(leftroot->right,rightroot->left);
}

bool isSymmetric(struct TreeNode* root) 
{
  if(root==NULL)
  return true;
  //根不对称,就去找左右子树比 相当于是拆成两棵树的了
  return _isSymmetric(root->left,root->right);
}

五、二叉树的前序遍历

OJ:二叉树的前序遍历

int TreeSize(struct TreeNode* root)
{
    return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}
void _preorder(struct TreeNode* root,int *a,int *i)
{
          if(root==NULL)
          return ;
          a[(*i)++]=root->val;
          _preorder(root->left,a,i);
          _preorder(root->right,a,i);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize) 
{
    //returnsize是结点数
    *returnSize=TreeSize(root);
     int *a=(int *)malloc(*returnSize*sizeof(int));
     int i=0;
     _preorder(root,a,&i);
     return a;
}

六、二叉树的中序遍历

OJ:二叉树的中序遍历

int i=0;
 int TreeSize(struct TreeNode* root)
{
    return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}
void _inorderTraversal(struct TreeNode* root,int *a)
{
          if(root==NULL)
          return ;
          _inorderTraversal(root->left,a);
          a[i++]=root->val;
          _inorderTraversal(root->right,a);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize) 
{
     //returnsize是结点数
    *returnSize=TreeSize(root);
     int *a=(int *)malloc(*returnSize*sizeof(int));
     i=0;//全局变量一定要记得赋0
     _inorderTraversal(root,a);//必须构造新函数去递归,因为在原函数递归会不断创建新的数组
     return a;
}

注:这题跟上题是差不多的,我稍微改了一下,这里数组的下标我不用指针去接受参数了,而是直接设置一个全局变量i!!要注意的是,因为力扣的测试可能会多次调用这个函数,所以我们一定要在递归函数运行前让i=0!!否则就会i就会一直叠加下去导致越界!! (还有一个注意事项就是,这里千万不要使用静态的局部变量,虽然他也同样可以在函数栈帧销毁时不被释放,但是他的作用域很小,不能让我们在主函数中让i=0)

但是尽量少使用全局变量!!

七、二叉树的后序遍历

OJ:二叉树的后序遍历

void _postorder(struct TreeNode* root,int *arr,int *arrsize)
{
    if(root==NULL)
    return;
    _postorder(root->left,arr,arrsize);
    _postorder(root->right,arr,arrsize);
    arr[(*arrsize)++]=root->val;
}

int* postorderTraversal(struct TreeNode* root, int* returnSize) 
{
    int *arr=(int*)malloc(100*sizeof(int));
    *returnSize=0;
     _postorder(root,arr,returnSize);
    return arr;
}

 注:这题和前两题差不多,但是又进行了改进,我们发现了题目的一个条件

      也就是说我们动态开辟100个空间的话是绝对不会越界的,所以就不需要通过自己封装一个treesize函数来计算节点个数数量了!! 那我们要怎么去让returnsize返回节点个数的值的??方法就是把*returnsize初始化为0作为下标,每次放进一个值的时候*returnsize就会++一次,当后序遍历结束的时候,returnsize恰好又多+了一次,正好表示节点个数的数量!!

八、另一颗树的子树

OJ:另一颗树的子树

 

bool isSametree(struct TreeNode* p,struct TreeNode* q)//比较两个树的递归函数
{
      if(p==NULL&&q==NULL)
      return true;
      if(p==NULL||q==NULL)
      return false;
      if(p->val!=q->val)
      return false;
      return isSametree(p->left,q->left)&&
             isSametree(p->right,q->right);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{
     if(root==NULL)
     return false;//为空就不比较的,因为subRoot是至少有一个节点的。
     if(isSametree(root,subRoot))
     return true;
     return isSubtree(root->left, subRoot)||isSubtree(root->right, subRoot);
     //左子树和右子树只要有一个找到了,就返回true
}

        关键就是我们每遍历到一个节点,都要尝试把他往下遍历去和另外一个子树进行比较!!所以单独封装了一个比较两个树是否相同的函数,该树每遍历一次节点就去调用一次,最后在用||操作符,因为左子树和右子树只要有一个找到就可以了!!

九、二叉树的构建及遍历

OJ:二叉树的构建及遍历

typedef char BTDataType;
typedef struct BTtreeNode
{
    BTDataType val;
    struct BTtreeNode*left;
    struct BTtreeNode*right;
}BTtreeNode;

BTtreeNode* BuyNode(BTDataType x)
{
    BTtreeNode*newnode=(BTDataType*)malloc(sizeof(BTDataType));
      newnode->left=newnode->right=NULL;
      newnode->val=x;
      if(newnode==NULL)
      {
        perror("malloc fail");
        exit(1);
      }
      return newnode;
}

BTtreeNode* CreateTree(BTDataType*a,int *pi)
{
    if(a[*pi]=='#')
    {
    (*pi)++;
    return NULL;
    }
    BTtreeNode*root=BuyNode(a[(*pi)++]);
    root->left=CreateTree(a,pi);
    root->right=CreateTree(a,pi);
    return root;
}

void InOrder(BTtreeNode*root)
{
    if(root==NULL)
    return;
    InOrder(root->left);
    printf("%c ",root->val);
    InOrder(root->right);
}

int main()
{
    char arr[100];
    scanf("%s",arr);
    int i=0;
    BTtreeNode*root=CreateTree(arr,&i);
    InOrder(root);
    printf("\n");
    return 0;
}

这题就是将二叉树的构建和链式结构的中序遍历结合起来了!!

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Linux设置jar包开机自启动

步骤 1、新建jar包自启文件 sudo vi /etc/init.d/jarSysInit.sh 按i键进入编辑模式输入以下内容: export JAVA_HOME/home/jdk/jdk-11.0.22 export CLASSPATH.:$JAVA_HOME/lib/dt.jar:$JAVA_HOME/lib/tools.jar:$JAVA_HOME/jre/lib/rt.jar export PATH$PATH:$JAVA_…

qml报错: QML Frame: Cannot anchor to an item that isn‘t a parent or sibling.

1、错误一:qrc:/main.qml:30:5: QML Frame: Cannot anchor to an item that isnt a parent or sibling. QML的anchor必须定位父级对象或者同级对象,不能定位到其他如:同级对象的子对象。 //main.qml import QtQuick 2.0 import QtQuick.Con…

Mybatis Day02

增删改查 环境准备 创建一个emp表创建一个新的springboot工程,选择mysql、lombok、mybatis依赖application.properties中引入数据库连接信息创建对应的实体类Emp准备Mapper接口EmpMapper,mapper代表程序运行时自动创建接口的代理对象,并放入…

[office] Excel 数据库函数条件区域怎样设置 #笔记#笔记

Excel 数据库函数条件区域怎样设置 以下面的数据表格为例,对于条件区域的设置,有几方面需要注意的内容,下面就一起看看如何对Excel 数据库函数条件区域设置的吧。希望会大家有所帮助 以下面的数据表格为例,对于条件区域的设置&am…

【硬核】javascript轻松实现自动化批量取消某音用户关注功能

🚀 个人主页 极客小俊 ✍🏻 作者简介:web开发者、设计师、技术分享博主 🐋 希望大家多多支持一下, 我们一起学习和进步!😄 🏅 如果文章对你有帮助的话,欢迎评论 💬点赞&a…

VMware虚拟机网络配置

VMware虚拟机网络配置 桥接模式NAT网络 桥接模式 桥接模式其实就是借助你宿主机上的网卡进行联网和通信,所以相当于虚拟机和宿主机平级,处于同一个网段中。 配置要点: 注意选择正确的宿主机网卡 查看宿主机的网络信息,这些信息指…

kali无线渗透之用wps加密模式破解出wpa模式的密码12

WPS(Wi-Fi Protected Setup,Wi-Fi保护设置)是由Wi-Fi联盟推出的全新Wi-Fi安全防护设定标准。该标准推出的主要原因是为了解决长久以来无线网络加密认证设定的步骤过于繁杂之弊病,使用者往往会因为步骤太过麻烦,以致干脆不做任何加密安全设定&…

哈希切分

目录 一 二 三 2.单个子文件太大怎么办?(分两种情况讨论) 一 这样的题目典型就是KV模型的问题,即通过key IP找对应的value 出现次数,对于KV模型的问题首先想到的就是用map来统计次数,但是100G大小的文件…

Windows11通过SMB映射NAS网络驱动磁盘

环境 NAS:威联通TS-416 操作系统:Windows11 第一步 连接NAS winr 打开运行,输入NAS局域网IP地址,按照如下的格式输入 然后输入NAS的账号和密码就可以通过SMB连接到NAS了 第二步 映射网络驱动器 举个栗子:右键Stora…

【AIGC】Stable Diffusion的模型入门

下载好相关模型文件后,直接放入Stable Diffusion相关目录即可使用,Stable Diffusion 模型就是我们日常所说的大模型,下载后放入**\webui\models\Stable-diffusion**目录,界面上就会展示相应的模型选项,如下图所示。作者…

[GXYCTF2019]禁止套娃

进来发现只有这句话,习惯性访问一下flag.php,发现不是404,那就证明flag就在这了,接下来要想办法拿到flag.php的源码。 这道题是.git文件泄露网页源码,githack拿到index.php源码 这里观察到多次判断,首先要…

Unity如何修改预制体(预制件)?

文章目录 19 复制复制复制,预制体与变体 19 复制复制复制,预制体与变体 【预制件】 预制件作用:方便复用 【预制件】的制作 直接拖拽,从层级面板 -> 项目面板。层级面板中当前图标会变蓝,子物体名字变蓝色。预制件…

node+vue3+mysql前后分离开发范式——实现对数据库表的增删改查

文章目录 ⭐前言⭐ 功能设计与实现💖 node后端操作数据库实现增删改查💖 vue3前端实现增删改查⭐ 效果⭐ 总结⭐ 结束⭐结束⭐前言 大家好,我是yma16,本文分享关于 node+vue3+mysql前后分离开发范式——实现对数据库表的增删改查。 技术选型 前端:vite+vue3+antd 后端:…

Javaweb之SpringBootWeb案例之AOP核心概念的详细解析

2.3 AOP核心概念 通过SpringAOP的快速入门,感受了一下AOP面向切面编程的开发方式。下面我们再来学习AOP当中涉及到的一些核心概念。 1. 连接点:JoinPoint,可以被AOP控制的方法(暗含方法执行时的相关信息) 连接点指的…

边缘计算:重塑数字世界的未来

引言 随着物联网(IoT)设备的激增和5G网络的普及,我们正站在一个计算模式的新纪元门槛上——边缘计算。这一技术范式将数据处理和分析推向网络的边缘,即设备或终端,为实时性要求较高的应用提供了前所未有的可能性。 目…

保育员答案怎么查找? #经验分享#微信

在大学生的学习过程中,我们经常会遇到各种难题和疑惑。有时候,我们可能会花费大量的时间和精力去寻找答案,但结果却并不尽如人意。为了帮助大家更好地解决这个问题,今天我要向大家介绍几款备受大学生欢迎的搜题软件,它…

问题:由于环境因素或人为因素干扰,致使土地生态系统的结构和功能失调,引起() #学习方法#经验分享

问题:由于环境因素或人为因素干扰,致使土地生态系统的结构和功能失调,引起() A.土地退化 B.土壤污染 C.生态平衡失调 D.土地沙化 参考答案如图所示

HCIA-HarmonyOS设备开发认证V2.0-轻量系统内核基础-互斥锁mux

目录 一、互斥锁基本概念二、互斥锁运行机制三、互斥锁开发流程四、互斥锁使用说明五、互斥锁接口六、代码分析(待续...) 一、互斥锁基本概念 互斥锁又称互斥型信号量,是一种特殊的二值性信号量,用于实现对共享资源的独占式处理。…

应急响应实战笔记02日志分析篇(3)

第3篇:Web日志分析 ox01 Web日志 Web访问日志记录了Web服务器接收处理请求及运行时错误等各种原始信息。通过对WEB日志进行的安全分析,不仅可以帮助我们定位攻击者,还可以帮助我们还原攻击路径,找到网站存在的安全漏洞并进行修复。 我们来…

问题:从完整的问题解决过程来看,( )是首要环节。A.理解问题 B.提出假设C.发现问题 D.检验假设 #学习方法#学习方法

问题:从完整的问题解决过程来看,( )是首要环节。A.理解问题 B.提出假设C.发现问题 D.检验假设 A.理解问题 B.提出假设 C.发现问题 参考答案如图所示