数据结构—链式二叉树-C语言

        代码位置：test-c-2024: 对C语言习题代码的练习 (gitee.com)

一、前言：

        在现实中搜索二叉树为常用的二叉树之一，今天我们就要通过链表来实现搜索二叉树。实现的操作有：建二叉树、前序遍历、中序遍历、后序遍历、求树的节点个数、求树的高度、求k层节点个数、查找节点、层序遍历，判断是否是完全二叉树，二叉树的销毁。

二、代码实现：

2.0-开辟空间函数及结构体：

        对于链表我们可以定义一个开辟空间的函数以便于后继的操作。对于结构体成员中我们需要包含节点值data和左右子树节点。

代码如下：

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include "Queue.h"

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 node");
		return NULL;
	}

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

	return node;
}

2.1-建二叉树：

        对于建二叉树我们需要手动搓一个二叉树。

建的树如图所示：

代码如下：

BTNode* CreatTree()			//建二叉树
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);

	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
	
	return node1;
}

2.2-前序遍历：

        二叉树前序遍历规则为：先访问根节点在访问左子树最后访问右子树。我这里是通过函数递归实现的访问。

代码如下：

void PreOrder(BTNode* root)			//前序遍历
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}

2.3-中序遍历：

        二叉树中序遍历规则为：先访问左子树在访问根节点最后访问右子树。我这里是通过函数递归实现的访问。

代码如下：

void InOrder(BTNode* root)			//中序遍历
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

2.4-后序遍历：

        二叉树后序遍历规则为：先访问左子树在访问右子树最后访问根节点。我这里是通过函数递归实现的访问。

代码如下：

void PostOrder(BTNode* root)			//后序遍历
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

2.5-求树的节点个数：

        这里是通过三目操作符以及递归来实现的统计节点个数。原理是如果该节点不是空节点则整体个数加1，然后继续访问下一子树，直到遍历完为止。

代码如下：

int TreeSize(BTNode* root)         //求节点个数
{
	return root == NULL ? 0
		: TreeSize(root->left)
		+ TreeSize(root->right)
		+ 1;
}

2.6-求树的高度：

        这里是通过leftHeight和rightHeight来存储左右子树高度值，然后在return中通过三目运算符来返回高的那一子树在加1（这里加1是节点本身占一个高度）

代码如下：

int TreeHeight(BTNode* root)
{
	if (root == NULL)
		return 0;
	int leftHeight = TreeHeight(root->left);
	int rightHeight = TreeHeight(root->right);

	return leftHeight> rightHeight
	? leftHeight + 1
	: rightHeight + 1;
}

2.7-求k层节点个数：

        这里是通过递归传k-1是为了找到k层的所有节点若存在则返回1，不存在返回0然后将所有返回值相加返回即是第k层的节点个数。

代码如下：


int TreeLeave(BTNode* root,int k)		//求k层节点个数
{
	assert(k > 0);
	if (root == NULL)
	{
		return 0;
	}
	if(k==1)
	{
		return 1;
	}

	return TreeLeave(root->left, k - 1) +TreeLeave(root->right, k - 1);
}

2.8-查找节点：

        这里是通过递归遍历一遍树查找是否存在查找值若存在则返回该节点，若不存在则返回NULL。（注：这个函数只能查找出该值前序遍历第一次出现的位置）

代码如下：


BTNode* BinaryTreeFind(BTNode* root, BTDataType x)		//查找
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->data == x)
	{
		return root;
	}
	BTNode* p = BinaryTreeFind(root->left, x);
	if(p)
	return p;
	BTNode * q=BinaryTreeFind(root->right, x);
	if (q )
	return q;

	return NULL;
}

2.9-层序遍历：

        这里需要用到队列以前的博客里我们实现过队列，所以这里我们可以当个CV工程师将以前的代码复制过来即可。

队列代码：

#pragma once

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

typedef struct BinaryTreeNode* QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;

void QueueInit(Queue* pq);								//初始化
void QueueDestory(Queue* pq);							//释放销毁
void QueuePush(Queue* pq,QDataType x);		//入队	
void QueuePop(Queue* pq);								//出队
int QueueSize(Queue* pq);								//元素个数
bool QueueEmpty(Queue* pq);							//判断队空
QDataType QueueFront(Queue* pq);					//队头数据
QDataType QueueBack(Queue* pq);					//队尾数据
#define _CRT_SECURE_NO_WARNINGS 1

#include "Queue.h"


void QueueInit(Queue* pq)			    					//初始化
{
	assert(pq);

	pq->head = pq->tail = NULL;
	pq->size = 0;
}

