【数据结构】二叉树链式结构的实现（三）

2023-09-13 10:59:37

目录

一，二叉树的链式结构

二，二叉链的接口实现

        1，二叉链的创建

        2，接口函数

        3，动态创立新结点

        4，创建二叉树

        5，前序遍历

        6，中序遍历

        7，后序遍历

三，结点个数以及高度等

        1，接口函数

        2，结点个数

        3，叶子结点个数

        4，二叉树高度

        5，二叉树第k层结点个数

        6，二叉树查找值为x的结点

一，二叉树的链式结构

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系；

通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。

链式结构又分为二叉链和三叉链，这里我们学习二叉链；

 二叉树是：

1，空树

2，非空：根节点，根节点的左子树、根节点的右子树组成的。

从图示中可以看出，二叉树定义是递归式的也称递归树，因此后序基本操作中基本都是按照该概念实现的；

 二叉链结构图示；

二，二叉链的接口实现

        1，二叉链的创建

typedef int BTDataType;
//二叉链
typedef struct BinaryTreeNode
{
	BTDataType data; // 当前结点值域	
	struct BinaryTreeNode* left; // 指向当前结点左孩子
	struct BinaryTreeNode* right; // 指向当前结点右孩子
}BTNode;

首先创建一个结构体表示二叉链，data是当前结点的值域，BTDataType是储存的值的数据类型；

left是指向当前结点左孩子，right是指向当前结点右孩子；

这里的BTDataType是int的重命名，也可以说是数据类型的重命名，这样统一化方便后续更改；

        2，接口函数

//动态创立新结点
BTNode* BuyNode(BTDataType x);
//创建二叉树
BTNode* GreatBTree();
//前序遍历
void PrevOrder(BTNode* root);
//中序遍历
void InOrder(BTNode* root);
//后序遍历
void PostOrder(BTNode* root);

这是以上要实现的接口函数；

        3，动态创立新结点

//动态创立新结点
BTNode* BuyNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	assert(newnode);
	newnode->data = x;
	newnode->left = NULL;
	newnode->right = NULL;
	return newnode;
}

后面创立新结点时直接调用此函数，一定要向堆区申请空间，这样函数结束空间会保留不会被回收；

将data赋新值，left与right都指向空，再返回结点指针即可；

        4，创建二叉树

//创建二叉树
BTNode* GreatBTree()
{
	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;
}

然后我们申请结点来构造二叉树，通过链接将新结点链接起来；

创建的二叉树结构图示如下：

        5，前序遍历

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

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

二叉树的前序，中序，后续遍历都是同一种思路：

1. 前序遍历(Preorder Traversal 亦称先序遍历)——根结点---->左子树--->右子树

2. 中序遍历(Inorder Traversal)——左子树--->根结点--->右子树

3. 后序遍历(Postorder Traversal)——左子树--->右子树--->根结点

这里要用到递归思想：这里NULL用N表示，建议画图来理解，一层一层遍历下去；

前序遍历：

先访问根结点（1）然后访问其左子树（2）；打印 1

此时根结点为（2）然后访问其左子树（3）；打印1 2

此时根结点为（3）然后访问其左子树（NULL）；打印1 2 3

此时根结点为（NULL）return NULL到（3），然后访问（3）的右子树（NULL）；打印1 2 3 N

此时根结点为（NULL）return NULL到（3），此时对（3）也就是对（2）的左子树的访问结束了，然后访问（2）的右子树（NULL)；打印1 2 3 N N

此时根结点为（NULL）return NULL到（2），此时对（2）也就是对（1）的左子树访问结束了，然后访问（1）的右子树（4）；打印1 2 3 N N N

此时根结点为（4）然后访问其左子树（5）；打印1 2 3 N N N 4

此时根结点为（5）然后访问其左子树（NULL）；打印1 2 3 N N N 4 5

此时根结点为（NULL）return NULL到（5）然后访问（5）的右子树（NULL）；打印1 2 3 N N N 4 5 N

此时根结点为（NULL）return NULL到（5）此时对（5）也就是对（4）的左子树的访问结束了，然后访问（4）的右子树（6）；打印 1 2 3 N N N 4 5 N N

此时根结点为（6）然后访问其左子树（NULL）；打印1 2 3 N N N 4 5 N N 6

此时根结点为（NULL）return NULL到（6）然后访问（6）的右子树（NULL）；打印1 2 3 N N N 4 5 N N 6 N

