数据结构【二叉树】

前言

我们在前面学习了使用数组来实现二叉树，但是数组实现二叉树仅适用于完全二叉树（非完全二叉树会有空间浪费），所以我们本章讲解的是链式二叉树，但由于学习二叉树的操作需要有一颗树，才能学习相关的基本操作，由于这只是开头，为了降低学习的成本，所以我们手动的来创建一颗普通的二叉树，等到本文的后面，再讲解真正的创建

二叉树的基本结构
typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
}BTNode;

创建新结点
BTNode*BuyNode(BTDataType x)
{
	BTNode* Node = (BTNode*)malloc(sizeof(BTNode));
	if (Node == NULL)
	{
		perror("malloc fail:");
		exit(1);
	}
	Node->_data = x;
	Node->_left = Node->_right = NULL;
}

创造树
BTNode* CreateBinaryTree()
{
	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);
	BTNode* node8 = BuyNode(8);

	node1->_left = node2;
	node2->_left = node3;
	node3->_right = node4;
	node1->_right = node5;
	node5->_right = node6;
	node6->_left = node7;
	node6->_right = node8;

	return node1;
}

int main()
{
	BTNode* root = CreateBinaryTree();
	return 0;
}

最后效果如图
在这里插入图片描述

在完成二叉树的基本操作之前，我们先在这里简单的回顾一下二叉树的基本概念。
二叉树只有两个状态

  1. 空树
  2. 非空：由根结点，根节点的左子树，根结点的右子树组成在这里插入图片描述

从图中可以看出，二叉树定义是递归形式的（根结点的左孩子也能看作根，其左右孩子以及对于的联系也能看成左右子树，根的右孩子同理），所以我们下面的操作都是通过递归来实现。

以下所有的操作都会使用上面手搓的树

二叉树的遍历

所谓前中后序的遍历就是根结点的先后访问顺序，所以前中后序遍历也叫前根、中根、后根遍历。

  1. 前序（前根）的访问顺序：根、左子树、右子树
  2. 中序（中根）的访问顺序：左子树、根、右子树
  3. 后序（后根）的访问顺序：左子树、右子树、根

这里先将遍历的原因是后续的操作，都会用到遍历的思路。
要被遍历的树

前序遍历

一般说这个树的前序遍历是[1, 2, 3, 4, 5, 6, 7, 8]
但这不是最详细的表达，最详细的表达是[1, 2, 3, NULL, 4, NULL, NULL, NULL, 5, NULL, 6, 7, NULL, NULL, 8, NULL, NULL]。

3 后面的NULL其实是 3 的左孩子，4 后面俩个NULL代表的是 4 的左孩子和右孩子，而 5 前面的NULL代表的是 2 的右孩子，5 后面的NULL代表 5 的左孩子，7 和 8 后面的NULL都是代表他们的左右孩子。

中序

一般说这个树的中序遍历是[3, 4, 2, 1, 5, 7, 6, 8 ];
实际则是[N, 3, N, 4, N, 2, N, 1, N, 5, N, 7, N, 6, N, 8, N]（N代替NULL）
由于是先访问左子树，所以第一个真正被遍历的一定是NULL。

3 前面的N就是 3 的左孩子，4 前后的 N则代表的是 4 的左右孩子，2 后面的N代表的是 2 的右孩子；5 前面的N代表 5 的左孩子，7 和 8 前后的N都代表他们的左右孩子。

后序

一般：[4, 3, 2, 7, 8, 6, 5, 1]
实际则是[N, N, N, 4, 3, N, 2, N, N, N, 7, N, N, 8, 6, 5, 1]（N代替NULL）

第一个N是 3 的左孩子，第二第三个N是 4 的左右孩子，3 后面的N是 2 的右孩子；而 2 后面的第一个N是 5 的左孩子，7 和 8 的前俩个N都是代表他们的左右孩子

注意：无论是哪种遍历，孩子之间的顺序一定是先左孩子，再是右孩子。