void QueueDestory(Queue* pq)     					//释放销毁
{
	assert(pq);

	QNode* cur =pq->head;
	while (cur)
	{
		pq->head = cur->next;
		free(cur);
		cur = NULL;
		cur = pq->head;
	}
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

void QueuePush(Queue* pq, QDataType x)		//入队	
{
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;

	if (pq->head == NULL)
	{
		assert(pq->tail==NULL);

		pq->head = pq->tail=newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;
}

void QueuePop(Queue* pq)								//出队
{
	assert(pq);
	assert(!QueueEmpty(pq));

	QNode* del = pq->head;
	pq->head = pq->head->next;
	free(del);
	del = NULL;
	if (pq->head == NULL)
	{
		pq->tail = NULL;
	}
	pq->size--;
}

int QueueSize(Queue* pq)								//元素个数
{
	assert(pq);

	return pq->size;
}

bool QueueEmpty(Queue* pq)							//判断队空
{
	assert(pq);

	return pq->size == 0;
}

QDataType QueueFront(Queue* pq)					//队头数据
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->head->data;
}

QDataType QueueBack(Queue* pq)					//队尾数据
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->tail->data;
}

遍历代码如下：

void LevelOrder(BTNode* root)				//层序遍历
{
	Queue p;
	QueueInit(&p);
	if(root)
		QueuePush(&p, root);
	while (!QueueEmpty(&p))
	{
		BTNode* front = QueueFront(&p);		//取队列首元素的值
		QueuePop(&p);
		printf("%d ", front->data);

		if (front->left)			//入下一层元素
		{
			QueuePush(&p, front->left);
		}
		if (front->right)
		{
			QueuePush(&p, front->right);
		}
	}

	QueueDestory(&p);
}

        层序遍历代码执行的过程如图所示：

2.10-判断是否是完全二叉树：

        判断完全二叉树是通过层序遍历和队列来实现。注意这里的层序遍历遇到空树也需要入队，为了判断二叉树是否为完全二叉树。原理：//层序遍历第一次遇到NULL时若后面没有数据节点则是完全二叉树，反之则不是

代码如下：

bool TreeComplete(BTNode* root)		//判断是否是完全二叉树
{
	Queue pq;
	QueueInit(&pq);
	QueuePush(&pq, root);
	while (!QueueEmpty(&pq))
	{
		BTNode* front = QueueFront(&pq);
		if (QueueFront(&pq) == NULL)
		{
			break;
		}
		QueuePop(&pq);

		QueuePush(&pq, front->left);
		QueuePush(&pq, front->right);
	}
	//层序遍历第一次遇到NULL时若后面没有数据节点则是完全二叉树，反之则不是
	while (!QueueEmpty(&pq))				
	{
		if (QueueFront(&pq) != NULL)
		{
			QueueDestory(&pq);
			return false;
		}
		QueuePop(&pq);
	}
	QueueDestory(&pq);
	return true;
}

2.11-二叉树的销毁：

        二叉树销毁需遍历一遍链表，这里采用后序遍历比较方便，因为另外两个遍历都会因为释放根节点后左右子节点不好释放而产生不必要的麻烦，所以这里最好是使用后序遍历。注意这里只是释放掉了空间，因为这里是一级指针所以这里置空属于局部变量不会影响外部，所以在主函数调用时我们需手动置空。

如图所示：

代码如下：

void TreeDestory(BTNode* root)		//销毁二叉树
{
	if (root == NULL)
		return;
	TreeDestory(root->left);
	TreeDestory(root->right);
	free(root);
}

三、结语：

递归效果图展示：

最终效果图为：

        上述内容，即是我个人对数据结构-链式二叉树-搜索二叉树-C语言的个人见解以及自我实现。若有大佬发现哪里有问题可以私信或评论指教一下我这个小萌新。非常感谢各位友友们的点赞，关注，收藏与支持，我会更加努力的学习编程语言，还望各位多多关照，让我们一起进步吧！

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

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

相关文章

AI音乐创作：一键生成，打造你的专属乐章

AI音乐创作：一键生成，打造你的专属乐章

文章目录 &#x1f34a;AI音乐创作&#xff1a;一键生成&#xff0c;打造你的专属乐章1 市面上的AI音乐应用1.1 Suno AI1.2 网易天音 2 AI音乐创作的流程2.1 AI音乐风格/流派2.2 AI音乐的结构顺序2.3 使用KIMI生成AI音乐歌词2.4 选择AI音乐乐器2.5 书写AI音乐提示词2.5.1 方法一…
阅读更多...
Java NIO 比传统 IO 强在哪里？

