二叉树链式结构的实现(二叉树的遍历以及各种常用功能函数的实现)

之前也是把堆部分的知识点梳理完毕(即二叉树链式顺序的实现):堆的应用:堆排序和TOP-K问题

那么讲完了二叉树链式结构的实现。今天就进入二叉树链式结构的实现:


文章目录

  • 1.准备工作
  • 2.二叉树的遍历
    • 2.1前序遍历
    • 2.2中序遍历
    • 2.3后序遍历
    • 2.4层序遍历
  • 3.节点个数以及高度等
    • 3.1二叉树节点个数
    • 3.2二叉树叶子节点(度为1的节点)个数
    • 3.3树的高度
    • 3.4二叉树第k层节点个数
    • 3.5二叉树查找值为x的节点
  • 4.二叉树的构建及销毁
    • 4.1通过前序遍历的数组构建二叉树
  • 4.2二叉树的销毁
  • 5.判断二叉树是否是完全二叉树


1.准备工作

我们先手动快速创建一棵简单的二叉树来先进入二叉树操作,等对二叉树递归和结构有了一定的熟练后我们反过头再来看二叉树真正的创建方式

这不是真正的创建方法,是自己手动构建

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<math.h>

typedef int BTDataType;
typedef struct BinaryTreeNode//节点
{
	BTDataType data;//数据
	struct BinaryTreeNode* left;//左孩子
	struct BinaryTreeNode* right;//右孩子
}TreeNode;

TreeNode* BuyTreeNode(int x)//创建数据为x的节点
{
	TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
	assert(node);

	node->data = x;
	node->left = NULL;
	node->right = NULL;

	return node;
}

TreeNode* CreateTree()//形成树(手动连接)
{
	TreeNode* node1 = BuyTreeNode(1);
	TreeNode* node2 = BuyTreeNode(2);
	TreeNode* node3 = BuyTreeNode(3);
	TreeNode* node4 = BuyTreeNode(4);
	TreeNode* node5 = BuyTreeNode(5);
	TreeNode* node6 = BuyTreeNode(6);//创建六个节点

	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;//进行连接

	return node1;
}

构建的二叉树如图:

请添加图片描述

2.二叉树的遍历

递归实现的关键在于将问题分解为规模更小的子问题,然后通过函数的递归调用来解决子问题。在二叉树遍历中,递归的思想可以很自然地应用,因为遍历左子树和右子树本质上就是对规模更小的子树进行遍历

二叉树遍历(Traversal)是指按照一定规则,依次访问二叉树中的所有节点,每个节点只被访问一次

二叉树的遍历有:前序/中序/后序的递归结构遍历和层序遍历

  1. 前序遍历(Preorder Traversal):先访问根节点,再访问左子树,最后访问右子树(根>左>右)
  2. 中序遍历(Inorder Traversal):先访问左子树,再访问根节点,最后访问右子树(左>根>右)
  3. 后序遍历(Postorder Traversal):先访问左子树,再访问右子树,最后访问根节点(左>右>根)
  4. 层序遍历是一种按层级顺序逐层遍历树结构的方法。它从树的根节点开始,逐层向下遍历,按照从左到右的顺序访问每一层的节点

2.1前序遍历

先访问根节点,再访问左子树,最后访问右子树(根>左>右);每进入一个新节点(先访问自身)

按照此规则之前构建的二叉树访问结果:1 2 3 NULL NULL NULL 4 5 NULL NULL 6 NULL NULL

方便大家理解,我就把NULL也写上:

请添加图片描述

void PreTraversal(TreeNode* root) 
{
	if (root == NULL) 
	{
		printf("NULL ");//正常是不需要的,这里是为了让大家看到NULL(看的全过程)
		return;
	}
	// 访问根节点
	printf("%d ", root->data);
	// 遍历左子树
	PreTraversal(root->left);
	// 遍历右子树
	PreTraversal(root->right);
}

int main()
{
	TreeNode* root = CreateTree();//创建好树
	PreTraversal(root);
	return 0;
}

结果:
请添加图片描述

2.2中序遍历

先访问左子树,再访问根节点,最后访问右子树(左>根>右);每进入一个新节点(先访问左子树)

按照此规则之前构建的二叉树访问结果:NULL 3 NULL 2 NULL 1 NULL 5 NULL 4 NULL 6 NULL

请添加图片描述

void InTraversal(TreeNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");//正常是不需要的,这里是为了让大家看到NULL(看的全过程)
		return;
	}
	// 遍历左子树
	InTraversal(root->left);
	// 访问根节点
	printf("%d ", root->data);
	// 遍历右子树
	InTraversal(root->right);
}

