数据结构与算法——二叉树+带你实现表达式树（附源码）

在这里插入图片描述

📖作者介绍：22级树莓人（计算机专业），热爱编程＜目前在c＋＋阶段，因为最近参加新星计划算法赛道(白佬)，所以加快了脚步，果然急迫感会增加动力>——目标Windows，MySQL，Qt，数据结构与算法，Linux，多线程，会持续分享学习成果和小项目的
📖作者主页：king&南星
📖专栏链接：数据结构

🎉欢迎各位→点赞👏 + 收藏💞 + 留言🔔​
💬总结：希望你看完之后，能对你有所帮助，不足请指正！共同学习交流 🐾

在这里插入图片描述

文章目录

    • 👨‍🎓二叉树
      • 🧑‍🎓一、概念及定义
        • ⛵1、概念
        • ⛵2、性质
      • 👩‍🎓 二、结点的定义、链表应用、空节点的说明
        • ⛵1、结点声明
        • ⛵2、链表的应用
        • ⛵ 3、空结点的说明及画图
      • 🧑‍🏫三、表达式树——遍历
        • ⛵1、表达式树引入与介绍
        • ⛵2、中序遍历
        • ⛵3、后序遍历
        • ⛵4、先序遍历
        • ⛵5、总结
        • ⛵ 6、构建一颗表达式树
          • ⛵A、第一步
          • ⛵B、第二步
          • ⛵C、第三步
          • ⛵D、第四步
          • ⛵E、第五步
          • ⛵F、第六步
      • 🧑‍⚖️四、查找节点
      • 🧑‍🌾五、插入节点
      • 👩‍🔧六、综合代码

👨‍🎓二叉树

🧑‍🎓一、概念及定义

⛵1、概念

二叉树是一棵树，其中每个结点的儿子都不能多于两个

如下图是由一个跟和两个子树组成的二叉树，且子树可能为空

在这里插入图片描述

⛵2、性质

二叉树的一个性质是平均二叉树的深度要比N小得多。分析表明，这个平均深度为O(根号N),而对于特殊的二叉树，即二叉查找树，其深度的平均值为O(logN),不幸的是这个深度是可以大到N-1的，如下图所示

在这里插入图片描述

👩‍🎓 二、结点的定义、链表应用、空节点的说明

⛵1、结点声明

因为一颗二叉树最多有两个儿子，所以我们可以用指针直接指向他们。树节点的声明在结构体是类似于双链表的声明，在声明中，一个节点就是由关键字信息加上两个指向其他节点的指针(Lift和Right)组成的结构

//叶子节点数据
#define EMPTY 6666
//是否要显示EMPTY  为1 不显示EMPTY  为0 显示EMPTY
#define NOTSHOWEMPTY  1
typedef struct Node
{
	int data;
	struct Node* pLift;
	struct Node* pright;
}Node;

⛵2、链表的应用

在进行一次插入时需要调用malloc创建一个节点，节点可以在调用free删除后释放

Node* createNode(int newNodedata) 
{
	Node* newNode = malloc(sizeof(Node));
	if (NULL == newNode) return newNode;
	newNode->data = newNodedata;
	newNode->pLift = newNode->pright = NULL;
	return newNode;
}

⛵ 3、空结点的说明及画图

我们可以用链表的知识用矩形框画出二叉树，但是，树一般画成圆圈并用一些直线连接起来，因为二叉树实际上就是图，当涉及树时，我们也不显示地画出NULL指针，因为具有N个节点的每一颗二叉树都需要N+1个NULL指针，我们在这里描述的二叉树是无序二叉树，叶子节点用EMPTY节点表示

🧑‍🏫三、表达式树——遍历

⛵1、表达式树引入与介绍

下图是一个表达式树，表达式树的树叶是操作数，比如常量或变量，而其他的节点为操作符。由于这里所有的操作都是二元的，因此这颗特定的树正好是二叉树，虽然这是最简单的情况，但是节点含有的儿子还是有可能多于两个的。一个节点也有可能只有一个儿子，如具有一目操作符的情况。可以将通过递归计算左子树和右子树所得到的值应用在根处的算符操作中而算出表达式树T的值。在本例中，左子树的值为a+(b*c)，右子树的值为(((d*e)+f)*g),因此整颗表达式的值为a+(b*c)+(((d*e)+f)*g)

在这里插入图片描述

