c语言——二叉树

目录

目录

二叉树关键概念理解

一颗拥有1000个结点的树度为4，则它的最小深度是？

那么对于二叉树，只掌握这些是远远不够的，我们还需要掌握几个最基本的经典问题，

求二叉树大小

求叶子结点个数 

求深度

求第k层的结点个数

寻找值为k的结点

遍历打印

判断二叉树是否是完全二叉树

销毁

二叉树的构建 

 1.    求二叉树大小

 2.    求叶子结点个数 

3.求深度

需要注意的是：需要每次存储每次递归的大小， 优化时间

4.求第k层的结点个数

5.寻找值为k的结点

 需要注注意的是需要存储每次递归的ret，优化时间

6.层序遍历打印

前序： 根->左子树->右子树

中序： 左子树->根->右子树

后序： 左子树->右子树->根

层序 ：一层一层打印

7. 判断二叉树是否是完全二叉树

8.销毁

一颗拥有1000个结点的树度为4，则它的最小深度是？

那么对于二叉树，只掌握这些是远远不够的，我们还需要掌握几个最基本的经典问题，

求二叉树大小

求叶子结点个数 

求深度

求第k层的结点个数

寻找值为k的结点

遍历打印

判断二叉树是否是完全二叉树

销毁

二叉树的构建 

 1.    求二叉树大小

 2.    求叶子结点个数 

3.求深度

需要注意的是：需要每次存储每次递归的大小， 优化时间

4.求第k层的结点个数

5.寻找值为k的结点

 需要注注意的是需要存储每次递归的ret，优化时间

6.层序遍历打印

前序： 根->左子树->右子树

中序： 左子树->根->右子树

后序： 左子树->右子树->根

层序 ：一层一层打印

7. 判断二叉树是否是完全二叉树

8.销毁

二叉树关键概念理解

二叉树的概念在这里就不进行过多的赘述，那么主要说一下我认为重要的部分，

第一点就是二叉树里面部分概念的理解：

就比如说，你对于如何构建二叉树，掌握的十分深刻，但刷题的时候对于一些题目所给的概念不清楚，导致看不明白题目，这课不好，

二叉树的概念如下图所示,其实都很简单，主要是当给他的名字时，你明不明白。

还有对于满二叉树与完全二叉树 需要注意的就是完全二叉树，最后一层，从左到右时必须连续的。 

 经过看过这两张图后，再加上我们原本的二叉树基础，我们看几道题：

一颗拥有1000个结点的树度为4，则它的最小深度是？

 如果我们了解度的概念，那么就很好计算出答案。

那么思路：最小度数就是当每个结点都是满的情况下，那么就为最小深度，

设高度为h，那么每个结点都是满的情况下，通过数学计算得出，此时总共结点数：（4^h-1)/3,那么h=5时，最大结点数为341，h=6时，为1365，

那么最小深度就为6.

 2-3树是一种特殊的树，它满足两个条件：

(1) 每个内部结点有两个或三个子结点

(2) 所有的叶结点到根的距离相同

如果一颗2-3树有10个结点，那么它有( )个叶结点

对于本道题，经过分析，我们得知，第二层一定是只有两个结点,或三个结点，

当为三个结点时，只有这一种情况：

 当为二个结点时：

再最多的情况下也只可以放九个

所以就只有6个叶子结点。

那么对于二叉树，只掌握这些是远远不够的，我们还需要掌握几个最基本的经典问题，

  1. 求二叉树大小

  2. 求叶子结点个数 

  3. 求深度

  4. 求第k层的结点个数

  5. 寻找值为k的结点

  6. 遍历打印

  7. 判断二叉树是否是完全二叉树

  8. 销毁

二叉树的构建 

//二叉树
typedef int BTDataType;
typedef struct BTNode
{
	BTDataType val;
	struct BTNode* left;
	struct BTNode* right;
}BTNode;
BTNode* Creat_Node()
{
	BTNode* Node1 = BuyNode(1);
	BTNode* Node2 = BuyNode(2);
	BTNode* Node3 = BuyNode(3);
	BTNode* Node4 = BuyNode(4);
	BTNode* Node5 = BuyNode(5);
	BTNode* Node6 = BuyNode(6);
	//BTNode* Node7 = BuyNode(7);
	Node1->left = Node2;
	Node1->right = Node4;
	Node2->left = Node3;
	Node4->left = Node5;
	Node4->right = Node6;
	//Node6->right = Node7;
	return Node1;
}