层序遍历

就是我们正常的思维，一层一层、从左到右的依次遍历，这种遍历方式叫广度优先遍历（BFS），而前三种遍历方式叫深度优先遍历（DFS）。

层序遍历需要依靠队列来实现。

代码实现

前中后序的遍历的大体相同，只是打印的位置不同

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	前序时printf的位置在前面
	printf("%d ", root->_data);
	
	BinaryTreePrevOrder(root->_left);
	
	中序时printf的位置在中间
	printf("%d ", root->_data);
	
	BinaryTreePrevOrder(root->_right);
	
	后续时printf的位置在末尾
	printf("%d ", root->_data)；
}

用图像讲解递归过程

在这里插入图片描述

右子树的递归过程大体相同，注意实际情况并不会开那么多的空间，而是当你使用完返回再使用的时候，是将原来的空间给重新利用了。

层序遍历的实现

在完成层序遍历之前，我们需要有队列这个数据结构（我们可以直接将以前的代码拿过来：具体代码在数据结构【队列】）

具体思路是，先创建一个队列，将二叉树的根结点存放到队列里，每遍历一个结点就删掉这个在队列里的结点，删掉的同时，将该结点的左右孩子存放到队列内部这样依次往复。

这里的类型是结点的类型，并且存放的是指针，所以要带个*号
typedef struct BinaryTreeNode* QUEUEDATA;

typedef struct QNode
{
	QUEUEDATA _val;
	struct QNode* _next;
}QNode;

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;

层序遍历代码

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	Queue* q = (Queue*)malloc(sizeof(Queue));
	QueueInit(q);

	//先把root入到队列
	QueuePush(q, root);
	//当队列尾空时，就代表以及打印完了
	while (!QueueEmpty(q))
	{
		//取队头数据
		BTNode*tmp = QueueFirst(q);

		//然后删除数据，我只是操作队列内部，并没有动原来的二叉树
		QueuePop(q);
		
		//当为空时不加数据，这就能应对根结点是空时的情况，就不需要在外面再做一次判断
		if (tmp == NULL)
		{
			printf("N ");
		}
		//非空，将左右孩子添加到队列
		else
		{
			printf("%d ", tmp->_data);
			QueuePush(q,tmp->_left);
			QueuePush(q,tmp->_right);
		}
	}
}

二叉树的计算

本文计算关于树的计算有四个

  1. 计算树结点的个数
  2. 计算树的叶子结点个数
  3. 计算第k层的节点个数
  4. 计算树的高度

计算节点个数

这就很简单了，就是左右子树加自己，但每个孩子又可以分为根，左子树，右子树，当根等于空时返回0就可以了。

// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
}

这里的+1就是加自己，当你来到下面那个return时，就代表该节点并不是空节点。

计算叶子节点个数

简单的回顾一下：叶子节点就是左右孩子都为空的节点。
所以就可以判断当左右孩子都为空时，就返回 1。

// 二叉树叶子节点个数
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);
}

计算第k层节点个数

这个也能很好的用递归来解决，第k层是对于根节点来说的，但对于根节点的下一层来说，第k层其实是第k-1层，所以可以一直减下去，直到当k==1时，return 1。

// 二叉树第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);
}

计算树的高度

那我就比较左子树和右子树的高度，比较出结果后再加自身的高度（比较出的高度+1）
结束递归的条件就是当我的子树为空，返回0。

// 二叉树的高度
int BinaryHeight(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return 	BinaryHight(root->_left) > BinaryHight(root->_right) ? 
	BinaryHight(root->_left) + 1: BinaryHight(root->_right) + 1;
}

