5.2.数据结构-c/c++二叉树详解(下篇)(算法面试题)

2024-09-04 03:04

本文主要是介绍5.2.数据结构-c/c++二叉树详解(下篇)(算法面试题),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

本章所有代码请见:5.3.数据结构-c/c++二叉树代码-CSDN博客

上篇:5.数据结构-c/c++二叉树详解(上篇)(遍历方法,完全二叉树)-CSDN博客 

目录

1 求二叉树 第k层的节点

2 查找一个节点是否在二叉树中

3 求二叉树节点的个数

4 求二叉树叶子节点的个数

5 求树的深度

6 判断一棵树是否为完全二叉树


1 求二叉树 第k层的节点

        思路:我们要求第k层结点个数,需要传入参数k。利用递归思想,我们从上到下没下一层,让k--,当k=1的时候到达第k层。

        然后我们让每一个结果返回1即可

如下图,计算第三层结点的递归图

      

函数返回值的返回图

这样就能够准确得出k层的节点数

代码

//求二叉树第k层结点的个数
int TreeKSize(BTNode* root, int k)
{if (root == nullptr)return 0;if (k == 1)return 1;return TreeKSize(root->left, k - 1) + TreeKSize(root->right, k - 1);
}

2 查找一个节点是否在二叉树中

只需使用遍历方法遍历一遍同时查找即可,遍历方法详见二叉树遍历

//查找某个结点是否在二叉树中
BTNode* TreeFind(BTNode* root, BTDataType x)
{if (root == nullptr)return nullptr;if (root->data == x)return root;BTNode* node1 = TreeFind(root->left, x);if (node1 != nullptr)return node1;BTNode* node2 = TreeFind(root->right, x);if (node2 != nullptr)return node2;
}

3 求二叉树节点的个数

有两种方法

1.遍历

//遍历
void TreeSize1(BTNode* root, int* psize)
{if (root == nullptr)return;else(*psize)++;TreeSize1(root->left, psize);TreeSize1(root->right, psize);
}

2.分治

分治的思想类似于第1题,求k个节点个数。

第一题让k层节点都返回1,最后得到答案

而这里让每一个节点都返回1,最后就能返回节点的个数

//分治
int TreeSize2(BTNode* root)
{if (root == nullptr)return 0;elsereturn 1 + TreeSize2(root->left) + TreeSize2(root->right);
}

4 求二叉树叶子节点的个数

与第一题类似,这里只要保证返回的条件是叶子节点(左右孩子都为空的节点)

