数据结构之链式结构二叉树的实现(初级版)

本文内容将主会多次用到函数递归知识!!!

本节内容需要借助画图才能更好理解!!!

和往常一样,还是创建三个文件

这是tree.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef char btdatatype;
//定义二叉树结点结果
typedef struct binarytreenode
{
	btdatatype data;
	struct binarytreenode* left;
	struct binarytreenode* right;
}btnode;

//前序遍历
void preorder(btnode* root);
//中序遍历
void InOrder(btnode* root);
//后序遍历
void PostOrder(btnode* root);

// ⼆叉树结点个数
int BinaryTreeSize(btnode* root);
// ⼆叉树叶⼦结点个数
int BinaryTreeLeafSize(btnode* root);
// ⼆叉树第k层结点个数
int BinaryTreeLevelKSize(btnode* root, int k);
//⼆叉树的深度/⾼度
int BinaryTreeDepth(btnode* root);
// ⼆叉树查找值为x的结点
btnode* BinaryTreeFind(btnode* root, btdatatype x);
// ⼆叉树销毁
void BinaryTreeDestory(btnode** root);

这是tree.c

​
#include"tree.h"
//先序遍历--根左右
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);
}
int BinaryTreeSize(btnode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
// ⼆叉树叶⼦结点个数
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层结点个数
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);
	//从上往下索引,索引一层就k-1
}
//⼆叉树的深度/⾼度  ???
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);
}
// ⼆叉树查找值为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;
}
//传二级指针可以这样简单理解,销毁即把指向这一空间的指针(地址)置为NULL,而我们的root是一个一级指针,要将其销毁,则需要将其地址置为NULL,故传二级指针
void BinaryTreeDestory(btnode** root)
{
	if (*root == NULL)
	{
		return;
	}BinaryTreeDestory(&((*root)->right));
	
	BinaryTreeDestory(&((*root)->left));
	free(*root);
	*root = NULL;
}
​

这是test.c

​
#include"tree.h"
btnode* buynode(btdatatype x)
{
	btnode* node = (btnode*)malloc(sizeof(btnode));
	assert(node);
	node->data = x;
	node->left = node->right = NULL;
	return node;
}
//手动构造一棵二叉树
btnode* createtree()
{
	btnode* nodeA = buynode('A');      //字符不要用双引号!!!
	btnode* nodeB = buynode('B');
	btnode* nodeC = buynode('C');
	btnode* nodeD = buynode('D');
	btnode* nodeE = buynode('E');
	btnode* nodeF = buynode('F');

	nodeA->left = nodeB;
	nodeA->right = nodeC;
	nodeB->left = nodeD;
	nodeC->left = nodeE;
	nodeC->right = nodeF;

	return nodeA;
}
void test()
{
	btnode* root = createtree();
	preorder(root);
	printf("\n");
	InOrder(root);
	printf("\n");
	PostOrder(root);
	printf("\n");

	printf("size:%d\n", BinaryTreeSize(root));
	printf("size:%d\n", BinaryTreeSize(root));

	printf("leaf size:%d\n", BinaryTreeLeafSize(root));
	printf("k size:%d\n", BinaryTreeLevelKSize(root, 2));
	printf("k size:%d\n", BinaryTreeLevelKSize(root, 3));
	printf("k size:%d\n", BinaryTreeLevelKSize(root, 1));
	printf("depth:%d\n", BinaryTreeDepth(root));
	btnode* find = BinaryTreeFind(root, 'A');
	if (find == NULL)
	{
		printf("not found!");
	}
	else
	{
		printf("we've found it!");
	}
    BinaryTreeDestory(&root);
}
int main()
{
	test();
	return 0;
}

​

说明:

1. 遍历规则
按照规则,⼆叉树的遍历有:前序/中序/后序的递归结构遍历:
1)前序遍历(Preorder Traversal 亦称先序遍历):访问根结点的操作发生在遍历其左右子树之前
访问顺序为:根结点、左子树、右子树
2)中序遍历(Inorder Traversal):访问根结点的操作发生在遍历其左右子树之中(间)
访问顺序为:左子树、根结点、右子树
3)后序遍历(Postorder Traversal):访问根结点的操作发生在遍历其左右子树之后

