【初阶数据结构篇】链式结构二叉树(二叉链)的实现(感受递归暴力美学)

文章目录

须知

💬 欢迎讨论:如果你在学习过程中有任何问题或想法,欢迎在评论区留言,我们一起交流学习。你的支持是我继续创作的动力!

👍 点赞、收藏与分享:觉得这篇文章对你有帮助吗?别忘了点赞、收藏并分享给更多的小伙伴哦!你们的支持是我不断进步的动力!
🚀 分享给更多人:如果你觉得这篇文章对你有帮助,欢迎分享给更多对C++感兴趣的朋友,让我们一起进步!

上篇已经实现过顺序结构二叉树-》堆

1. 链式结构二叉树的实现

1.1 二叉树的概念与结构
1.1.1 链式二叉树概念
⽤链表来表⽰⼀棵⼆叉树,即⽤链来指示元素的逻辑关系。 通常的⽅法是链表中每个结点由三个域组成, 数据域 左右指针域 ,左右指针分别⽤来给出该结点左孩⼦和右孩⼦所在的链结点的存储地址 。
1.1.2 链式二叉树结构
typedef int BTDataType;
typedef struct BinaryTreeNode
{
    BTDataType data;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
}BTNode;
1.2 创建二叉树

 ⼆叉树的创建⽅式⽐较复杂,为了更好的步⼊到⼆叉树内容中,我们先⼿动创建⼀棵链式⼆叉树

BTNode* BuyBTNode(int val)
{
BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
if (newnode == NULL)
{
perror("malloc fail");
return NULL;
}
newnode->val = val;
newnode->left = NULL;
newnode->right = NULL;
return newnode;
}
BTNode* CreateTree()
{
BTNode* n1 = BuyBTNode(1);
BTNode* n2 = BuyBTNode(2);
BTNode* n3 = BuyBTNode(3);
BTNode* n4 = BuyBTNode(4);
BTNode* n5 = BuyBTNode(5);
BTNode* n6 = BuyBTNode(6);
BTNode* n7 = BuyBTNode(7);
n1->left = n2;
n1->right = n4;
n2->left = n3;
n4->left = n5;
n4->right = n6;
n5->left = n7;return n1;
}

回顾

1. ⼆叉树分为空树和⾮空⼆叉树,⾮空⼆叉树由根结点、根结点的左⼦树、根结点的右⼦树组成的。

2. 根结点的左⼦树和右⼦树分别⼜是由⼦树结点、⼦树结点的左⼦树、⼦树结点的右⼦树组成的,因此⼆叉树定义是递归式的,后序链式⼆叉树的操作中基本都是按照该概念实现的。

BinaryTree.h

头文件包括函数的定义,其他头文件以及二叉树的结构

我们将依次实现下面重要的函数

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//定义二叉树的链式结构
//二叉树结点的结构
typedef int BTDataType;
typedef struct BinaryTreeNode
{int data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;//前序遍历
void PreOrder(BTNode* root);
//中序遍历
void InOrder(BTNode* root);
//后序遍历 
void PostOrder(BTNode* root);// ⼆叉树结点个数
int BinaryTreeSize(BTNode* root);// ⼆叉树结点个数
//void BinaryTreeSize(BTNode* root, int* psize);// ⼆叉树叶子结点个数
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);//层序遍历
void LevelOrder(BTNode* root);//判断二叉树是否为完全二叉树
bool BinaryTreeComplete(BTNode* root);

在程序开发前,一般每次写出函数,就会进行测试,一遍进行检查错误。

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Binary.h"BTNode * buyNode(BTDataType x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->left = newnode->right = NULL;return newnode;
}void test01()
{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 = node3;node2->right = node4;//node2->right = node5;//node3->left = node6;//PreOrder(node1);//printf("\n");//InOrder(node1);//printf("\n");//PostOrder(node1);//int size = 0;//BinaryTreeSize(node1, &size);//printf("size : %d\n", size);size = 0;//BinaryTreeSize(node1, &size);//printf("size : %d\n", size);//printf("size:%d\n", BinaryTreeSize(node1));//printf("size:%d\n", BinaryTreeSize(node1));//printf("size:%d\n", BinaryTreeSize(node1));//printf("leaf size: %d\n", BinaryTreeLeafSize(node1));//printf("第K层size : %d\n", BinaryTreeLevelKSize(node1, 2));//printf("depth/height:%d\n", BinaryTreeDepth(node1));//BTNode* find =BinaryTreeFind(node1, 33);//printf("%s\n", find == NULL ? "未找到!" : "找到了!");//LevelOrder(node1);bool ret = BinaryTreeComplete(node1);printf("%s\n", ret == false ? "不是完全二叉树" : "是完全二叉树");BinaryTreeDestory(&node1);
}int main()
{test01();return 0;
}