BTNode* BuyNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc fail");
	}
	node->val = x;
	node->left = NULL;
	node->right = NULL;
	return node;
}

 接下来依次介绍

 1.    求二叉树大小

代码实现：

int BT_Size(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return BT_Size(root->left) + BT_Size(root->right) + 1;
}

或者： 

int BT_Size(BTNode* root)
{
	return root == NULL ? 0 : BT_Size(root->left) +
		BT_Size(root->right) + 1;
}

 2.    求叶子结点个数 

 叶子结点有一个特点，那么就是左节点与右节点全为空，只要抓住这一点特点，利于递归，还是很好实现的。

int BT_Leaf_Size(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return BT_Leaf_Size(root->left) +
		BT_Leaf_Size(root->right);
}

3.求深度

求二叉树深度可以转化为求左子树的深度，与右子树的深度，然后比比谁的大，然后左子树深度求法又可以分为，求左子树的左子树与右子树的深度，以此类推。

需要注意的是：需要每次存储每次递归的大小， 优化时间

int BT_Depth_Size(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int left_Depth_Size = BT_Depth_Size(root->left);
	int right_Depth_Size = BT_Depth_Size(root->right);
	return left_Depth_Size > right_Depth_Size ?
		BT_Depth_Size(root->left) + 1 : 
		BT_Depth_Size(root->right) + 1;
}

4.求第k层的结点个数

 思路就是首先我们要先找到第k层所在位置，然后每找到一个就利用递归然会去1；

int BT_Size_Levre_k(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BT_Size_Levre_k(root -> left, k - 1) +
		BT_Size_Levre_k(root -> right, k - 1);
}

5.寻找值为k的结点

 需要注注意的是需要存储每次递归的ret，优化时间

BTNode* BTFind_Data_k(BTNode* root, int k)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->val == k)
	{
		return root;
	}
	BTNode* ret1 = BTFind_Data_k(root->left, k);
	if (ret1)
	{
		return ret1;
	}
	BTNode* ret2 = BTFind_Data_k(root->right, k);
	if (ret2)
	{
		return ret2;
	}
	return NULL;
}

6.层序遍历打印

前序： 根->左子树->右子树

void Prev_Order(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	printf("%d ", root->val);
	Prev_Order(root->left);
	Prev_Order(root->right);
}

中序： 左子树->根->右子树

void In_Order(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	In_Order(root->left);
	printf("%d ", root->val);
	Prev_Order(root->right);
}

后序： 左子树->右子树->根

void Post_Order(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	In_Order(root->left);
	Prev_Order(root->right);
	printf("%d ", root->val);
}

层序 ：一层一层打印

层序打印需要运用到栈，这里不提供栈的实现了，只提供实现层序打印的代码

void Lever_Order(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%d ", front->val);
		if (front->left)
		{
			QueuePush(&q, front->left);
		}
		if (front->right)
		{
			QueuePush(&q, front->right);
		}
	}
	printf("\n");
}

7. 判断二叉树是否是完全二叉树

 检查是否为完全二叉树，也是利用栈的知识来实现，因为在层序遍历的时候，是出完一层的时候也会在进完下一层，并且顺序是完全按照一层一层从左到右

所以实现思路就为，先找到第一个为空的结点，然后查看他后面的结点是不是为空，如果为空，那么就为完全二叉树，反之不是。

bool BinaryTreeComplete(BTNode* root)
{
	//层序遍历，从第一个为空开始，向后看是否为空
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front == NULL)
		{
			break;
		}
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
	}
	//检查后面是否为空  ，有非空即不是完全二叉树
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front != NULL)
		{
			return false;
		}
		if (front->left)
		{
			QueuePush(&q, front->left);
		}
		if (front->right)
		{
			QueuePush(&q, front->right);
		}
	}
	return true;
}

8.销毁

void BinaryTreeDestory(BTNode* root)//后序顺序释放
{
	if (root == NULL)
	{
		return;
	}
	BinaryTreeDestory(root->left);
	BinaryTreeDestory(root->right);
	free(root);
}

还有一些结论：

1：二叉树第i层上的结点数目最多为2i-1(i>=1)

2：深度为k的二叉树至多有2^(k) - 1个结点（k>=1）,叶子节点为 2^(k - 1) 

3：包含n个结点的二叉树的高度至少为( log2(n) )+1

4：在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1

5：leftchild=parent*2+1;   rightchild=parent*2+2;

6:  parent=(child-1)/2;