int main()
{
	TreeNode* root = CreateTree();//创建好树
	InTraversal(root);
	return 0;
}

结果:

请添加图片描述

2.3后序遍历

先访问左子树,再访问右子树,最后访问根节点(左>右>根);每进入一个新节点(先访问右子树)

按照此规则之前构建的二叉树访问结果:NULL NULL 3 NULL 2 NULL NULL 5 NULL NULL6 4 1

请添加图片描述

void PostTraversal(TreeNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");//正常是不需要的,这里是为了让大家看到NULL(看的全过程)
		return;
	}
	// 遍历左子树
	PostTraversal(root->left);
	// 遍历右子树
	PostTraversal(root->right);
	// 访问根节点
	printf("%d ", root->data);
}

int main()
{
	TreeNode* root = CreateTree();//创建好树
	PostTraversal(root);
	return 0;
}

结果:

请添加图片描述

2.4层序遍历

它从树的根节点开始,逐层向下遍历,按照从左到右的顺序访问每一层的节点

在 C 语言中,一般使用队列来实现层序遍历:

  1. 从根节点开始,将根节点入队列

  2. 循环执行以下步骤,直到队列为空:

    • 弹出队列的首节点,并访问该节点
    • 将该节点的左右子节点(如果存在)依次入队列;即弹出节点后把子节点入队列

    队列为空时,循环结束

void LevelOrder(TreeNode* root)
{
	Queue q;//创建队列,队列节点里的data储存root的地址
	QInit(&q);//初始化
	QPush(&q, root);//根进去了
	int LevelSize = 1;//要一层一层输出,来辅助
	while (!QEmpty(&q))
	{
		while (LevelSize--)//LevelSize是几就循环几次,一开始是1,输出一个就换行了,再Push后再次更新,来输出下一行
		{
			TreeNode* first = QFront(&q);//先存下来
			QPop(&q);//再pop掉第一个


			printf("%c ", first->data);
			if (first->left)//有左节点就push进来
			{
				QPush(&q, first->left);
			}
			if (first->right)//有右节点就push进来
			{
				QPush(&q, first->right);
			}
		}
		printf("\n");
		LevelSize = QSize(&q);
	}

	QDestroy(&q);
}

请添加图片描述


3.节点个数以及高度等

3.1二叉树节点个数

同样是递归

  1. 计算二叉树节点个数的问题就是计算左子树节点个数和计算右子树节点个数两个子问题
  2. 对于当前节点,我们需要计算以当前节点为根的子树的节点个数。这个节点本身占据一个节点(后面加一),所以我们将问题拆分为计算左子树节点个数和计算右子树节点个数两个子问题,然后将左右子树节点个数相加,并加上当前根节点,即 TreeSize(root->left) + TreeSize(root->right) + 1
  3. 对于左子树和右子树,我们同样可以按照上述步骤继续拆分分析,直到遇到空节点为止(递归终止条件)
int TreeSize(TreeNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return TreeSize(root->left) + TreeSize(root->right) + 1;
}

int main()
{
	TreeNode* root = CreateTree();//创建好树
	printf("%d\n", TreeSize(root));
	return 0;
}

结果:

请添加图片描述

代码也可以这样写:

int TreeSize(TreeNode* root)
{
	return root == NULL ? 0 : 
		TreeSize(root->left) + TreeSize(root->right) + 1;//利用三目运算符
}

3.2二叉树叶子节点(度为1的节点)个数

  1. 判断当前节点是否为空。如果为空,子树的叶子节点个数为 0,直接返回 0
  2. 节点不为空,我们需要判断当前节点是否为叶子节点。如果当前节点的左右子树均为空,即 root->left == NULL && root->right == NULL,则表示当前节点为叶子节点,返回 1
  3. 不是叶子节点,则需要计算以当前节点为根的子树的叶子节点个数。这个节点本身不是叶子节点,所以我们将问题拆分为计算左子树叶子节点个数和计算右子树叶子节点个数两个子问题,然后将左右子树叶子节点个数相加,即 TreeLeafSize(root->left) + TreeLeafSize(root->right)
  4. 对于左子树和右子树,我们同样可以按照上述步骤继续拆分,直到遇到空节点或叶子节点为止
int TreeLeafSize(TreeNode* root)
{
	if (root == NULL)//是NULL就返回0
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)//是叶子就返回1
	{
		return 1;
	}
	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
	//不是叶子就返回左子树叶子与右子树叶子之和
}

