wordpress 跟随插件/seo外链发布技巧
文章目录
- 1. 二叉树的性质
- 2. 链式结构二叉树
- 3. 二叉树链式结构的4种遍历方式
- 4. 二叉树节点个数
- 5. 二叉树的叶子节点个数
- 6. 二叉树第k层节点个数
- 7. 二叉树的高度/深度
- 8. 二叉树查找值为x的节点
- 9. 二叉树的销毁
- 10. 判断是否为完全二叉树
- 11. 二叉树练习题
- 11.1 单值二叉树
- 11.2 相同的树
- 11.3 另一棵树的子树
- 11.4 二叉树的前序遍历
- 11.5 二叉树遍历
1. 二叉树的性质
- 假设一个二叉树有a个度为2的节点,b个度为1的节点,c个度为0的节点,那么该二叉树的边数是2a+b == a+b+c-1
- 二叉树的边数等于其节点数-1
- 二叉树度为2的节点数等于度为0的节点数-1
- 完全二叉树的高度h = log2(n+1) 2为底,n+1为对数,n为二叉树节点数
- 若完全二叉树的节点数为2n个,那么它的叶子节点数为n
- 若完全二叉树的节点数为2n-1个,那么它的叶子节点数为n
2. 链式结构二叉树
- 链式二叉树的数据结构
3. 二叉树链式结构的4种遍历方式
- 前序遍历----根左右原则
//前序遍历
void PreOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}printf("%c ", root->data);PreOrder(root->left);PreOrder(root->right);
}
- 兄弟们,感受一下函数递归的暴力美学吧!
- 中序遍历----左根右原则
//中序遍历
void InOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return ;}InOrder(root->left);printf("%c ", root->data);InOrder(root->right);
}
- 后序遍历----左右根原则
//后序遍历
void PostOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%c ", root->data);
}
- 层序遍历
- 除了先序遍历、中序遍历、后序遍历外,还可以对二叉树进行层序遍历。设二叉树的根结点所在层数为1,层序遍历就是从所在二叉树的根结点出发,首先访问第一层的树根结点,然后从左到右访问第2层上的结点,接着是第三层的结点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历
- 实现层序遍历需要额外借助数据结构:队列
//层序遍历
void LevelOrder(BTNode* root)
{//队列Queue q;QueueInit(&q);//初始化QueuePush(&q, root);//根节点入队//队列不为空while (!QueueEmpty(&q)){BTNode* top = QueueFront(&q);//取队头QueuePop(&q);//销毁队头printf("%c ", top->data);//打印队头//取出的队头的左子结点不为空入队if (top->left){QueuePush(&q, top->left);}//取出的队头的右子结点不为空入队if (top->right){QueuePush(&q, top->right);}}QueueDestroy(&q);//销毁队列
}
4. 二叉树节点个数
//二叉树节点数个数
int BinaryTreeSize(BTNode* root)
{if (root == NULL){return 0;}return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
5. 二叉树的叶子节点个数
//二叉树的叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL){return 0;}if (root->left == NULL && root->right == NULL){return 1;}return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
6. 二叉树第k层节点个数
//二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == NULL){return 0;}if (k == 1){return 1;}return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}
7. 二叉树的高度/深度
//二叉树的高度/深度
int BinaryTreeDepth(BTNode* root)
{if (root == NULL){return 0;}int leftDep = BinaryTreeDepth(root->left);int rightDep = BinaryTreeDepth(root->right);return 1 + (leftDep > rightDep ? leftDep : rightDep);
}
8. 二叉树查找值为x的节点
//查找二叉树中值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode* leftFind = BinaryTreeFind(root->left, x);if (leftFind){return leftFind;}BTNode* rightFind = BinaryTreeFind(root->right, x);if (rightFind){return rightFind;}//二叉树没有这个节点return NULL;
}
9. 二叉树的销毁
//二叉树的销毁
void BinaryTreeDestory(BTNode** root)
{if (*root == NULL){return;}BinaryTreeDestory(&((*root)->left));BinaryTreeDestory(&((*root)->right));free(*root);*root = NULL;
}
10. 判断是否为完全二叉树
//判断二叉树是否为完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);//根节点入队//第一次遍历非空队列找NULLwhile (!QueueEmpty(&q)){BTNode* top = QueueFront(&q);//取队头QueuePop(&q);//出队头if (top == NULL){break;}QueuePush(&q, top->left);//队头的左孩子入队QueuePush(&q, top->right);//队头的右孩子入队}//第二次遍历找NULL后是否有非NULL节点while (!QueueEmpty(&q)){BTNode* top = QueueFront(&q);//取队头QueuePop(&q);//出队头if (top != NULL){QueueDestroy(&q);//销毁队列return false;}}//第二次循环中没有NULLQueueDestroy(&q);return true;
}
11. 二叉树练习题
11.1 单值二叉树
bool isUnivalTree(struct TreeNode* root)
{//如果根节点为NULL,它也是单值二叉树if(root == NULL){return true;}//如果根节点的左孩子节点存在且该节点的值不等于其左孩子节点的值if(root->left && root->val != root->left->val){return true;}//如果根节点的右孩子节点存在且该节点的值不等于其右孩子节点的值if(root->right && root->val != root->right->val){return true;}//说明当前节点和它的左孩子右孩子节点的值相等return isUnivalTree(root->left) && isUnivalTree(root->right);
}
11.2 相同的树
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);
}
11.3 另一棵树的子树
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;}//如果root和subRoot两个二叉树相同if(isSameTree(root,subRoot)){return true;}//root和subRoot不是相同的树//分别判断subRoot是否是root的左子树和右子树return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
}
11.4 二叉树的前序遍历
typedef struct TreeNode TreeNode;//求二叉树节点个数int TreeSize(TreeNode* root){if(root == NULL){return 0;}return 1 + TreeSize(root->left) + TreeSize(root->right);}//前序遍历--根左右void PreOrder(TreeNode* root,int* arr,int* p){if(root == NULL){return ;}arr[(*p)++] = root->val;PreOrder(root->left,arr,p);PreOrder(root->right,arr,p);}
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{//先求出二叉树节点的个数*returnSize = TreeSize(root);//为数组arr申请节点空间int* arr = (int*)malloc(sizeof(int)*(*(returnSize)));if(arr == NULL){exit(1);}int i = 0;PreOrder(root,arr,&i);return arr;
}
11.5 二叉树遍历
#include <stdio.h>
#include <stdlib.h>
typedef char BTDataType;
//创建二叉树的数据结构
typedef struct BinaryNode
{BTDataType data;struct BinaryNode* left;struct BinaryNode* right;
}BTNode;
//申请节点
BTNode* buyNode(char x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));node->data = x;node->left = node->right = NULL;return node;
}//创建二叉树---根左右
BTNode* CreaterTreeNode(char* arr, int* p)
{if(arr[*p] == '#'){(*p)++;return NULL;}//如果读取到的数组元素不是'#'BTNode* root = buyNode(arr[*p]);(*p)++;root->left = CreaterTreeNode(arr, p);root->right = CreaterTreeNode(arr, p);return root;
}
//中序遍历
void InOrder(BTNode* root)
{if(root == NULL){return;}//非空InOrder(root->left);printf("%c ",root->data);InOrder(root->right);
}
int main()
{//创建数组char arr[100];scanf("%s",arr);//读取字符串//创建二叉树int i = 0;//数组下标BTNode* root = CreaterTreeNode(arr,&i);//中序遍历InOrder(root);return 0;
}
相关文章:

【数据结构与算法】第9课—数据结构之二叉树(链式结构)
文章目录 1. 二叉树的性质2. 链式结构二叉树3. 二叉树链式结构的4种遍历方式4. 二叉树节点个数5. 二叉树的叶子节点个数6. 二叉树第k层节点个数7. 二叉树的高度/深度8. 二叉树查找值为x的节点9. 二叉树的销毁10. 判断是否为完全二叉树11. 二叉树练习题11.1 单值二叉树11.2 相同…...

【CSS】居中样式
对于行内元素,使用 text-align: center。对于已知宽度的块级元素,使用 margin: 0 auto。对于需要灵活布局的元素,使用 Flexbox 或 Grid。 flex .parent {display: flex;justify-content: center; /* 水平居中 */align-items: center; /* 垂…...

Vite环境下uniapp Vue 3项目添加和使用环境变量的完整指南
一、引言 在uniapp项目中,合理配置环境变量对于提高开发效率和保障项目安全至关重要。Vite作为新一代的前端构建工具,为环境变量的管理提供了简洁而强大的支持。下面,我们将一步步学习如何在Vite环境下为uniapp Vue 3项目添加和使用环境变量…...

mysql-springboot netty-flink-kafka-spark(paimon)-minio
1、下载spark源码并编译 mkdir -p /home/bigdata && cd /home/bigdata wget https://archive.apache.org/dist/spark/spark-3.4.3/spark-3.4.3.tgz 解压文件 tar -zxf spark-3.4.3.tgz cd spark-3.4.3 wget https://raw.githubusercontent.com/apache/incubator-celeb…...

讨论一个mysql事务问题
最近在阅读一篇关于隔离级别的文章,文章中提到了一种场景,我们下面来分析一下。 文章目录 1、实验环境2、两个实验的语句执行顺序3、关于start transaction和start transaction with consistent snapshot4、实验结果解释4.1、实验14.2、实验24.3、调整实…...

pytest插件精选:提升测试效率与质量
pytest作为Python生态系统中备受推崇的测试框架,以其简洁、灵活和可扩展性赢得了广泛的认可。通过合理使用pytest的各种插件,可以显著提升测试效率、增强测试的可读性和可维护性。 pytest-sugar:提升测试体验 pytest-sugar是一款增强版的py…...

HTB:Sightless[WriteUP]
目录 连接至HTB服务器并启动靶机 使用nmap对靶机TCP端口进行开放扫描 继续使用nmap对靶机开放的TCP端口进行脚本、服务扫描 首先尝试对靶机FTP服务进行匿名登录 使用curl访问靶机80端口 使用浏览器可以直接访问该域名 使用浏览器直接访问该子域 Getshell 横向移动 查…...

国产化浪潮下,高科技企业如何选择合适的国产ftp软件方案?
高科技企业在数字化转型和创新发展中,数据资产扮演着越来越重要的角色。在研发过程中产生的实验数据、设计文档、测试结果等,专利、商标、版权之类的创新成果等,随着信息量急剧增加和安全威胁的复杂化,传统的FTP软件已经不能满足这…...

自注意力机制
当输入一系列向量,想要考虑其中一个向量与其他向量之间的关系,决定这个向量最后的输出 任意两个向量之间的关系计算 计算其他向量对a1的关联性 多头注意力机制 图像也可以看成一系列的向量,交给自注意力机制处理,CNN是特殊的自注意…...

抽象工厂模式详解
1. 引言 1.1 设计模式概述 设计模式(Design Patterns)是软件开发中解决常见问题的一种最佳实践。它们通过总结经验,提供了一套被验证有效的代码结构和设计原则,帮助开发者提高代码的可维护性、可重用性和可扩展性。 设计模式主…...

【Linux】软硬链接和动静态库
🔥 个人主页:大耳朵土土垚 🔥 所属专栏:Linux系统编程 这里将会不定期更新有关Linux的内容,欢迎大家点赞,收藏,评论🥳🥳🎉🎉🎉 文章目…...

HarmonyOS入门 : 获取网络数据,并渲染到界面上
1. 环境搭建 开发HarmonyOS需要安装DevEco Studio,下载地址 : https://developer.huawei.com/consumer/cn/deveco-studio/ 2. 如何入门 入门HarmonyOS我们可以从一个实际的小例子入手,比如获取网络数据,并将其渲染到界面上。 本文就是基于…...

【贪心】【哈希】个人练习-Leetcode-1296. Divide Array in Sets of K Consecutive Numbers
题目链接:https://leetcode.cn/problems/divide-array-in-sets-of-k-consecutive-numbers/description/ 题目大意:给出一个数组nums[]和一个数k,求nums[]能否被分成若干个k个元素的连续的子列。 思路:比较简单,贪心就…...

【数据库实验一】数据库及数据库中表的建立实验
目录 实验1 学习RDBMS的使用和创建数据库 一、 实验目的 二、实验内容 三、实验环境 四、实验前准备 五、实验步骤 六、实验结果 七、评价分析及心得体会 实验2 定义表和数据库完整性 一、 实验目的 二、实验内容 三、实验环境 四、实验前准备 五、实验步骤 六…...

Web服务nginx基本实验
安装软件: 启动服务: 查看Nginx服务器的网络连接信息,监听的端口: 查看默认目录: 用Windows访问服务端192.168.234.111的nginx服务:(防火墙没有放行nginx服务,访问不了) …...

Ubuntu实现双击图标运行自己的应用软件
我们知道在Ubuntu上编写程序,最后编译得到的是一个可执行文件,大致如下 然后要运行的时候在终端里输入./hello即可 但是这样的话感觉很丑很不方便,下边描述一种可以类似Windows上那种双击运行的实现方式。 我们知道Ubuntu是有一些自带的程序…...

js id字符串转数组
将一个逗号分隔的字符串(例如 "12,123,213,")转换为一个 JavaScript 数组,并去除多余的逗号,可以使用以下几种方法。这里我将展示几种常见的方式: 方法 1: 使用 split 和 filter 你可以使用 split 方法将字…...

《手写Spring渐进式源码实践》实践笔记(第十八章 JDBC功能整合)
文章目录 第十八章 JDBC功能整合背景技术背景JDBC JdbcTemplate关键特性 用法示例业务背景 目标设计实现代码结构类图实现步骤 测试事先准备属性配置文件测试用例测试结果: 总结 第十八章 JDBC功能整合 背景 技术背景 JDBC JDBC(Java Database Conne…...

边缘计算在智能交通系统中的应用
💓 博客主页:瑕疵的CSDN主页 📝 Gitee主页:瑕疵的gitee主页 ⏩ 文章专栏:《热点资讯》 边缘计算在智能交通系统中的应用 边缘计算在智能交通系统中的应用 边缘计算在智能交通系统中的应用 引言 边缘计算概述 定义与原…...

HTML5+css3(浮动,浮动的相关属性,float,解决浮动的塌陷问题,clear,overflow,给父亲盒子加高度,伪元素)
浮动的相关属性 以下使浮动的常用属性值: float: 设置浮动 以下属性: left : 设置左浮动 right : 设置右浮动 none :不浮动,默认值clear 清除浮动 清除前面兄弟元素浮动元素的响应 以下属性: left &…...

【C++ 滑动窗口】2134. 最少交换次数来组合所有的 1 II
本文涉及的基础知识点 C算法:滑动窗口及双指针总结 LeetCode2134. 最少交换次数来组合所有的 1 II 交换 定义为选中一个数组中的两个 互不相同 的位置并交换二者的值。 环形 数组是一个数组,可以认为 第一个 元素和 最后一个 元素 相邻 。 给你一个 二…...

使用 PyTorch 实现并测试 AlexNet 模型,并使用 TensorRT 进行推理加速
本篇文章详细介绍了如何使用 PyTorch 实现经典卷积神经网络 AlexNet,并利用 Fashion-MNIST 数据集进行训练与测试。在训练完成后,通过 TensorRT 进行推理加速,以提升模型的推理效率。 本文全部代码链接:全部代码下载 环境配置 为了保证代码在 GPU 环境下顺利运行,我们将…...

Python 数据可视化详解教程
Python 数据可视化详解教程 数据可视化是数据分析中不可或缺的一部分,它通过图形化的方式展示数据,帮助我们更直观地理解和分析数据。Python 作为一种强大的编程语言,拥有丰富的数据可视化库,如 Matplotlib、Seaborn、Plotly 和 …...

springboot集成opencv开源计算机视觉库
最近项目需要用到opencv,网上看到很多资料都是下载安装并且引入jar包与dll文件,感觉很麻烦,不是我想要的,于是花时间折腾了下,不需要任何安装与引入jar包与dll文件,简单方便,快速上手。 先说说…...

CCF ChinaOSC |「开源科学计算与系统建模openSCS专题分论坛」11月9日与您相约深圳
2024年11月9日至10日,以“湾区聚力 开源启智”为主题的2024年中国计算机学会中国开源大会(CCF ChinaOSC)将在深圳召开。大会将汇聚国内外学术界、顶尖科技企业、科研机构及开源社区的精英力量,共同探索人工智能技术和人类智慧的无…...

2024年11月8日上海帆软用户大会
2024年11月8日上海帆软用户大会 2024年11月8日,上海成功举办了帆软用户大会,主题为“数字聚力,绽放新机”。大会汇聚了众多行业专家和企业代表,共同探讨数字化转型和商业智能领域的最新趋势和实践。 大会亮点: 专家…...

信息泄露漏洞一文速通
文章目录 信息泄露漏洞一文速通敏感信息の概念敏感信息の分类企业敏感信息用户敏感信息站点敏感信息 如何挖掘信息泄露漏洞?信息泄露风险清单(checklist)未授权访问类文件与数据泄露开发与调试信息泄露公共配置文件泄露其他敏感信息泄露点 威…...

Android 启动时应用的安装解析过程《二》
上一篇内容说到InitAppsHelper这个类的initSystemApps函数,只说了一下几个重要参数的来源还没展开,这里继续,有兴趣的可以看链接: Android 启动时应用的安装解析过程《一》 一、系统应用的扫描安装 /*** Install apps from system dirs.*/Gu…...

智谱AI:ChatGLM强大的生成式语言模型
目录 智谱AI:ChatGLM强大的生成式语言模型 一、ChatGLM的定义与特点 二、ChatGLM的应用场景 三、举例说明 四、注意事项 智谱AI:ChatGLM强大的生成式语言模型 它通过对话的方式能够生成自然流畅的文本,这一特性使其在多个领域都有广泛的应用潜力,特别是在智能对话和智能…...

git tag
已经发布了 v1.0 v2.0 v3.0 三个版本,这个时候,我突然想不改现有代码的前提下,在 v2.0 的基础上加个新功能,作为 v4.0 发布。就可以检出 v2.0 的代码作为一个 branch ,然后作为开发分支。 要查看仓库中的所有标签 gi…...