BinaryTree.cpp 这个源文件都是实现头文件的,定义。

下面我们将直接上高速,不再多废话了.

2. 函数的定义

2.1 二叉树的遍历

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

偷偷告诉大家我是如何记这个规则,自我感觉很有用,子树都是从左往右遍历,看什么遍历,例如前序遍历,就说明根在前。

2.1.1.1 前序遍历

核心思想:递归(先递推,再递归)

首先递归一定要有结束条件,没有则会无限递归,死循环。

当递归到叶子节点,左右节点都为NULL,结束递推,逐次递归回上一次创建函数栈帧。

root==NULL

void PreOrder(BTNode* root)
{if (root == NULL){return;}printf("%d ", root->data);PreOrder(root->left);PreOrder(root->right);
}

图示:

 2.1.1.2 中序遍历
//中序遍历--左根右
void InOrder(BTNode* root)
{if (root == NULL){return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}
2.1.1.3 后序遍历
void PostOrder(BTNode* root)
{if (root == NULL){//printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);
}
2.2 二叉树节点个数

本节点+左节点+右节点

当节点为空,返回0

int BinaryTreeSize(BTNode* root)
{if (root == NULL){return 0;}return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

图解:

 2.3 二叉树叶子节点个数

叶子结点:度为0,即没有孩子节点

// ⼆叉树叶⼦结点个数
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);
}

图解:

2.4 二叉树第k层节点个数

求第k层左子树节点个数+第k层右子树节点个数

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

 图解:

2.5 二叉树的深度/高度
  • 要求高度,即子树高度的最大值+1,子树高度的最大值又是其子树高度最大值+1,以此类推
  • 当递推到空节点时结束——>返回0(空节点不算高度)
  • 回归时每次返回左右子树高度取最大值+1
//⼆叉树的深度/⾼度
int BinaryTreeDepth(BTNode* root)
{if (root == NULL){return 0;}int leftDep = BinaryTreeDepth(root->left);int rightDep = BinaryTreeDepth(root->right);return leftDep > rightDep ? leftDep + 1 : rightDep + 1;
}
源代码(C++)
#define _CRT_SECURE_NO_WARNINGS 1
#include "Binary.h"
#include "Queue.h"
//前序遍历---根左右
void PreOrder(BTNode* root)
{if (root == NULL){return;}printf("%d ", root->data);PreOrder(root->left);PreOrder(root->right);
}//中序遍历--左根右
void InOrder(BTNode* root)
{if (root == NULL){return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}//后序遍历 ---左右根
void PostOrder(BTNode* root)
{if (root == NULL){//printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);
}
// ⼆叉树结点个数
//int size = 0;
//int BinaryTreeSize(BTNode* root)
//{
//	if (root == NULL)
//	{
//		return 0;
//	}
//	++size;
//	BinaryTreeSize(root->left);
//	BinaryTreeSize(root->right);
//	return size;
//}//错误的写法
//void BinaryTreeSize(BTNode* root,int* psize)
//{
//	if (root == NULL)
//	{
//		return 0;
//	}
//	++(*psize);
//	BinaryTreeSize(root->left,psize);
//	BinaryTreeSize(root->right,psize);
//}// ⼆叉树结点个数
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);
}
//⼆叉树的深度/⾼度
int BinaryTreeDepth(BTNode* root)
{if (root == NULL){return 0;}int leftDep = BinaryTreeDepth(root->left);int rightDep = BinaryTreeDepth(root->right);return leftDep > rightDep ? leftDep + 1 : rightDep + 1;
}
// ⼆叉树查找值为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;
}// ⼆叉树销毁
void BinaryTreeDestory(BTNode** root)
{if (*root == NULL){return;}BinaryTreeDestory(&((*root)->left));BinaryTreeDestory(&((*root)->right));free(*root);*root = NULL;
}

 相信通过这篇文章你对二叉树递归暴力的有了初步的了解。如果此篇文章对你学习数据结构(二叉树)有帮助,期待你的三连,你的支持就是我创作的动力!!!