此时根结点为（NULL）return NULL到（6），此时对（6）也就是对（4）的右子树的访问结束了，此时对（4）也就是对（1）的右子树的访问结束了，此时对（1）的访问也结束了，前序遍历也就结束了；打印1 2 3 N N N 4 5 N N 6 N N

图解思路示例：

    

BTNode* root = GreatBTree();
//前序遍历
PrevOrder(root);

这就是前序遍历；

        6，中序遍历

//中序遍历
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

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

中序遍历：左子树--->根结点--->右子树

跟前序遍历思路一致，就是换了一下访问的顺序，按照前序遍历的思路来就完事了；

//中序遍历
InOrder(root);
printf("\n");

        7，后序遍历

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

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

后序遍历：左子树--->右子树--->根结点

思路还是一致的，就是换了一下访问顺序，前，中，后序遍历的思路都是一致的，只要搞清楚其中一个就全部拿捏了；

//后续遍历
PostOrder(root);
printf("\n");

 这里对二叉链的基础遍历就实现完全了，有人说还有一个层序遍历，这个遍历需要用到队列，目前C语言阶段实现太过于繁琐，后序博主会补上；

三，结点个数以及高度等

像此类问题也都是递归问题，更加看重我们对函数栈帧的理解；

        1，接口函数

//结点个数
int	SumNode(BTNode* root);
//叶子结点个数
int LeafNode(BTNode* root);
//二叉树高度
int HeightTree(BTNode* root);
//二叉树第k层结点个数
int BTreeLeveSize(BTNode* root, int k);
//二叉树查找值为x的结点
BTNode* BTreeFine(BTNode* root, int x);

以上是要实现的函数；

        2，结点个数

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

递归其实说难也难，说不难也不难，是有技巧在里面的；

1，大事化小：根结点为（1）的二叉树的结点总和==>左子树（2）的结点总和加上右子树（4）的结点总和再加上本身的结点个数1，然后根结点为（2）的结点总和==>左子树（3）的总和加上NULL加1，这就是规律；【（1）=（2）+（4）+1 】

2，结束条件，当结点为NULL时返回0；

//结点个数
printf("%d\n", SumNode(root));

        3，叶子结点个数

//叶子结点个数
int LeafNode(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left==NULL && root->right==NULL)
	{
		return 1;
	}
	else
	{
		return LeafNode(root->left) + LeafNode(root->right);
	}
}

 

大事化小：求根结点为（1）的二叉树的叶子节点的个数==>其左子树（2）加上其右子树（4）的叶子节点的个数；【（1）=（2）+（4）】

结束条件：当结点为NULL时返回0，当结点的左右子树都为NULL时返回1；

        4，二叉树高度

//二叉树高度
int HeightTree(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int left = HeightTree(root->left);
	int right = HeightTree(root->right);
	return left > right ? left + 1 : right + 1;
}

大事化小：求根结点为（1）的二叉树的高度==>其左子树（2）与右子树（4）中高的一颗的高度加上本身的高度1；【（1）=（2）>（4）？（2）+1：（4）+1 】

结束条件：当结点为NULL时返回0；

//二叉树高度
printf("%d\n", HeightTree(root));

        5，二叉树第k层结点个数

//二叉树第k层结点个数
int BTreeLeveSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BTreeLeveSize(root->left, k - 1)  + BTreeLeveSize(root->right, k - 1);
}

大事化小：求根结点为（1）的二叉树第K层的结点个数==>其左子树（2）加上右子树（4）中第K-1层结点的个数；【（1）=（2）+（4）】

结束条件：当结点为NULL时返回0，当K等于1时返回1；

//二叉树第k层结点个数
printf("%d\n", BTreeLeveSize(root,3));

        6，二叉树查找值为x的结点

//二叉树查找值为x的结点
BTNode* BTreeFine(BTNode* root, int x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	if (BTreeFine(root->left, x) == NULL)
	{
		return BTreeFine(root->right, x);
	}
	else
	{
		return BTreeFine(root->left, x);
	}
}

大事化小：查找根结点为（1）的二叉树中值为x的结点==>查找其左子树（2）与右子树（4）中值为x的结点；

结束条件：当结点为NULL时返回NULL，当结点的值为x时返回该结点；

思路：所以当其中一个子树不为NULL时就是所求的结点，如果左子树不为空则返回左子树的结点，否则返回右子树的结点，如果左右都为空那也返回右子树的结点；

//二叉树查找值为x的结点
BTNode* ret = BTreeFine(root, 6);
printf("%d\n", ret->data);