7: 令度为0，的结点个数为N0,度为2的个数为N2

那么N0=N2+1；

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

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

相关文章

多线程编程9——线程池

多线程编程9——线程池

一、为什么要引入线程池？ 虽然对比进程，线程已经很轻量了，创建销毁调度线程都更高效。但是随着并发程度的提高，我们对于性能要求的标准也越来越高，当我们需要频繁创建销毁调度线程时，就发现线程也没有那么…
阅读更多...
【基础算法】二分查找

【基础算法】二分查找

1.二分查找 二分查找 思路&#xff1a; 朴素二分模版 class Solution { public:int search(vector<int>& nums, int target) {int l 0, r nums.size() - 1;while(l < r){int mid (l r) / 2;if(nums[mid] < target) l mid 1;else if(nums[mid] > ta…
阅读更多...
综合性练习（后端代码练习1）——加法计算器

综合性练习（后端代码练习1）——加法计算器

目录 一、准备工作 二、约定前后端交互接口 1、概念介绍 2、需求分析 3、接口定义 请求参数 响应数据 三、服务器代码 四、前端页面代码 五、运行测试 遇到问题如何解决&#xff1f; 需求&#xff1a;输入两个整数&#xff0c;点击 “点击相加” 按钮&#xff0c;显…
阅读更多...
JAVA顺序表相关习题1

JAVA顺序表相关习题1