访问顺序为:左子树、右子树、根结点 

图解遍历:
以前序遍历为例:

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

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

相关文章

数据结构(Java)—— 认识泛型

1. 包装类 在学习泛型前我们需要先了解一下包装类 在 Java 中&#xff0c;由于基本类型不是继承自 Object &#xff0c;为了在泛型代码中可以支持基本类型&#xff0c; Java 给每个基本类型都对应了一个包装类型。 1.1 基本数据类型和对应的包装类 基本数据类型包装类byteByt…

LSTM模型改进实现多步预测未来30天销售额

项目源码获取方式见文章末尾&#xff01; 600多个深度学习项目资料&#xff0c;快来加入社群一起学习吧。 《------往期经典推荐------》 项目名称 1.【BiLSTM模型实现电力数据预测】 2.【卫星图像道路检测DeepLabV3Plus模型】 3.【GAN模型实现二次元头像生成】 4.【CNN模型实…

使用带有令牌认证的 Jupyter Notebook 服务器

当你不想在默认浏览器打开Jupyter Notebook,但是在其他浏览器打开http://localhost:8890/lab或者http://localhost:8889/tree&#xff0c;却显示 Token authentication is enabled&#xff0c;如下图 可以按以下步骤操作&#xff1a; 获取令牌&#xff1a;在启动 Jupyter Note…

软考(中级-软件设计师)数据库篇(1101)

第6章 数据库系统基础知识 一、基本概念 1、数据库 数据库&#xff08;Database &#xff0c;DB&#xff09;是指长期存储在计算机内的、有组织的、可共享的数据集合。数据库中的数据按一定的数据模型组织、描述和存储&#xff0c;具有较小的冗余度、较高的数据独立性和扩展…

【java】java的基本程序设计结构06-运算符

运算符 一、分类 算术运算符关系运算符位运算符逻辑运算符赋值运算符其他运算符 1.1 算术运算符 操作符描述例子加法 - 相加运算符两侧的值A B 等于 30-减法 - 左操作数减去右操作数A – B 等于 -10*乘法 - 相乘操作符两侧的值A * B等于200/除法 - 左操作数除以右操作数B /…

躺平成长-代码开发(07)-利用kimi帮助自己写代码

开源竞争&#xff1a; 开源竞争&#xff08;当你无法彻底掌握技术的时候&#xff0c;就去开源这个技术&#xff0c;让更多人了解这个技术&#xff0c;随着越来越多的人了解这个技术&#xff0c;就会培养出更多的技术依赖&#xff0c;让更多的人帮助你们完善你的技术依赖&#x…

基于javaweb(springboot+mybatis)网站建设服务管理系统设计和实现以及文档报告设计

基于javaweb(springbootmybatis)网站建设服务管理系统设计和实现以及文档报告设计 &#x1f345; 作者主页 网顺技术团队 &#x1f345; 欢迎点赞 &#x1f44d; 收藏 ⭐留言 &#x1f4dd; &#x1f345; 文末获取源码联系方式 &#x1f4dd; &#x1f345; 查看下方微信号获取…

时间序列预测(十)——长短期记忆网络(LSTM)

目录 一、LSTM结构 二、LSTM 核心思想 三、LSTM分步演练 &#xff08;一&#xff09;初始化 1、权重和偏置初始化 2、初始细胞状态和隐藏状态初始化 &#xff08;二&#xff09;前向传播 1、遗忘门计算&#xff08;决定从上一时刻隐状态中丢弃多少信息&#xff09; 2、…

Sigrity Power SI 3D-EM Full Wave Extraction模式如何进行S参数提取和观测3D电磁场和远场操作指导(一)

Sigrity Power SI 3D-EM Full Wave Extraction模式如何进行S参数提取和观测3D电磁场和远场操作指导(一) Sigrity Power SI的3D-EM Full Wave Extraction模式是Power SI的3D全波提取工具,相比于2D提取,3D全波提取的结果更为精确,且支持设置跨平面的port,也就是lump port,这…

rhce:web服务器

web服务器简介 服务器端&#xff1a;此处使用 nginx 提供 web 服务&#xff0c; RPM 包获取&#xff1a; http://nginx.org/packages/ /etc/nginx/ ├── conf.d #子配置文件目录 ├── default.d ├── fastcgi.conf ├── fastcgi.conf.default ├── fastcgi_params #用…