//求叶子节点个数
int TreeLeafSize(BTNode* root)
{if (root == nullptr)return 0;//保证遇到叶子节点的时候返回1if (root->left == nullptr && root->right == nullptr)return 1;//分治且其他所有节点都不返回值return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

5 求树的深度

求一棵树的深度,只要找到最深一层的结点即可

如下图,红色表示深一层结点向上返回,黑色表示其他节点返回

每一次返回的时候,返回较大的一个值即可

//求树的深度
int TreeDepth(BTNode* root)
{if (root == nullptr)return 0;int leftdepth = TreeDepth(root->left);int rightdepth = TreeDepth(root->right);if (leftdepth > rightdepth)return leftdepth + 1;elsereturn rightdepth + 1;
}

6 判断一棵树是否为完全二叉树

        要判断一棵树是否为完全二叉树,只要判断树最后一层结点是否只集中在左侧且其他层结点都是满的。

思路:

        我们依次将所有结点放入一个队列中(如果遇到空结点也放入队列中),遇到空结点的时候退出,再判断队列中还有无结点,如果有不为空的结点,则说明该二叉树不是完全二叉树。

例图:

代码

//判断一棵树是否为完全二叉树
bool TreeComplete(BTNode* root)
{queue<BTNode*> q;//空树是完全二叉树if (!root)	return true;q.push(root);while (!q.empty()){BTNode* front = q.front();q.pop();if (front == nullptr)break;q.push(front->left);q.push(front->right);}//判断while (!q.empty()){BTNode* front = q.front();q.pop();if (front != nullptr)return false;}return true;
}

7 简单测试

测试代码

int main()
{BTNode* A = CreatNode('A');BTNode* B = CreatNode('B');BTNode* C = CreatNode('C');BTNode* D = CreatNode('D');BTNode* E = CreatNode('E');BTNode* F = CreatNode('F');BTNode* G = CreatNode('G');A->left = B;A->right = C;B->left = D;B->right = E;//C->left = F;C->right = G;int sizeA = 0;TreeSize1(A, &sizeA);cout << "TreeSize1:" << sizeA << endl;cout << "TreeSize2:" << TreeSize2(A) << endl;cout << "TreeLeafSize:" << TreeLeafSize(A) << endl;cout << "TreeDepth:" << TreeDepth(A) << endl;cout << "k=3 TreeKsize:" << TreeKSize(A, 3) << endl;if (TreeComplete(A))cout << "是完全二叉树" << endl;elsecout << "不是完全二叉树" << endl;return 0;
}

测试结果

注释掉F结点

这篇关于5.2.数据结构-c/c++二叉树详解(下篇)(算法面试题)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1134811

相关文章

SpringIoC与SpringDI详解

《SpringIoC与SpringDI详解》本文介绍了Spring框架中的IoC(控制反转)和DI(依赖注入)概念,以及如何在Spring中使用这些概念来管理对象和依赖关系,感兴趣的朋友一起看看吧... 目录一、IoC与DI1.1 IoC1.2 DI二、IoC与DI的使用三、IoC详解3.1 Bean的存储

Spring Cloud之注册中心Nacos的使用详解

《SpringCloud之注册中心Nacos的使用详解》本文介绍SpringCloudAlibaba中的Nacos组件,对比了Nacos与Eureka的区别,展示了如何在项目中引入SpringClo... 目录Naacos服务注册/服务发现引⼊Spring Cloud Alibaba依赖引入Naco编程s依

C语言中的浮点数存储详解

《C语言中的浮点数存储详解》:本文主要介绍C语言中的浮点数存储详解,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、首先明确一个概念2、接下来,讲解C语言中浮点型数存储的规则2.1、可以将上述公式分为两部分来看2.2、问:十进制小数0.5该如何存储?2.3 浮点

大数据spark3.5安装部署之local模式详解

《大数据spark3.5安装部署之local模式详解》本文介绍了如何在本地模式下安装和配置Spark,并展示了如何使用SparkShell进行基本的数据处理操作,同时,还介绍了如何通过Spark-su... 目录下载上传解压配置jdk解压配置环境变量启动查看交互操作命令行提交应用spark,一个数据处理框架

MySQL中COALESCE函数示例详解

《MySQL中COALESCE函数示例详解》COALESCE是一个功能强大且常用的SQL函数,主要用来处理NULL值和实现灵活的值选择策略,能够使查询逻辑更清晰、简洁,:本文主要介绍MySQL中C... 目录语法示例1. 替换 NULL 值2. 用于字段默认值3. 多列优先级4. 结合聚合函数注意事项总结C

Java实现数据库图片上传功能详解

《Java实现数据库图片上传功能详解》这篇文章主要为大家详细介绍了如何使用Java实现数据库图片上传功能,包含从数据库拿图片传递前端渲染,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1、前言2、数据库搭建&nbsChina编程p; 3、后端实现将图片存储进数据库4、后端实现从数据库取出图片给前端5、前端拿到

Win32下C++实现快速获取硬盘分区信息

《Win32下C++实现快速获取硬盘分区信息》这篇文章主要为大家详细介绍了Win32下C++如何实现快速获取硬盘分区信息,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 实现代码CDiskDriveUtils.h#pragma once #include <wtypesbase

Windows命令之tasklist命令用法详解(Windows查看进程)

《Windows命令之tasklist命令用法详解(Windows查看进程)》tasklist命令显示本地计算机或远程计算机上当前正在运行的进程列表,命令结合筛选器一起使用,可以按照我们的需求进行过滤... 目录命令帮助1、基本使用2、执行原理2.1、tasklist命令无法使用3、筛选器3.1、根据PID

MySql中的数据库连接池详解

《MySql中的数据库连接池详解》:本文主要介绍MySql中的数据库连接池方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录mysql数据库连接池1、概念2、为什么会出现数据库连接池3、原理4、数据库连接池的提供商5、DataSource数据源6、DBCP7、C

Spring-AOP-ProceedingJoinPoint的使用详解

《Spring-AOP-ProceedingJoinPoint的使用详解》:本文主要介绍Spring-AOP-ProceedingJoinPoint的使用方式,具有很好的参考价值,希望对大家有所帮... 目录ProceedingJoinPoijsnt简介获取环绕通知方法的相关信息1.proceed()2.g