这样也可以，但是如果用这个去做利扣的题是无法通过的，并不是因为程序结果错误，而是因为栈溢出。
看看为什么会栈溢出：我要比较出两个子树的长度，就一定会运行
return BinaryHight(root->_left) > BinaryHight(root->_right) ? BinaryHight(root->_left) + 1: BinaryHight(root->_right) + 1; 这有没有发现，我并没有记录比较高的值，我辛辛苦苦递归很多次才得到的左右子树中较高的子树，当我要返回高度的时候，诶？我前面的数是啥？所以我就又要进行 BinaryHight(root->_left) + 1或者BinaryHight(root->_right) + 1，这样我又会进行递归，再递归比较，然后再递归返回值->递归比较这样一直下去，直到最低层（root == NULL）。

所以，我们需要变量来记录两颗子树的高度，这样我们再比较的时候就不会重复递归了。


// 二叉树的高度
int BinaryHeight(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	//记录左树的高度
	int L = BinaryHight(root->_left);
	//记录右树的高度
	int R = BinaryHight(root->_right);
	//比较出较高的，加上自己这一层的高度
	return (L > R ? L : R) + 1;
}

二叉树的创建和销毁

二叉树的创建（前序）

这题是使用前序来创建二叉树

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);

'#'号代表空，a是数组，n是长度，pi是下标
先创建父亲节点，然后左子树 -> 创建左子树当中的父亲节点，然后创建左子树 —>直到这时的数据是'#'返回NULL，创建右子树，右子树创建完，函数自然结束，回到上一层让上一层来创建右子树。
当pi等于n的时候，就代表已经遍历完该数组了，这条数组里的数据已经被我创建成一个二叉树了；这时候就返回NULL；这个判断放在函数的开头。

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
//当下标与长度相等，返回NULL
	if (*pi == n)
	{
		return NULL;
	}
	if (a[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}
	BTNode* root = (BTNode*)malloc(sizeof(BTNode));//先创建根节点，再创建左子树，再创建右子树
	root->_data = a[(*pi)++];
	root->_left = BinaryTreeCreate(a, n, pi);//先创建左子树
	root->_right = BinaryTreeCreate(a, n, pi);//再创建右子树
	return root;//返回根节点
}

二叉树的销毁（后序）

这题我们采用后序来删除，是因为后续并不需要记录节点，是从底层一点一点销毁节点，当我左右子树的节点都销毁了（或者都为NULL），才销毁我的根节点。

// 二叉树销毁
void BinaryTreeDestory(BTNode** root)

既然是销毁，那么就会修改原来的值，所以我们就传二叉树根节点的地址。

// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{
	if (root == NULL || *root == NULL)
	{
		return;
	}
	BinaryTreeDestory(&(*root)->_left);//先销毁左子树
	BinaryTreeDestory(&(*root)->_right);//再销毁右子树
	
	//当左右节点都被销毁或者都为NULL
	free(*root);//最后再销毁根节点
}

结语

到这里二叉树的基本函数就讲完啦。

最后感谢您能阅读完此片文章，如果有任何建议或纠正欢迎在评论区留言，也可以前往我的主页看更多好文哦(点击此处跳转到主页)。
如果您认为这篇文章对您有所收获，点一个小小的赞就是我创作的巨大动力，谢谢！！！

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

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

相关文章

2024.6.23周报

2024.6.23周报

目录 摘要 ABSTRACT 一、文献阅读 一、题目 二、摘要 三、网络架构 四、创新点 五、文章解读 1、Introduction 2、Method 3、实验 4、结论 二、代码实验 总结 摘要 本周阅读了一篇题目为NAS-PINN: NEURAL ARCHITECTURE SEARCH-GUIDED PHYSICS-INFORMED NEURAL N…
阅读更多...
生成式AI和LLM的一些基本概念和名词解释

生成式AI和LLM的一些基本概念和名词解释

1. Machine Learning 机器学习是人工智能（AI）的一个分支，旨在通过算法和统计模型，使计算机系统能够从数据中学习并自动改进。机器学习算法使用数据来构建模型，该模型可用于预测或决策。机器学习应用于各种领域&#x…
阅读更多...
Windows环境下使用VisualGDB进行Linux项目开发

Windows环境下使用VisualGDB进行Linux项目开发