int main()
{
	TreeNode* root = CreateTree();//创建好树
	//printf("%d\n", TreeSize(root));
	printf("%d\n", TreeLeafSize(root));
	return 0;
}

请添加图片描述

3.3树的高度

  1. 如果树为空,返回高度为 0
  2. 如果树不为空,则树的高度等于左子树的高度和右子树的高度中的较大值加 1,即 fmax(TreeHeight(root->left), TreeHeight(root->right)) + 1
  3. 对于左子树和右子树,我们同样可以按照上述步骤继续递归计算
int TreeHeight(TreeNode* root)
{
	if (root == NULL)
		return 0;
	return fmax(TreeHeight(root->left), TreeHeight(root->right)) + 1;
}

int main()
{
	TreeNode* root = CreateTree();//创建好树
	//printf("%d\n", TreeSize(root));
	//printf("%d\n", TreeLeafSize(root));
	printf("%d\n", TreeHeight(root));
	return 0;
}

请添加图片描述

3.4二叉树第k层节点个数

  1. 如果树为空,返回节点数为 0
  2. 如果 k 等于 1,表示计算树的根节点,返回 1
  3. 如果 k 大于 1,则第 k 层节点数等于左子树的第 k-1 层节点数加上右子树的第 k-1 层节点数,即 TreeLevelNodes(root->left, k-1) + TreeLevelNodes(root->right, k-1)
  4. 对于左子树和右子树,我们同样可以按照上述步骤继续递归计算
int TreeLevelKSize(TreeNode* root, int k)
{
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return TreeLevelKSize(root->left, k - 1) + TreeLevelKSize(root->right, k - 1);
}

int main()
{
	TreeNode* root = CreateTree();//创建好树

	printf("%d\n", TreeLevelKSize(root,2));//求个第二层的
	return 0;
}

3.5二叉树查找值为x的节点

  1. 如果为空,那肯定找不到,直接返回NULL(同时也作为递归终止的情况之一)
  2. 先找跟节点,找到了即root->data == x,就返回该节点地址(同时也作为递归终止的情况之一)
  3. 找不到,就递归左节点,再右节点
  4. 都没有return的机会后,最后return NULL

递归停止的两种情况:要么找到了返回地址, 要么没找到返回NULL

  • 当不是NULL时,说明找到了,就一路返回上去,得到结果
  • 是NULL,就说明没找到,就去另外一边继续
TreeNode* TreeFind(TreeNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	// 先看根节点
	if (root->data == x)
	{
		return root;
	}
	// 看左子树
	TreeNode* ret1= TreeFind(root->left, x);//递归停止的两种情况:要么找到了返回地址
                                                 // 要么没找到返回NULL
                                              //当不是NULL时,说明找到了,就一路返回上去,得到结果
	if (ret1 != NULL)
	{
		return ret1;
	}
	// 看右子树
	TreeNode* ret2 = TreeFind(root->right, x);//如上
	if (ret2 != NULL)
	{
		return ret2;
	}
	return NULL;
}

int main()
{
	TreeNode* root = CreateTree();//创建好树
	//printf("%d\n", TreeSize(root));
	//printf("%d\n", TreeLeafSize(root));
	//printf("%d\n", TreeHeight(root));
	//printf("%d\n", TreeLevelKSize(root,2));//求个第二层的
	printf("%p\n", TreeFind(root, 5));
	return 0;
}

请添加图片描述

返回地址,说明找到了


4.二叉树的构建及销毁

4.1通过前序遍历的数组构建二叉树

通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树