Java NIO 比传统 IO 强在哪里？

这里先给大家展示一副传统 IO 和 NIO 的对比图&#xff0c;感受一下。 传统IO基于字节流或字符流&#xff08;如 FileInputStream、BufferedReader 等&#xff09;进行文件读写&#xff0c;以及使用Socket和ServerSocketChannel进行网络传输。 NIO 使通道&#xff08;Channel&a…
阅读更多...
【过题笔记】 7.15

【过题笔记】 7.15

Array Without Local Maximums 算法&#xff1a;动态规划 简要思路&#xff1a; 考虑左边的数跟当前位置的关系&#xff0c;不难想到只有三种情况&#xff1a;大于&#xff0c;小于&#xff0c;等于。 于是可以得到状态 f [ i ] [ j ] [ 0 / 1 / 2 ] f[i][j][0/1/2] f[i][j][…
阅读更多...
ubuntu22.04安装SecureCRT8.7.3，完成顺利使用

ubuntu22.04安装SecureCRT8.7.3，完成顺利使用

材料准备 scrt-sfx安装包 &#xff0c; securecrt_linux_crack.pl 补丁脚本&#xff0c;和两个依赖库 其中securecrt_linux_crack.pl是找的专门适合 8.7.3版本的&#xff0c;网上很多版本的crack.pl只能打补丁以前的老版本。 而更老版本的SecureCRT对ubuntu22支持更不好&#…
阅读更多...
数据库使用SSL加密连接

数据库使用SSL加密连接

简介 数据库开通SSL加密连接是确保数据传输过程中安全性的关键措施&#xff0c;它通过加密数据、验证服务器身份、保护敏感信息、维护数据完整性和可靠性&#xff0c;同时满足行业标准和法规要求&#xff0c;进而提升用户体验和信任度&#xff0c;为企业的数据安全和业务连续性…
阅读更多...
HTML5+CSS3小实例：纯CSS实现奥运五环

HTML5+CSS3小实例：纯CSS实现奥运五环

实例：纯CSS实现奥运五环 技术栈：HTML+CSS 效果： 源码： 【HTML】 <!DOCTYPE html> <html lang="zh-CN"> <head><meta charset="UTF-8"><meta name="viewport" content="width=device-width, initial-sca…
阅读更多...
1.CATIA：CAA调用Excel接口

1.CATIA：CAA调用Excel接口

生成调用Excel的头文件 参考如下进行excel头文件的生成： 如何使用vs2022通过excel.exe生成VC、C++能够使用的头文件 添加如下的接口： #include "CApplication.h" #include "CWorkbook.h" #include "CWorkbooks.h" #include "CWorkshee…
阅读更多...
AMD software 将两个显示器合并为一个超宽显示器

AMD software 将两个显示器合并为一个超宽显示器

最近玩游戏的时候&#xff0c;发现了一个骚操作。 可以将两个显示器&#xff08;更多个的自己去试&#xff0c;不知道&#xff09;组合为一个显示器&#xff0c;注意&#xff0c;这里说的不是将两个显示都连接电脑从而使用双屏显示器&#xff0c; 而是 将两个显示器组合为一个…
阅读更多...
实验一：图像信号的数字化

实验一：图像信号的数字化

目录 一、实验目的 二、实验原理 三、实验内容 四、源程序及结果 源程序&#xff08;python&#xff09;&#xff1a; 结果&#xff1a; 五、结果分析 一、实验目的 通过本实验了解图像的数字化过程&#xff0c;了解数字图像的数据矩阵表示法。掌握取样&#xff08;象素个…
阅读更多...
利用AI辅助制作ppt封面

利用AI辅助制作ppt封面

如何利用AI辅助制作一个炫酷的PPT封面 标题使用镂空字背景替换为动态视频 标题使用镂空字 1.首先&#xff0c;新建一个空白的ppt页面&#xff0c;插入一张你认为符合主题的图片&#xff0c;占满整个可视页面。 2.其次&#xff0c;插入一个矩形&#xff0c;右键选择设置形状格式…
阅读更多...
uniapp-vue3-vite 搭建小程序、H5 项目模板

uniapp-vue3-vite 搭建小程序、H5 项目模板

uniapp-vue3-vite 搭建小程序、H5 项目模板 特色准备拉取默认UniApp模板安装依赖启动项目测试结果 配置自动化导入安装依赖在vite.config.js中配置 引入 prerttier eslint stylelint.editorconfig.prettierrc.cjs.eslintrc.cjs.stylelintrc.cjs 引入 husky lint-staged com…
阅读更多...
2024Datawhale AI夏令营---基于术语词典干预的机器翻译挑战赛--学习笔记