1.新建项目-打开文件下的新建项目菜单 2.工程项目类型配置 3.Linux机器选择设置 4.设置代码位置 5.编译选项设置 6.调试环境设置
阅读更多...
(Python)可变类型不可变类型；引用传递值传递；浅拷贝深拷贝

(Python)可变类型不可变类型；引用传递值传递；浅拷贝深拷贝

从一段代码开始说事，先上代码： a [[1],[2],[3]] b [[4,5],[6,7],[7,8]] for i,j in zip(a,b):print(i,j)i [9]#i[0] 8j[:2][1,2]print(i, j) print(a) print(b) 运行的结果： [1] [4, 5] [9] [1, 2] [2] [6, 7] [9] [1, 2] [3] [7, 8] …
阅读更多...
后仿真中 module path polarity 问题

后仿真中 module path polarity 问题

目录 一 未知极性 二 正极性 三 负极性 不知道大家有没有遇到这个问题：什么？我们知道的module path delay 指的是定义在specify...endspecify block 中的语句，指示输入-输出的延迟信息。 这里的module path 竟然还有极性问题，今天，来学习一下。 模块路径的极性是一…
阅读更多...
使用dify.ai做一个婚姻法助手

使用dify.ai做一个婚姻法助手

步骤 1：注册并登录 Dify.ai 访问 Dify.ai 官网，注册一个账号并登录。 步骤 2：创建新项目 登录后，点击“创建新项目”。为项目命名，例如“婚姻法助手”。 步骤 3：导入婚姻法文本到知识库 在项目中&…
阅读更多...
如何使用idea连接Oracle数据库？

如何使用idea连接Oracle数据库？

idea版本：2021.3.3 Oracle版本：10.2.0.1.0（在虚拟机Windows sever 2003 远程连接数据库） 数据库管理系统：PLSQL Developer 在idea里面找到database，在idea侧面 选择左上角加号，新建&#xff…
阅读更多...
定义和反射Annotation类（注解）

定义和反射Annotation类（注解）

文章目录 前言一、定义Annotation类二、反射Anootation类 1.元注解2.反射注解总结 前言 在写代码的过程中，我们经常会写到注释，以此来提醒代码中的点。但是，这些注释不会被查看，也不在整个代码之中，只能在源代码中进行…
阅读更多...
vue 基于antV 实现流程图编辑器代码

vue 基于antV 实现流程图编辑器代码

最近在做流程图功能开发&#xff0c;发现阿里antV 有对应的可视化引擎&#xff0c;于是自己做了一个简单vue 基于antV 实现流程图编辑器代码 部分代码如下&#xff1a; <template><div id"flowEditorContent"><header><h3>antv X6 流程编辑…
阅读更多...
Java热部署：让应用更新如丝般顺滑，告别繁琐重启！

Java热部署：让应用更新如丝般顺滑，告别繁琐重启！

目录 手动启动热部署 自动启动热部署 参与热部署监控的文件范围配置 关闭热部署 什么是热部署&#xff1f;简单说就是你程序改了&#xff0c;现在要重新启动服务器&#xff0c;嫌麻烦&#xff1f;不用重启&#xff0c;服务器会自己悄悄的把更新后的程序给重新加载一遍&…
阅读更多...
发那科机器人IO 分配

发那科机器人IO 分配

IO 信号 也称为输入\输出信号&#xff0c;是机器人与外围设备通信的电信号
阅读更多...
Studying-代码随想录训练营day16| 513找到左下角的值、112.路径总和、106从中序与后序遍历序列构造二叉树

Studying-代码随想录训练营day16| 513找到左下角的值、112.路径总和、106从中序与后序遍历序列构造二叉树

第十六天&#xff0c;二叉树part03&#x1f4aa;&#x1f4aa;&#x1f4aa;&#xff0c;编程语言&#xff1a;C 目录 513找到左下角的值 112.路径总和 113.路径总和II 106从中序与后序遍历序列构造二叉树 105.从前序与中序遍历序列构造二叉树 总结 513找到左下角的值…
阅读更多...
Elk安装及使用