先根据这个画出来(#为NULL就不画了):

请添加图片描述

TreeNode* CreateTreeTrue(char* arr, int* pi)
{
	if (arr[*pi] == '#')
	{
		(*pi)++;//调到下一个字符
		return NULL;
	}
	TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
	assert(root);
	root->data = arr[*pi];//根创建且赋值好了
	(*pi)++;

	root->left=CreateTreeTrue(arr, pi);//创建左树
	root->right=CreateTreeTrue(arr, pi);//创建右树
	return root;
}

严格按照> 左子树> 右子树的顺序,每一个左子树又是作为一个根,有自己的左子树及右子树。所以以创建根的方法来创建左子树和右子树,直到遇到#来返回NULL进行终止

4.2二叉树的销毁

销毁我们都使用后序销毁

void TreeDestory(TreeNode** root)
{
	if (*root == NULL)
	{
		return;
	}
	TreeDestory((*root)->left);
	TreeDestory((*root)->right);
	free(*root);
	*root = NULL;
}

因为最后要把root置空,传一级指针不行(没用,形参是临时拷贝),想要改变root本身就传入root的地址(即二级指针


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

也是利用队列,pop出一个后把他的左右节点push进去,遇到NULL就出循环,再看此时队列里是否全是NULL,如果全是NULL那就是完全二叉树,只要还有节点,那就不是完全二叉树

int BinaryTreeComplete(TreeNode* root)
{
	Queue q;
	QInit(&q);
	QPush(&q, root);//根进去了
	int LevelSize = 1;
	while (!QEmpty(&q))
	{
		TreeNode* first = QFront(&q);
		QPop(&q);
		if (first == NULL)
			break;//通过这个出循环
		QPush(&q, first->left);
		QPush(&q, first->right);

	}
    // 已经遇到空节点,如果此时队列中后面的节点还有非空,就不是完全二叉树
	while (!QEmpty(&q))
	{
		TreeNode* first = QFront(&q);
		QPop(&q);
		if (first != NULL)
		{
            QDestroy(&q);
			return 0;
		}
	}
	QDestroy(&q);
	return 1;
}

终于啊,二叉树中较为基本的地方都已经梳理完毕了,相信在不久的将来,还会有二叉树的内容,大家敬请期待吧!!!

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

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

相关文章

用通俗易懂的方式讲解:基于扩散模型(Diffusion),文生图 AnyText 的效果太棒了

近年来&#xff0c;随着AIGC的爆火&#xff0c;图片生成技术得到飞速发展&#xff0c;当前AI生成的图片已达到真假难辨的高保真度。不过&#xff0c;当合成图片中出现文字内容时&#xff0c;仍能够使AI露出马脚&#xff0c;因为当前主流方法尚无法在图片中生成准确可读的字符。…

YOLOv8融合改进 更换检测头为Detect_DyHead同时添加C2f-EMSC和C2f-EMSCP模块

一、Detect_DyHead检测头和C2f-EMSC&#xff0c;C2f-EMSCP模块 详细介绍和代码在往期的博客里&#xff1a; Detect_DyHead&#xff1a; &#xff08;YOLOv8改进检测头Detect为Detect_Dyhead-CSDN博客&#xff09; C2f-EMSC和C2f-EMSCP&#xff1a; &#xff08;YOLOv8改进…

Unity中Shader雾效在场景中的调节技巧

文章目录 前言一、修改棋盘格Shader的Cull可以在属性面板控制1、在属性面板定义CullMode2、在SubShader中&#xff0c;使用CullMode3、这样就可以在不同剔除情况下使用棋盘格场景了 二、调节天际线颜色和雾融为一体1、在摄像机设置不渲染天空盒&#xff0c;渲染单一颜色2、采样…

我开发了一个聚合网盘资源搜索引擎-支持阿里云盘与夸克网盘资源

还在为找不到电子书资源而发愁&#xff1f;还在愁没有高清影视剧观看&#xff1f; 来试试我开发的云盘资源搜索引擎吧&#xff01; 公众号回复关键词: 搜索 ! 就可以获取到网站网址。 这里还有资源分享微信群&#xff0c;不定期分享资源。 关于界面 怎么使用这个引擎&#x…

实验笔记之——下载数据到服务器

开发过程中经常需要把数据传到服务器上&#xff0c;太麻烦了&#xff0c;为此本博文记录采用百度云来传输数据 百度云 使用bypy包。 安装&#xff1a;pip install bypy 配置bypy连接百度网盘&#xff1a; 终端输入bypy info将命令行提示的链接复制到浏览器&#xff0c;并复制…

Github 2024-01-04 开源项目日报 Top10

根据Github Trendings的统计&#xff0c;今日(2024-01-04统计)共有10个项目上榜。根据开发语言中项目的数量&#xff0c;汇总情况如下&#xff1a; 开发语言项目数量Python项目3C项目2TypeScript项目2Java项目2Jupyter Notebook项目1Go项目1 系统设计指南 创建周期&#xff…

Flutter用GridView实现网格功能(1、item设置一个外边框,2、item背景点击变色,松开恢复原色)

GridView接收如下可选参数属性&#xff1a; scrollDirection&#xff1a;滚动方法padding&#xff1a;内边距resolve&#xff1a;组件反向排序crossAxisSpacing&#xff1a;水平子Widget之间间距mainAxisSpacing&#xff1a;垂直子Widget之间间距crossAxisCount&#xff1a;一…

C#/.NET/.NET Core优秀项目和框架2023年12月简报

前言 公众号每月定期推广和分享的C#/.NET/.NET Core优秀项目和框架&#xff08;公众号每周至少推荐两个优秀的项目和框架当然节假日除外&#xff09;&#xff0c;公众号推文有项目和框架的介绍、功能特点以及部分功能截图等&#xff08;打不开或者打开GitHub很慢的同学可以优先…

Wireshark本地回环网络抓包

背景 因为发往本机的数据包是通过回环地址的&#xff0c;即&#xff1a;数据包不会通过真实的网络接口发送&#xff0c;因此我们需要通过设置路由规则来让本来发到虚拟网络接口的数据包发送到真实网络接口即可。 场景描述&#xff1a;在网络程序开发的过程中&#xff0c;有时…

SQL中 Group by Grouping Sets 分组的用法

文章目录 1. 用法2. 语法3. 实际应用3.1 求总和与小计3.2 按多个维度分组3.3 标记小计和总计 1. 用法 将Grouping Sets 运算符添加到Group by 子句中&#xff0c;使用Grouping Set 可以在一个查询中指定数据的多个分组&#xff0c;其结果与针对指定的组执行union all 运算等效…

k8s中的容器探针

pod的容器健康检查---探针 probe&#xff1a;k8s对容器执行的定期检查&#xff0c;诊断。 探针的三种规则 所有的探针都是针对容器不是针对pod 1、 存活探针---livenessProbe&#xff1a;探测容器是否正常运行。如果发现探测失败&#xff0c;会杀掉容器。容器会根据重启策略…

ensp vlan连接(详细)

1.将需要的设备放置好 2.将设备连接起来 3.启动所有设备 4.备注好每台PC机的信息 5.配置好每台PC机 6.配置交换机1 进入配置视图&#xff0c;关闭信息提示 重命名设备 批量创建VLAN 开始配置接口 更改接口类型为ACCESS 将接口划分到对应的VLANN 配置下一个接口&#xff0c;步…

windows server 2012 安装telnet

系统版本 安装telnet 勾选telnet客户端 点击安装 等待安装完成 打开cmd&#xff0c;输入telnet&#xff0c;出现下图&#xff0c;说明安装成功 telnet.exe路径

hAdmin漂亮的后台html模板免费下载

hAdmin漂亮的后台html模板免费下载-遇见你与你分享

STGAN:用于交通数据插补的时空生成对抗网络

文章地址: STGAN: Spatio-temporal generative adversarial network for traffic data imputation 主要研究问题: 由于硬件故障或数据传输,观测到的交通数据中产生了噪声和缺失条目。这些质量差的数据无疑会降低ITS的性能; 本文贡献: 为交通数据插补任务提出了一种改进…

华芯微特MCU之TIMER触发ADC

01 TIMER定时器之脉冲发送功能 我们今天详细讲解一下TIMER的ADC触发功能。 SWM190的TIMER2/3支持SAR ADC触发功能&#xff0c;此功能配置为定时器或脉冲发送均有效&#xff0c;可通过配置相应寄存器实现。 将SAR ADC CTRL寄存器中TRIG设置为TIMER2触发或TIMER3触发。TIMER可作…

手机视频监控客户端APP,实时视频分享,享受免密看直播

目 录 一、媒体分享功能随处可见 二、手机视频监控客户端App分享功能 &#xff08;一&#xff09;手机APP安装 &#xff08;二&#xff09;手机APP功能描述 &#xff08;三&#xff09;实时视频分享介绍 三、实时监控视频分享的应用场景 1、搜救现场 2、指…

教育场景数字化中音视频小程序的发展

教育场景数字化逐步成为刚需 2018年以来&#xff0c;国家对在线教育行业的监管收紧&#xff0c;以及受益于 5G 技术的发展&#xff0c;教育科技逐步走向成熟化和规范化。 教育行业的本质是人与人&#xff08;老师与学生、老师与家长&#xff0c;以及更多角色直接的沟通与互动…

java基于SSM的校内信息服务发布系统的设计与实现+vue论文

校内信息服务发布系统的设计与实现 摘要 近年来&#xff0c;信息化管理行业的不断兴起&#xff0c;使得人们的日常生活越来越离不开计算机和互联网技术。首先&#xff0c;根据收集到的用户需求分析&#xff0c;对设计系统有一个初步的认识与了解&#xff0c;确定校内信息服务发…

GPT-Pilot:AI开发者的伴侣

GPT Pilot 一个真正的AI程序员&#xff0c;它可以从零开始构建整个应用程序&#xff0c;它能自己编写代码、配置开发环境、管理开发任务、调试代码&#xff0c;你还可以随时和它聊天提问帮助你解决开发难题。你只需要在一旁监督开发过程即可... 主要功能 自动化编码&#xff…