1.笔试题:cvte str1 :welcome to cvte str2:come 描述:删除第一个字符串当中出现的所有的第二个字符串的字符!结果:wlt vt 要求 用ArrayList完成! public class Test {public static List<Character> findSameWords(String u1, String u2){List<Character> listn…
阅读更多...
前端请求没问题，后端正常运行，但查不出数据

前端请求没问题，后端正常运行，但查不出数据

写代码时写得快了些&#xff0c;Orders.的订单状态写错了CONFIRMED 改成COMPLETED
阅读更多...
二、再识VUE-MVVM

二、再识VUE-MVVM

一、初识VUE 二、再识VUE-MVVM 三、VUE数据代理 MVVM Vue.js 专注于 MVVM 模型的 ViewModel 层。它通过双向数据绑定把 View 层和 Model 层连接了起来。实际的 DOM 封装和输出格式都被抽象为了 Directives 和 Filters。 ViewModel 一个同步 Model 和 View 的对象。在 Vue.js…
阅读更多...
汇川AM400PLC编码器转速测量功能块(M法测速)

汇川AM400PLC编码器转速测量功能块(M法测速)

M法测速的原理和相关代码，大家可以参考相关专栏文章，常用链接如下： 1、编码器M法测速仿真 编码器M法测速仿真(Simulink)_mt法测速 simulink-CSDN博客文章浏览阅读2k次。编码器M法和T法测速的详细讲解可以参看下面的文章链接，这里不再赘述，这里主要介绍Simulink里建模仿真…
阅读更多...
（06）vite与ts的结合

（06）vite与ts的结合

文章目录 系列全集package.json在根目录创建 tsconfig.json 文件在根目录创建 vite.config.ts 文件index.html额外的类型声明 系列全集 &#xff08;01&#xff09;vite 从启动服务器开始 &#xff08;02&#xff09;vite环境变量配置 &#xff08;03&#xff09;vite 处理 c…
阅读更多...
详细介绍如何使用YOLOv9 在医疗数据集上进行实例分割-含源码+数据集下载

详细介绍如何使用YOLOv9 在医疗数据集上进行实例分割-含源码+数据集下载

深度学习彻底改变了医学图像分析。通过识别医学图像中的复杂模式，它可以帮助我们解释有关生物系统的重要见解。因此，如果您希望利用深度学习进行医疗诊断，本文可以成为在医疗数据集上微调YOLOv9 实例分割的良好起点。 实例分割模型不是简单地将区域分类为属于特定细胞类型，…
阅读更多...
新质生产力实践，我用chatgpt开发网站

新质生产力实践，我用chatgpt开发网站

是的&#xff0c;我用chatgpt开发了一个网站&#xff0c;很轻松。 我之前一点不懂前端&#xff0c;也没有网站开发的代码基础&#xff0c;纯正的0基础。 从0开始到最后成品上线&#xff0c;时间总计起来大致一共花了2-3周的时间。 初始想法我是想给我公司开发一个网站&#…
阅读更多...
3月8日是星期六

3月8日是星期六

突然有查询特殊条件日期的需求。 <html> <title>3月8日是星期六</title> <center> <h1 id"h1"></h1> <div id"div"></div> </center> <script> var weekday [星期日, 星期一, 星期二, 星期…
阅读更多...
Eclipse：-Dmaven.multiModuleProjectDirectory system propery is not set.

Eclipse：-Dmaven.multiModuleProjectDirectory system propery is not set.

eclipse中使用maven插件的时候&#xff0c;运行run as maven build的时候报错 -Dmaven.multiModuleProjectDirectory system propery is not set. Check $M2_HOME environment variable and mvn script match. 可以设一个环境变量M2_HOME指向你的maven安装目录 M2_HOMED:\Apps\…
阅读更多...
echarts开发技巧

echarts开发技巧

tooltip 提示框组件相关的行为&#xff0c;必须引入提示框组件后才能使用。 tooltip: {trigger: axis,axisPointer: {type: cross,label: {backgroundColor: #6a7985,},},//为弹出层的value值增加百分号valueFormatter: function (value) {return value %}, }, tooltip.axi…
阅读更多...
碳课堂｜快速了解标准要点：ISO 14064-1

碳课堂｜快速了解标准要点：ISO 14064-1

为了提高企业组织碳排放报告信誉度&#xff0c;国际标准化组织&#xff08;ISO&#xff09;发布了ISO14064 标准&#xff08;全称&#xff1a;《ISO 14064-1组织层次上对温室气体排放和清除的量化和报告的规范及指南》&#xff09;&#xff0c;报告中详细规定了公司温室气体清单…
阅读更多...
确定性最大似然（DML）估计测角

确定性最大似然（DML）估计测角

1. 最大似然函数 贝叶斯方法是基于统计理论的一种经典方法&#xff0c;适合于有关参数估计问题。最大似然 (Maximum Likelihood&#xff0c;ML) 估计方法就是贝叶斯估计方法的一种特例&#xff0c;是在已知高斯噪声情况下的贝叶斯最优估计。在ML算法中&#xff0c;观测所得信号…
阅读更多...
品牌出海新篇章：独立站构建与流量转化策略

品牌出海新篇章：独立站构建与流量转化策略

在当今数字化时代&#xff0c;品牌出海已成为许多企业拓展国际市场的重要途径之一。在这个过程中&#xff0c;构建一个高效、专业的独立站&#xff0c;成为了品牌出海的重要一环。独立站不仅有助于企业塑造独特的品牌形象&#xff0c;更能通过精准的营销策略提高流量和转化率&a…
阅读更多...
乘用车整车太阳光模拟加速老化试验太阳光模拟器

乘用车整车太阳光模拟加速老化试验太阳光模拟器

1.阳光模拟试验介绍 太阳辐射会对室外停放的汽车内外饰件产生热效应和光化学效应&#xff0c;影响汽车内外饰件的外观、性能&#xff0c;对汽车质产生不利影响。按照汽车产环境试验标准的要求&#xff0c;汽车在研制定型之前应进行太阳辐射试验&#xff0c;以考虑其对太阳辐射环…
阅读更多...
微服务之分布式理论zookeeper概述

微服务之分布式理论zookeeper概述

一、分布式技术相关的理论 CAP理论 CAP定理(CAP theorem)&#xff0c;⼜被称作布鲁尔定理(Eric Brewer)&#xff0c;1998年第⼀次提出. 最初提出是指分布式数据存储不可能同时提供以下三种保证中的两种以上: (1) ⼀致性(Consistency): 每次读取收到的信息都是最新的; (2) …
阅读更多...
探索主播美颜工具与直播美颜SDK的技术奥秘

探索主播美颜工具与直播美颜SDK的技术奥秘

主播的形象美化是至关重要的一环&#xff0c;而实现这一目标的关键在于美颜工具和直播美颜SDK。接下来&#xff0c;我们将一同深入探索这些技术的奥秘&#xff0c;揭示它们背后的原理和工作方式。 一、美颜工具的背后 美颜工具是一类应用软件&#xff0c;旨在通过图像处理技术…
阅读更多...
树莓派点亮LED灯

树莓派点亮LED灯

简介 使用GPIO Zero library 的 Python库实现点亮LED灯。接线 树莓派引脚参考图如下&#xff1a; LED正极 接GPIO17 LED负极 接GND 权限 将你的用户加到gpio组中&#xff0c; 否则无法控制GPIO sudo usermod -a -G gpio 代码 from gpiozero import LED from time impor…
阅读更多...
最新文章

Copyright @ 2022~2023