这里我们先看看我们这里用的数据

在这里插入图片描述

⛵2、中序遍历

我们可以通过递归产生一个带括号的左表达式，然后打印出在根处的运算符，然后再递归地产生一个带括号的右表达式而得到一个(对两个括号整体进行运算的)中缀表达式。这种一般的方法(左，根，右)被称为中序遍历

代码如下

void _midTravel(Node* root) 
{
	if (NULL == root) return;
	_midTravel(root->pLift);
#if NOTSHOWEMPTY
	if (root->data != EMPTY)
#endif
		printf("%d ", root->data);
	_midTravel(root->pright);
}

⛵3、后序遍历

就是递归打印出左子树，右子树，然后打印根节点，也就是后缀表达式，这种遍历一般称为后序遍历

代码如下

void _lstTravel(Node* root) 
{
	if (NULL == root) return;
	_lstTravel(root->pLift);
	_lstTravel(root->pright);
#if NOTSHOWEMPTY
	if (root->data != EMPTY)
#endif
		printf("%d ", root->data);
}

⛵4、先序遍历

先序遍历就是先打印出根节点，然后递归的打印出右子树和左子树，是一种前序记法

代码如下

void _preTravel(Node* root) 
{
	if (NULL == root) return;
#if NOTSHOWEMPTY
	if (root->data != EMPTY)
#endif
		printf("%d ", root->data);
	_preTravel(root->pLift);
	_preTravel(root->pright);
}

⛵5、总结

已知中序 和 先序 可以推导出树 知道后序
已知中序 和 后序 可以推导出树 知道先序
已知先序和后序，不能推导出树

这是因为只要知道先序和后序一个就可以知道根节点了，知道了中序就可以推导出左右子树了

⛵ 6、构建一颗表达式树