Elk安装及使用

es安装及使用 单机版安装 集群安装 132 node-01 133 node-02 135 node-03 日志用户权限有问题 看日志 解决方案&#xff1a; 出现错误后&#xff0c;再次重启前&#xff0c;需要删除三个节点/data/下的内容 9300-http 9300-tcp logstasha安装及使用 Ssh错误 Yum安装默认路…
阅读更多...
职场记 | 有些人的成功真的不是偶然

职场记 | 有些人的成功真的不是偶然

今天跟大家聊一聊雷总的成长记&#xff0c;希望给职场中的朋友们一点启发&#xff1a; 强烈的创业精神与持续的创新意识 雷军自大学时期起就展现出了强烈的创业热情。他不仅在求学期间积极参与创业活动&#xff0c;更在毕业后迅速踏上创业道路&#xff0c;创立了多家知名企业…
阅读更多...
大模型时代，新手和程序员如何转型入局AI行业？

大模型时代，新手和程序员如何转型入局AI行业？

在近期的全国两会上&#xff0c;“人工智能”再次被提及&#xff0c;并成为国家战略的焦点。这一举措预示着在接下来的十年到十五年里&#xff0c;人工智能将获得巨大的发展红利。技术革命正在从“互联网”向“人工智能”逐步迈进&#xff0c;我将迎来新一轮技术革新和人才需求…
阅读更多...
NetSuite 不同类型Item的公司间交易科目的设置

NetSuite 不同类型Item的公司间交易科目的设置

我们知道&#xff0c;NetSuite中有Intercompany Preferences的设置&#xff0c;如下所示&#xff0c;分别涉及到公司间应收、公司间应付、公司间收入、公司间费用以及公司间成本共5个科目&#xff0c;非常明确清晰。 最近用户遇到的场景是&#xff0c;如果是Non-Inventory Item…
阅读更多...
史上最全的整合Harbor安装教程，哈哈哈哈

史上最全的整合Harbor安装教程，哈哈哈哈

一、安装docker 下载地址&#xff1a;https://download.docker.com/linux/static/stable/x86_64/docker-23.0.4.tgz 1.1 解压二进制包 wget https://download.docker.com/linux/static/stable/x86_64/docker-23.0.4.tgz tar zxvf docker-23.0.4.tgz mv docker/* /usr/bin1.2…
阅读更多...
【C语言】16.动态内存管理

【C语言】16.动态内存管理

文章目录 1.为什么要有动态内存分配2.malloc和free2.1 malloc2.2 free 3.calloc和realloc3.1 calloc3.2 realloc 4.常见的动态内存的错误4.1 对NULL指针的解引⽤操作4.2 对动态开辟空间的越界访问4.3 对⾮动态开辟内存使⽤free释放4.4 使⽤free释放⼀块动态开辟内存的⼀部分4.5…
阅读更多...
对红酒数据集，分别采用决策树算法和随机森林算法进行分类。

对红酒数据集，分别采用决策树算法和随机森林算法进行分类。

1.导入所需要的包 from sklearn.tree import DecisionTreeClassifier from sklearn.ensemble import RandomForestClassifier from sklearn.datasets import load_wine from sklearn.model_selection import train_test_split 2.导入数据&#xff0c;并且对随机森林和决策数进…
阅读更多...
每月 GitHub 探索｜10 款引领科技趋势的开源项目

每月 GitHub 探索｜10 款引领科技趋势的开源项目

1.IT-Tools 仓库名称&#xff1a; CorentinTh/it-tools 截止发稿星数: 16842 (近一个月新增:5744) 仓库语言: Vue 仓库开源协议&#xff1a; GNU General Public License v3.0 引言 CorentinTh/it-tools 是一个开源项目&#xff0c;提供各种对开发者友好的在线工具&#xff0…
阅读更多...
最新文章

Copyright @ 2022~2023