jenkins国内插件源

Jenkins是一个开源的持续集成和持续部署&#xff08;CI/CD&#xff09;工具, 可以大大减轻部署的工作量, 但是jenkins作为一个国外的软件, 在国内下载插件会很麻烦, 因此我们可以将其换为国内源 更换步骤 替换国内插件下载地址 以linux为例 首先, jenkins初始化完成之后不会…

DiffusionDet: Diffusion Model for Object Detection—用于对象检测的扩散模型论文解析

DiffusionDet: Diffusion Model for Object Detection—用于对象检测的扩散模型论文解析 这是一篇发表在CVPR 2023的一篇论文&#xff0c;因为自己本身的研究方向是目标跟踪&#xff0c;之前看了一点使用扩散模型进行多跟踪的论文&#xff0c;里面提到了DiffusionDet因此学习一…

idea 配置tomcat 服务

选择tomcat的安装路径 选到bin的文件夹的上一层就行

opencv 图像预处理

图像预处理 ​ 在计算机视觉和图像处理领域&#xff0c;图像预处理是一个重要的步骤&#xff0c;它能够提高后续处理&#xff08;如特征提取、目标检测等&#xff09;的准确性和效率。OpenCV 提供了许多图像预处理的函数和方法&#xff0c;以下是一些常见的图像预处理操作&…

初始JavaEE篇——多线程(4):wait、notify,饿汉模式,懒汉模式,指令重排序

找往期文章包括但不限于本期文章中不懂的知识点&#xff1a; 个人主页&#xff1a;我要学编程(ಥ_ಥ)-CSDN博客 所属专栏&#xff1a;JavaEE 目录 wait、notify 方法 多线程练习 单例模式 饿汉模式 懒汉模式 指令重排序 wait、notify 方法 wait 和 我们前面学习的sleep…

新工具可绕过 Google Chrome 的新 Cookie 加密系统

一位研究人员发布了一款工具&#xff0c;用于绕过 Google 新推出的 App-Bound 加密 cookie 盗窃防御措施并从 Chrome 网络浏览器中提取已保存的凭据。 这款工具名为“Chrome-App-Bound-Encryption-Decryption”&#xff0c;由网络安全研究员亚历山大哈格纳 (Alexander Hagenah…

JavaSE笔记4】API、包、String类、Object类

目录 一、API 二、包 2.导入不同包下的同名程序 三、String 1. String类是什么&#xff1f; 2. 如何创建String对象?(常用的四种方法&#xff09; 3. String API a. 遍历字符串 b. 判断字符串内容是否相等&#xff1a; c. 截取子串 d. 替换部分内容 e. 匹配子串 f. 匹配开头字…

【含文档】基于ssm+jsp的超市订单后台理系统(含源码+数据库+lw)

1.开发环境 开发系统:Windows10/11 架构模式:MVC/前后端分离 JDK版本: Java JDK1.8 开发工具:IDEA 数据库版本: mysql5.7或8.0 数据库可视化工具: navicat 服务器: apache tomcat 主要技术: Java,Spring,SpringMvc,mybatis,mysql,vue 2.视频演示地址 3.功能 该系统有两个主…

雷军救WPS“三次”,WPS注入新生力量,不再“抄袭”微软

救WPS“三次” 1989年&#xff0c;求伯君用128万行代码编写出了WPS1.0&#xff0c;宣告了中国自主办公时代的开启。 那时候&#xff0c;雷军还在武汉大学深造&#xff0c;他早就把求伯君当成了自己的榜样&#xff0c;这一来二去的&#xff0c;雷军和WPS之间也就结下了不解之缘…

MySQL中,如何定位慢查询?定位到的慢SQL如何分析?

目录 1. 慢查询发生的场景&#xff1f; 2. MySQL中&#xff0c;如何定位慢查询&#xff1f; 2.1 详细解释 3. 定位到的慢SQL如何分析&#xff1f; 3.1 详细说明 1. 慢查询发生的场景&#xff1f; 2. MySQL中&#xff0c;如何定位慢查询&#xff1f; 介绍一下当时产生问题…