下一篇文章再会!!!

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

aws(学习笔记第十课) 对AWS的EBS如何备份(snapshot)以及使用snapshot恢复数据,AWS实例存储

aws(学习笔记第十课) 对AWS的EBS如何备份&#xff08;snapshot&#xff09;以及使用snapshot&#xff0c;AWS实例存储 学习内容&#xff1a; 对AWS的EBS如何备份AWS实例存储EBS和实例存储的不足 1. 对AWS的EBS如何备份&#xff08;snapshot&#xff09;以及使用snapshot恢复数…

适用于 c++ 的 wxWidgets框架源码编译SDK-windows篇

本文章记录了下载wxWidgets源码在windows 11上使用visual Studio 2022编译的全过程,讲的不详细请给我留言,让我知道错误并改进。 本教程是入门级。有更深入的交流可以留言给我。 如今互联网流行现在大家都忘记了这块桌面的开发,我认为桌面应用还是有用武之地,是WEB无法替代…

Pycharm贪吃蛇小游戏后续2

前文中我们提到用面向对象去编写贪吃蛇 目前功能实现贪吃蛇吃食物&#xff0c;身体加长&#xff0c;其次可以按下-&#xff08;键盘上右分大小写的-&#xff0c;不是数字的-&#xff09;来改变speed&#xff0c;终端可以看到速度&#xff0c;后续将陆续实现撞墙死亡&#xff0…

你丢失的数据,10款数据恢复软件帮你找!!

现实与虚拟的交错&#xff0c;互联网的进步&#xff0c;加大了我们之间交流的效率&#xff0c;而且便便捷了许许多多的事&#xff0c;比如信息保存&#xff1b;今天咱们来聊聊数据恢复这个话题。你是不是会一不小心删除了重要文件&#xff1f;硬盘出了问题&#xff0c;数据不见…

ArcGIS005:ArcMap常用操作101-150例动图演示

摘要&#xff1a;本文涵盖了GIS软件操作的多方面内容&#xff0c;包括地图文档的新建、打开、保存及版本兼容性处理&#xff1b;错误与警告的查阅及帮助文档的使用技巧&#xff1b;地图打印比例尺的调整与地图信息的完善&#xff1b;图层操作的撤销与恢复&#xff0c;界面元素的…

算法【Java】—— 动态规划之斐波那契数列模型

动态规划 动态规划的思路一共有五个步骤&#xff1a; 状态表示&#xff1a;由经验和题目要求得出&#xff0c;这个确实有点抽象&#xff0c;下面的题目会带大家慢慢感受状态标识状态转移方程初始化&#xff1a;避免越界访问 dp 表&#xff0c;所以在进行填表之前我们要预先填…

【学习】软件测试中的过程管理为何如此重要

在软件世界的繁华盛景之中&#xff0c;无数代码编织成了璀璨的星空&#xff0c;而每一颗闪烁的星点背后&#xff0c;都离不开精心的过程管理来确保其光华不减。正如一座摩天大楼需要稳固的地基与精细的设计图一样&#xff0c;软件的成功问世同样依赖于严谨、系统的流程管控。本…

深入学习 Scrapy 框架:从入门到精通的全面指南

深入学习 Scrapy 框架&#xff1a;从入门到精通的全面指南 引言 在数据驱动的时代&#xff0c;网络爬虫成为了获取信息的重要工具。Scrapy 是一个强大的 Python 爬虫框架&#xff0c;专为快速高效地提取网页数据而设计。本文将深入探讨 Scrapy 的使用&#xff0c;从基础知识到…

【Python】【数据可视化】【商务智能方法与应用】课程 作业一 飞桨AI Studio

作业说明 程序运行和题目图形相同可得90分&#xff0c;图形显示有所变化&#xff0c;美观清晰可适当加分。 import matplotlib.pyplot as plt import numpy as npx np.linspace(0, 1, 100) y1 x**2 y2 x**4plt.figure(figsize(8, 6))# yx^2 plt.plot(x, y1, -., labelyx^2,…

Postgresql源码(137)执行器参数传递与使用