ret = BTreeFine(root, 3);
printf("%d\n", ret->data);

到这里就结束了，通过这些题目也充分的认识了二叉树（递归树），这就是递归算法，还是要多画图来理解，递归基层的知识就是函数栈帧的创建与销毁；

第三阶段就到这里了，这阶段带大家了解一下二叉树（递归树）的递归思想；

后面博主会陆续更新；

如有不足之处欢迎来补充交流！

完结。。

更多推荐

PMP考试备考：两个月时间足够吗？

PMP（ProjectManagementProfessional）认证是全球范围内最受认可的项目管理专业资格之一。对于想要提升项目管理技能和职业发展的人来说，PMP认证是一个重要的里程碑。然而，很多人担心备考时间不足以充分准备PMP考试。那么，两个月的备考时间足够吗？答案并不是简单的肯定或否定。两个月的备考时间对于P

Bigemap如何添加mapbox图源？

会使用到的工具bigemapgisoffice，下载链接：BIGEMAPGISOffice-全能版打开软件，要提示需要授权和添加地图，然后去点击选择地图这个按钮，列表中有个添加按钮点进去选择添加地图的方式。第一种方式：通过地图配置文件批量解析添加地图第二种方式：通过以下在线地图的网址输入添加。mapbox:https:

爆款产品的秘诀：海外网红营销策略

近年来，随着社交媒体的兴起和全球互联网的普及，海外网红营销已成为一种极具影响力的市场推广方式。通过与知名网红合作，企业可以迅速将其产品或服务推向国际市场，实现爆款产品的目标。本文Nox聚星将和大家深入探讨海外网红营销打造爆款产品的原理，以及如何通过这一策略来创造成功的爆款产品。1、网红的选择要打造爆款产品，首先要选择合

ai智能生成文章-智能生成文章软件

您是否曾为创作内容而感到头疼不已？是否一直在寻找一种能够帮助您轻松生成高质量文章的解决方案？什么是AI智能生成文章，特别是147SEO智能原创文章生成。这是一种先进的技术，利用人工智能和自然语言处理，能够自动生成各种类型的文章。这包括了新闻报道、博客文章、产品描述、营销内容等等。这项技术的妙处在于，它可以帮助您在几分钟

python抠图（去水印）开源库lama-cleaner入门应用实践

1.关于LamaCleanerLamaCleaner是由SOTAAI模型提供支持的免费开源图像修复工具。可以从图片中移除任何不需要的物体、缺陷和人，或者擦除并替换（poweredbystablediffusion）图片上的任何东西。特征：完全免费开源，完全自托管，支持CPU&GPU&M1/2Windows一键安装程序本

六、决策树算法(DT，DecisionTreeClassifier)（有监督学习）

决策树（DT）是一种用于分类和回归的非参数监督学习方法。其目标是创建一个模型，通过学习从数据特征中推断出的简单决策规则来预测目标变量的值。一棵树可以看作是一个片断常数近似值。一、算法思路具体可参考博文：七、决策树算法和集成算法基尼系数Gini：衡量选择标准的不确定程度；说白了，就是越不确定Gini系数越高需要选择最小的

CentOS7 防火墙（firewall）的操作命令

安装：yuminstallfirewalld1、firewalld的基本使用启动：systemctlstartfirewalld查看状态：systemctlstatusfirewalld禁用，禁止开机启动：systemctldisablefirewalld停止运行：systemctlstopfirewalld2.配置f

FasterTransformer在linux系统中的安装教程（ubuntu系统）

参考资料官方文档安装过程在官方文档中，其对安装流程已经表述的比较详细，主要是安装nvidia-docker和安装编译FasterTransformer。其中难点主要是在安装nvidia-docker上。当然其实也可以不安装nvidia-docker，直接使用配置好的cuda环境配置，但是这样的话我们就无法使用docke

Python运算符、函数与模块和程序控制结构

给我家憨憨写的python教程——雁丘Python运算符、函数与模块和程序控制结构关于本专栏一运算符1.1位运算符1.1.1按位取反1.1.2按位与1.1.3按位或1.1.4按位异或1.1.5左移位1.2关系运算符1.3运算顺序1.4运算方向二函数与模块2.1内建函数2.2库函数2.2.1标准库函数2.2.3第三方库2

windows系统使用软件异地同步数据（灾备）