2024Datawhale AI夏令营---基于术语词典干预的机器翻译挑战赛--学习笔记

#Datawhale #NLP 1.背景介绍&#xff1a; 机器翻译&#xff08;Machine Translation&#xff0c;简称MT&#xff09;是自然语言处理领域的一个重要分支&#xff0c;其目标是将一种语言的文本自动转换为另一种语言的文本。机器翻译的发展可以追溯到20世纪50年代&#xff0c;经历…
阅读更多...
springboot 适配ARM 架构

springboot 适配ARM 架构

下载对应的maven https://hub.docker.com/_/maven/tags?page&page_size&ordering&name3.5.3-alpinedocker pull maven:3.5.3-alpinesha256:4c4e266aacf8ea6976b52df8467134b9f628cfed347c2f6aaf9e6aff832f7c45 2、下载对应的jdk https://hub.docker.com/_/o…
阅读更多...
【银河麒麟操作系统】虚机重启lvs丢失现象分析及处理建议

【银河麒麟操作系统】虚机重启lvs丢失现象分析及处理建议

了解银河麒麟操作系统更多全新产品&#xff0c;请点击访问麒麟软件产品专区&#xff1a;https://product.kylinos.cn 环境及现象描述 40台虚机强制重启后&#xff0c;其中8台虚机找不到逻辑卷导致启动异常&#xff0c;后续通过pvcreate 修复重建pv&#xff0c;激活vg和lv并修复…
阅读更多...
矿产资源潜力预测不确定性评价

矿产资源潜力预测不确定性评价

研究目的&#xff1a; 不确定性评估&#xff1a; 到底什么叫不确定性&#xff0c;简单来说就是某区域内的矿产资源量&#xff0c;并不确定到底有多少&#xff0c;你需要给出一个评估或者分布。 研究方法&#xff1a; 1.以模糊集来表示某些量&#xff1a; 关于什么是模糊集&am…
阅读更多...
AWS Aurora Postgres 的开源替代品：存储和计算分离 | 开源日报 No.278

AWS Aurora Postgres 的开源替代品：存储和计算分离 | 开源日报 No.278

neondatabase/neon Stars: 13.0k License: Apache-2.0 Neon 是一个无服务器的开源替代品&#xff0c;用于 AWS Aurora Postgres。它将存储和计算分离&#xff0c;通过在节点集群中重新分配数据来替换 PostgreSQL 存储层。 提供自动扩展、分支和无限存储。Neon 安装包括计算节…
阅读更多...
【常见开源库的二次开发】基于openssl的加密与解密——Base58比特币钱包地址——算法分析（三）

【常见开源库的二次开发】基于openssl的加密与解密——Base58比特币钱包地址——算法分析（三）

目录&#xff1a; 目录&#xff1a; 一、base58(58进制) 1.1 什么是base58&#xff1f; 1.2 辗转相除法 1.3 base58输出字节数&#xff1a; 二、源码分析&#xff1a; 2.1源代码&#xff1a; 2.2 算法思路介绍&#xff1a; 2.2.1 Base58编码过程&#xff1a; 2.1.2 Base58解码过…
阅读更多...
基于高德地图实现Android定位功能实现（二）

基于高德地图实现Android定位功能实现（二）

基于高德地图实现Android定位功能实现&#xff08;二&#xff09; 在实现的高德地图的基本显示后&#xff0c;我们需要不断完善地图的功能 地图界面设计&#xff08;悬浮按钮等&#xff09; 首先就是地图页面的布局&#xff0c;这个根据大家的实际需求进行设计即可&#xff…
阅读更多...
nacos 适配瀚高数据库、ARM 架构

nacos 适配瀚高数据库、ARM 架构

下载nacos源码： https://github.com/alibaba/nacos/tree/2.3.1 瀚高技术文档 1、修改pom.xml 根目录nacos-all => pom.xml<dependencyManagement><dependency><groupId>com.highgo</groupId><artifactId>HgdbJdbc</artifactId><…
阅读更多...
xss复习总结及ctfshow做题总结xss

xss复习总结及ctfshow做题总结xss

xss复习总结 知识点 1.XSS 漏洞简介 ​ XSS又叫CSS&#xff08;Cross Site Script&#xff09;跨站脚本攻击是指恶意攻击者往Web页面里插入恶意Script代码&#xff0c;当用户浏览该页之时&#xff0c;嵌入其中Web里面的Script代码会被执行&#xff0c;从而达到恶意攻击用户的…
阅读更多...
最新文章

Copyright @ 2022~2023