参考 《Postgresql源码&#xff08;127&#xff09;投影ExecProject的表达式执行分析》 0 总结速查 prepare p_04(int,int) as select b from tbl_01 where a $1 and b $2为例。 custom计划中&#xff0c;在表达式计算中使用参数的值&#xff0c;因为custom计划会带参数值&…

自适应对话式团队构建,提升语言模型代理的复杂任务解决能力

人工智能咨询培训老师叶梓 转载标明出处 如何有效利用多个大模型&#xff08;LLM&#xff09;代理解决复杂任务一直是一个研究热点。由美国南加州大学、宾夕法尼亚州立大学、华盛顿大学、早稻田大学和谷歌DeepMind的研究人员联合提出了一种新的解决方案——自适应团队构建&…

GitHub上传自己的项目

目录 一、安装Git插件 1&#xff09;下载 2&#xff09;安装 二、创建Gothub的创库 三、通过Git上传本地文件到Github 四、其他 1、部分指令 2、如果已经运行过git init并设置了[user]&#xff0c;下次可以直接用 一、安装Git插件 1&#xff09;下载 下载地址&#x…

SpringBoot整合EasyExcel加Vue

EasyExcel好处是什么? EasyExcel 是一个基于 Apache POI 的 Java Excel 处理库&#xff0c;主要用于高效地读写 Excel 文件。它的主要好处包括&#xff1a; 高性能&#xff1a;EasyExcel 在内存管理和读取速度上进行了优化&#xff0c;适合处理大规模 Excel 文件。 简洁易用…

VisionPro —— CogPatInspectTool对比工具

一、CogPathInspectTool工具简介 CogPathInspectTool是VisionPro重要的工具&#xff0c;主要用于缺陷检测&#xff0c;通过将当前图像与“训练图像”对比&#xff0c;获取“原始差异图像”&#xff0c;再将“原始差异图像”与“阈值图像”进行对比&#xff0c;进而获取“阈值差…

css实现antd丝带效果

先上效果图&#xff1a; 代码&#xff1a; <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>Document…

BFV/BGV全同态加密方案浅析

本文主要为翻译内容&#xff0c;原文地址&#xff1a;Introduction to the BFV encryption scheme、https://www.inferati.com/blog/fhe-schemes-bgv 之前的一篇博客我们翻译了CKKS全同态加密方案的内容&#xff0c;但该篇上下文中有一些知识要点&#xff0c;作者在BFV/BGV中已…

占地1.1万平,2亿投资的智能仓储系统:高架库、AGV、码垛机器人……

导语 大家好&#xff0c;我是社长&#xff0c;老K。专注分享智能制造和智能仓储物流等内容。 我国调味料市场近年来展现出惊人的增长潜力&#xff0c;各大品牌纷纷加大投入&#xff0c;力求在竞争中脱颖而出。 广东美味鲜调味食品有限公司&#xff0c;作为行业内的佼佼者&#…

EJEAS S2滑雪对讲机全球发布会圆满举办,为滑雪市场注入新活力

时光向新&#xff0c;步履向前。站在冰雪运动与科技创新的交汇点&#xff0c;深圳爱骑仕智能科技有限公司&#xff08;以下简称“EJEAS”&#xff09;于2024年11月2日在新疆阿勒泰可可托海成功举办S2滑雪对讲机全球发布会。现场汇聚了来自全国各地的两三百名嘉宾&#xff0c;包…

个人对Numpy中transpose()函数的理解

NumPy中的transpose()函数用于对数组进行转置&#xff1a; 如果函数中不传递任何参数&#xff0c;它将进行标准的矩阵转置&#xff1b; 如果传递了一个轴序列&#xff0c;NumPy将按照这个序列重新排列轴。 二维的转置很好理解&#xff0c;就是线性代数中的矩阵转置。但高纬度…

【运动的&足球】足球运动员球守门员裁判检测系统源码&数据集全套:改进yolo11-DBBNCSPELAN

改进yolo11-FocalModulation等200全套创新点大全&#xff1a;足球运动员球守门员裁判检测系统源码&#xff06;数据集全套 1.图片效果展示 项目来源 人工智能促进会 2024.10.28 注意&#xff1a;由于项目一直在更新迭代&#xff0c;上面“1.图片效果展示”和“2.视频效果展示…