Syncthing是一个开源文件同步工具，可以在多台设备之间实时同步文件或文件夹，官方网站：Syncthing下载地址：Syncthing|Downloads，一般推荐下载图形界面SyncTrayzor。官方下载地址：https://github.com/canton7/SyncTrayzor/releases/dow

【python数据分析基础】—对列操作：获取DataFrame不同的类型columns

文章目录前言一、生成不同类型的列名1.获取数组类型的结果2.获取list类型的结果二、实际应用前言在DataFrame进行数据分析时，我们时常会想对DataFrame的所有列进行数据清洗操作，比如转换不同字段的数据类型，但如果DataFrame字段比较多，一列列数据引用进行数据处理显现效率比较低，使用DataFrame

热文推荐
  1. CFimagehost私人图床本地部署结合cpolar内网穿透实现公网访问

    文章目录1.前言2.CFImagehost网站搭建2.1CFImagehost下载和安装2.2CFImagehost网页测试2.3cpolar的安装和注册3.本地网页发布3.1Cpolar临时数据隧道3.2Cpolar稳定隧道（云端设置）3.3.Cpolar稳定隧道（本地设置）4.公网访问测试5.结语1.前言图片服务器

  2. STC单片机定时器0手动状态脉冲定时器2自动状态脉冲加减速控制

    /***定时器0中断运行函数判断电机运行为一启动输出***///ManuMTARUN_FLAG手动定时器电机A运行标志M_Speed//ManuMTBRUN_FLAG手动定时器电机B运行标志//a1=XAddSpeed;//X加速系数送缓冲器201845//b1=YAddSpeed;//Y加速系数送缓冲器201845v

  3. C++学习（1）

    一、C++概述（了解）C++在C语言的基础上添加了面向对象编程和泛型编程的支持二、helloword程序（掌握）#define_CET_SECURE_NO_WARNINGS//在开发软件visualstudio编译c文件时,visualstudio认为strcpy,scanf等函数不安全的导致报警告和错误，导致无法编译

  4. CPP-Templates-2nd--第十一章 泛型库

    目录11.1可调用对象（Callables）11.1.1函数对象的支持11.1.2处理成员函数以及额外的参数11.1.3函数调用的包装11.2其他一些实现泛型库的工具11.2.1类型萃取11.2.2std::addressoff()11.2.3std::declval()11.3完美转发临时变量11.4作为模板参数的引

  5. NK试剂盒使用注意事项及NK细胞培养攻略

    NK细胞自然杀伤细胞（Naturalkillercell，NK细胞)，是除T细胞、B细胞之外的第三大类淋巴细胞，不表达T细胞和B细胞所特有的膜表面分子。无需抗原的预先刺激与活化即可直接杀伤被病毒感染的自身细胞或肿瘤细胞，与抗肿瘤、抗感染和免疫调节有关，是固有免疫最重要的组成成分之一。NK细胞大概约占外周血淋巴细胞的10

  6. MongoDB性能分析

    mongostatmongostat是mongdb自带的状态检测工具，在命令行下使用。它会间隔固定时间获取mongodb的当前运行状态，并输出。如果你发现数据库突然变慢或者有其他问题的话，你第一手的操作就考虑采用mongostat来查看mongo的状态。它的输出有以下几列：inserts/s:每秒插入次数query/s

  7. nvm下载安装教程

    前言nvm官网地址：https://nvm.uihtm.com一、nvm下载进入nvmgithub地址，下载最新版本：https://github.com/coreybutler/nvm-windows/releases点击选择当前最新版本。滑动到底部，点击nvm-setup.exe下载安装文件。接受，下一步。选择nv

  8. 中国式现代化落地社区的“3510”模式示范点在烟台正式启动

    第一个中国式现代化落地社区（村居）、家庭和养老（托幼）的“3510”模式示范点——烟台市莱山区迎春佳苑智慧社区、智慧家庭、智慧养老综合服务中心于9月16日正式启动！山东省人大城环委原副主任委员尚龙江，淄博市卫健委原主任、二级巡视员宋晓东，烟台市民政局局长卢国栋，莱山区区委书记罗建，莱山区区长蒋海华，河北省山东商会副会长

  9. 使用postman做接口测试

    1.接口测试：针对软件对外提供服务的接口的输入输出进行测试，以及接口间相互逻辑的测试，验证接口功能与接口描述文档的一致性2.接口测试流程：1）获取接口信息：通过接口文档或抓包来获取接口的基本调用方式和返回，抓包可以通过fiddler、charles或者chrome的开发者工具等2）接口测试用例设计：根据获取到的接口信息