我们现在给出一种算法来把后缀表达式转换为表达式树。这种方法酷似后缀求值算法。一次一个符号地读入表达式，如果符号是操作数，那么我们就建立一个单节点树并将一个指向它的指针推入栈中。如果符号是操作符，那么我们就从栈中弹出指向两棵树T1和T2的两个指针(T1的先弹出）并形成一颗新的树，该树的根就是操作符，它的左右儿子分别指向T2和T1。然后将指向这棵树的指针压入栈中

来看一个例子，设输入为：ab+cde+**

⛵A、第一步

前两个符号是操作数，因此我们创建两颗单节点树并将指向它们的指针压入栈中

在这里插入图片描述

⛵B、第二步

接着，读入“+”,因此弹出指向这两颗树的指针，一棵新的树新成，而将指向该树的指针压入栈中

在这里插入图片描述

⛵C、第三步

然后，读入c、d、e，在每棵单节点树创建后，将指向对应的树的指针压入栈中

在这里插入图片描述

⛵D、第四步

接下来读入“+”,因此两棵树合并

在这里插入图片描述

⛵E、第五步

继续进行，读入“”,因此，弹出两个树指针并形成一颗新的树，“”是它的根
在这里插入图片描述

⛵F、第六步

最后，读入最后一个符号，两棵树合并，而指向最后的树的指针留在栈中

在这里插入图片描述

🧑‍⚖️四、查找节点

Node* findNode(Node* root, int findData) 
{
	if (NULL == root) return NULL;
	if (findData = EMPTY) return NULL;
	if (root->data == findData) return root;
	Node* pTemp = findNode(root->pLift, findData);
	if (pTemp) return pTemp;
	return findNode(root->pright, findData);
}

🧑‍🌾五、插入节点

这里就体现了递推的大用处了，还有就是要传二级指针，因为要修改根节点

//插入(先序遍历）
bool inserData(Node** root, int insertdata)
{
	if (NULL == root) return false;
	//插入根节点
	if( NULL == *root )
	{
		*root = createNode(insertdata);
		return true;
	}
	if ((*root)->data == EMPTY) return false;
	if (true == inserData(&((*root)->pLift), insertdata))
		return true;
	else
		return inserData(&((*root)->pright), insertdata);
}

👩‍🔧六、综合代码

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<stdbool.h>
//叶子节点数据
#define EMPTY 6666
//是否要显示EMPTY  为1 不显示EMPTY  为0 显示EMPTY
#define NOTSHOWEMPTY  1
typedef struct Node
{
	int data;
	struct Node* pLift;
	struct Node* pright;
}Node;
//创建节点函数
Node* createNode(int newNodedata);
//PRE：先序遍历,MID：中序遍历,LST：后序遍历
enum travelType { PRE, MID, LST };
//遍历
void Travel(Node* root, enum travelType type);
//先序遍历
void _preTravel(Node* root);
//中序遍历
void _midTravel(Node* root);
//后序遍历
void _lstTravel(Node* root);
//插入(先序遍历）
bool inserData(Node** root, int insertdata);
//找到数据为findData的第一个节点 找到返回节点地址 否则返回NULL
Node* findNode(Node* root, int findData);
int main() 
{
	//一颗空树
	Node* pRoot = NULL;

	int arr[] = { 10, 99, 83, EMPTY, 22, EMPTY, EMPTY, EMPTY ,96,
		EMPTY, 56, 6, EMPTY, EMPTY, 11, 36, EMPTY, EMPTY, EMPTY,666 };


	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
		inserData(&pRoot, arr[i]);

	Travel(pRoot, PRE);
	Travel(pRoot, MID);
	Travel(pRoot, LST);

	return 0;
}
//创建节点函数
Node* createNode(int newNodedata) 
{
	Node* newNode = malloc(sizeof(Node));
	if (NULL == newNode) return newNode;
	newNode->data = newNodedata;
	newNode->pLift = newNode->pright = NULL;
	return newNode;
}
//遍历
void Travel(Node* root, enum travelType type) 
{
	switch (type)
	{
	case PRE:
		printf("先序遍历：");
		_preTravel(root);
		printf("\n");
		break;
	case MID:
		printf("中序遍历：");
		_midTravel(root);
		printf("\n");
		break;
	case LST:
		printf("后序遍历: ");
		_lstTravel(root);
		printf("\n");
		break;
	}
}
//先序遍历
void _preTravel(Node* root) 
{
	if (NULL == root) return;
#if NOTSHOWEMPTY
	if (root->data != EMPTY)
#endif
		printf("%d ", root->data);
	_preTravel(root->pLift);
	_preTravel(root->pright);
}
//中序遍历
void _midTravel(Node* root) 
{
	if (NULL == root) return;
	_midTravel(root->pLift);
#if NOTSHOWEMPTY
	if (root->data != EMPTY)
#endif
		printf("%d ", root->data);
	_midTravel(root->pright);
}
//后序遍历
void _lstTravel(Node* root) 
{
	if (NULL == root) return;
	_lstTravel(root->pLift);
	_lstTravel(root->pright);
#if NOTSHOWEMPTY
	if (root->data != EMPTY)
#endif
		printf("%d ", root->data);
}
//插入(先序遍历）
bool inserData(Node** root, int insertdata)
{
	if (NULL == root) return false;
	//插入根节点
	if( NULL == *root )
	{
		*root = createNode(insertdata);
		return true;
	}
	if ((*root)->data == EMPTY) return false;
	if (true == inserData(&((*root)->pLift), insertdata))
		return true;
	else
		return inserData(&((*root)->pright), insertdata);
}
//找到数据为findData的第一个节点 找到返回节点地址 否则返回NULL
Node* findNode(Node* root, int findData) 
{
	if (NULL == root) return NULL;
	if (findData = EMPTY) return NULL;
	if (root->data == findData) return root;
	Node* pTemp = findNode(root->pLift, findData);
	if (pTemp) return pTemp;
	return findNode(root->pright, findData);
}

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

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

相关文章

ThreadLocal详解

ThreadLocal详解

一、什么是ThreadLocal 1、什么是ThreadLocal&为什么用ThreadLocal ThreadLocal&#xff0c;即线程本地变量&#xff0c;在类定义中的注释如此写This class provides thread-local variables。如果创建了一个ThreadLocal变量&#xff0c;那么访问这个变量的每个线程都会有…
阅读更多...
C++基础算法④——排序算法(插入、桶附完整代码)

C++基础算法④——排序算法(插入、桶附完整代码)

排序算法 1.插入排序 2.桶排序 1.插入排序 基本思想&#xff1a;将初始数据分为有序部分和无序部分&#xff1b;每一步将无序部分的第一个值插入到前面已经排好序的有序部分中&#xff0c;直到插完所有元素为止。步骤如下&#xff1a; 每次从无序部分中取出第一个值&#x…
阅读更多...
图像分类卷积神经网络模型综述

图像分类卷积神经网络模型综述

图像分类卷积神经网络模型综述遇到问题 图像分类&#xff1a;核心任务是从给定的分类集合中给图像分配一个标签任务。 输入&#xff1a;图片 输出&#xff1a;类别。 数据集MNIST数据集 MNIST数据集是用来识别手写数字&#xff0c;由0~9共10类别组成。 从MNIST数据集的SD-1和…
阅读更多...
在Clion开发工具上使用NDK编译可以在安卓上执行的程序

在Clion开发工具上使用NDK编译可以在安卓上执行的程序

1. 前言 因为工作需要&#xff0c;我要将一份C语言代码编译成可执行文件传送到某安卓系统里执行。 众所周知&#xff0c;使用ndk编译代码有三种使用方式&#xff0c;分别是基于 Make 的 ndk-build、CMake以及独立工具链。以前进行ndk编程都是使用ndk-build进行的&#xff0c;新…
阅读更多...
RocketMQ的基本概念、系统架构、单机安装与启动

RocketMQ的基本概念、系统架构、单机安装与启动

RocketMQ的基本概念、系统架构、单机安装与启动 文章目录RocketMQ的基本概念、系统架构、单机安装与启动一、基本概念1、消息&#xff08;Message&#xff09;2、主题&#xff08;Topic&#xff09;3、标签&#xff08;Tag&#xff09;4、队列&#xff08;Queue&#xff09;5、…
阅读更多...
C# 教你如何终止Task线程

C# 教你如何终止Task线程

我们在多线程中通常使用一个bool IsExit类似的代码来控制是否线程的运行与终止&#xff0c;其实使用CancellationTokenSource来进行控制更为好用&#xff0c;下面我们将介绍CancellationTokenSource相关用法。C# 使用 CancellationTokenSource 终止线程使用CancellationTokenSo…
阅读更多...
【Leetcode】-有效的括号

【Leetcode】-有效的括号

作者&#xff1a;小树苗渴望变成参天大树 作者宣言&#xff1a;认真写好每一篇博客 作者gitee:gitee 如 果 你 喜 欢 作 者 的 文 章 &#xff0c;就 给 作 者 点 点 关 注 吧&#xff01; 文章目录前言前言 今天我们再来讲一期关于题目的博客&#xff0c;我挑选的是一道leet…
阅读更多...
Git学习与gitlab中央仓库搭建（详细介绍）

Git学习与gitlab中央仓库搭建（详细介绍）

环境&#xff1a;centos7.3一&#xff0c;Git的发展史git&#xff1a;分布式版本控制系统&#xff0c;是当前最流行的版本控制软件创始人&#xff1a;林纳斯.拖瓦兹二&#xff0c;部署Git环境1.安装git服务[rootlocalhost ~]# yum -y install git2.配置git环境不一定是data目录…
阅读更多...
【C++】初识模板

【C++】初识模板

放在专栏【C知识总结】&#xff0c;会持续更新&#xff0c;期待支持&#x1f339;前言在谈及本章之前&#xff0c;我们先来聊一聊别的。橡皮泥大家小时候应该都玩过吧&#xff0c;通常我们买来的橡皮泥里面都会带有一些小动物的图案的模子。我们把橡皮泥往上面按压&#xff0c;…
阅读更多...
【性能分析】分析JVM出现的内存泄漏的性能故障

【性能分析】分析JVM出现的内存泄漏的性能故障

分析JVM出现的内存持续增加的性能故障手册 前言 本文通过常见的性能文件为例&#xff0c;提供简单清晰的思路去快速定位问题根源&#xff0c;从而可以快速解决性能故障。 性能问题介绍 在性能测试工作中针对Java程序最重要的是要关注JVM的内存消耗情况&#xff0c;JVM的内存…
阅读更多...
面试错题本

面试错题本

目录2023.3.21 深信服哈夫曼树哈夫曼编码2023.3.21 深信服 ​同一线程共享的有堆、全局变量、静态变量、指针&#xff0c;引用、文件等&#xff0c;而独自占有栈 友元函数不能被继承&#xff0c;友元函数不是成员函数 友元函数不能被继承&#xff0c;友元函数不是当前类的成员…
阅读更多...
Vue2项目总结-电商后台管理系统

Vue2项目总结-电商后台管理系统

Vue2项目总结-电商后台管理系统 去年做的项目&#xff0c;拖了很久&#xff0c;总算是打起精力去做这个项目的总结&#xff0c;并对Vue2的相关知识进行回顾与复习 各个功能模块如果有过多重复冗杂的部分&#xff0c;将会抽取部分值得记录复习的地方进行记录 一&#xff1a;项目…
阅读更多...
精心整理前端主流框架学习路径

精心整理前端主流框架学习路径

版权声明 本文原创作者&#xff1a;谷哥的小弟作者博客地址&#xff1a;http://blog.csdn.net/lfdfhl 前端主流框架 前端框架指的是用于构建Web前端应用程序的框架&#xff0c;使用框架进行前端开发带来以下显著优势&#xff1a; 提高开发效率&#xff1a;前端框架提供了现成的…
阅读更多...
STM32的CAN总线调试经验分享

STM32的CAN总线调试经验分享

相关文章 CAN总线简易入门教程 CAN总线显性电平和隐性电平详解 STM32的CAN总线调试经验分享 文章目录相关文章背景CAN总线CAN控制器CAN收发器调试过程硬件排查CAN分析仪芯片CAN控制器调试总结背景 最近负责的一个项目用的主控芯片是STM32F407IGT6&#xff0c;需要和几个电机控…
阅读更多...
DWF文件怎么用CAD打开？DWF输入CAD步骤

DWF文件怎么用CAD打开？DWF输入CAD步骤

DWF是一种开放、安全的文件格式&#xff0c;它可以将丰富的设计数据高效率地分发给需要查看、评审或打印这些数据的任何人。那么&#xff0c;DWF文件如何打开呢&#xff1f;下面就和小编一起来了解一下DWF输入浩辰CAD软件中的具体操作步骤吧&#xff01; DWF输入CAD中步骤&…
阅读更多...
安装CentOS系统

安装CentOS系统

打开 Oracle VM VirtualBox 点击新建 输入名称 点击下一步 点击下一步 点击创建 点击下一步 点击下一步 分配30G硬盘 点击创建 创建成功 点击启动按钮 选择 CentOS 系统 iso 镜像文件 点击启动 按键盘方向键 “上键”&#xff0c;选择第一项 按键盘回车键&#xff0c;然后等待 …
阅读更多...
QT搭建MQTT开发环境

QT搭建MQTT开发环境

QT搭建MQTT开发环境 第一步、明确安装的QT版本 注意&#xff1a; 从QT5.15.0版本开始&#xff0c;官方不再提供离线版安装包&#xff0c;除非你充钱买商业版。 而在这里我使用的QT版本为5.15.2&#xff0c;在线安装了好久才弄好&#xff0c;还是建议使用离线安装的版本 在这里…
阅读更多...
代码随想录复习——单调栈篇 每日温度 下一个更大元素12 接雨水 柱状图中最大的矩形

代码随想录复习——单调栈篇 每日温度 下一个更大元素12 接雨水 柱状图中最大的矩形

739.每日温度 每日温度 暴力解法双指针 def dailyTemperatures(self, temperatures: List[int]) -> List[int]:n len(temperatures)res [0] * nfor i in range(n):for j in range(i,n):if temperatures[j] < temperatures[i]: continueelse: res[i] j-ibreakreturn …
阅读更多...
pytorch 计算混淆矩阵

pytorch 计算混淆矩阵

混淆矩阵是评估模型结果的一种指标 用来判断分类模型的好坏 预测对了 为对角线 还可以通过矩阵的上下角发现哪些容易出错 从这个 矩阵出发 可以得到 acc &#xff01; precision recall 特异度&#xff1f; 目标检测01笔记AP mAP recall precision是什么 查全率是什么 查准率…
阅读更多...
【K8S系列】深入解析Pod对象(一)

【K8S系列】深入解析Pod对象(一)

目录 序言 1.问题引入 1.1 问题描述 2 问题解答 2.1 pod 属性 2.1.1 NodeSelector 2.1.2 HostAliases 2.1.3 shareProcessNamespace 2.1.4 NodeName 2.1.5 其他pod属性 2.2 容器属性 2.2.1 ImagePullPolicy 2.2.2 Lifecycle 3 总结 4. 投票 序言 任何一件事情&am…
阅读更多...
最新文章

Copyright @ 2022~2023