资讯专栏INFORMATION COLUMN

【数据结构初阶】第八篇——二叉树的链式结构(二叉树的前、中和后序遍历+层序遍历+链式结构的实现+相关

BigNerdCoding / 704人阅读

摘要:代码实现如下二叉树的创建与销毁二叉树的创建问题通过前序遍历的数组给定一串字符串,代表的是空树,其他的都是节点。

⭐️本篇博客我要来和大家一起聊一聊数据结构中的二叉树的链式结构的实现及相关的一些问题的介绍
⭐️博客代码已上传至gitee:https://gitee.com/byte-binxin/data-structure/commit/de7024a7498be71a78c18d22b7a7caee53f3ffb4


?二叉树的链式结构

前一篇博客介绍了二叉树的顺序结构,是通数组来存储的,这里我们通过创建链式结构来存储,在堆上申请空间,结构如下:

typedef char BTDataType;typedef struct BinaryTreeNode{	BTDataType data;	struct BinaryTreeNode* left;	struct BinaryTreeNode* right;}BTNode;

?二叉树的简单创建

这里我们用最粗暴的方法创建一棵树,就是一个节点一个节点的创建,实现代码如下:

BTNode* CreatBinaryTree(){    BTNode* treeNode1 = (BTNode*)malloc(sizeof(BTNode));	BTNode* treeNode2 = (BTNode*)malloc(sizeof(BTNode));	BTNode* treeNode3 = (BTNode*)malloc(sizeof(BTNode));	BTNode* treeNode4 = (BTNode*)malloc(sizeof(BTNode));	BTNode* treeNode5 = (BTNode*)malloc(sizeof(BTNode));	BTNode* treeNode6 = (BTNode*)malloc(sizeof(BTNode));	treeNode1->data = "A";	treeNode2->data = "B";	treeNode3->data = "C";	treeNode4->data = "D";	treeNode5->data = "E";	treeNode6->data = "F";	treeNode1->left = treeNode2;	treeNode1->right = treeNode3;	treeNode2->left = treeNode4;	treeNode2->right = treeNode5;	treeNode3->left = treeNode6;	treeNode3->right = NULL;	treeNode4->left = treeNode4->right = NULL;	treeNode5->left = treeNode5->right = NULL;	treeNode6->left = treeNode6->right = NULL;}

如下图:

?二叉树的遍历

?前序遍历(递归实现)

?这里我先给大家介绍一下用递归实现,后面我会给大家介绍如何用栈模拟实现非递归。
?前序遍历指的是先遍历根,再遍历左子树,再遍历右子树。
?思想: 二叉树本身就是一种递归结构,所以通过递归来遍历这棵树,如何递归遍历呢?
是这样的,先遍历根,再遍历左子树,左子树又可以分解为,根、左子树和右子树,直到把所以左子树的部分遍历完,然后就遍历右子树,右子树又可以分解为,根、左子树和右子树
假如我们构建了一个PrevOrder,这个函数是可以实现前序遍历的,所以我们先遍历根,剩下的左子树和右子树遍历就交给这个函数去实现。
递归就是把一个大的问题一直分解,直到分解为最后一个小问题来解决,这就是所谓的大事化小

了解了上面那些,我们就来看一下代码是如何实现的,

void BinaryTreePrevOrder(BTNode* root){    // 遍历到NULL就返回	if (root == NULL)	{		printf("NULL ");		return;	}  	// 先遍历根	printf("%c ", root->data);	// 左子树交给BinaryTreePrevOrder这个函数去遍历	BinaryTreePrevOrder(root->left);	// 右子树交给BinaryTreePrevOrder这个函数去遍历	BinaryTreePrevOrder(root->right);}

下面我们来看一下代码运行结果:

?中序遍历(递归实现)

?中序遍历指的是先遍历左子树,再遍历根,再遍历右子树。
?思想: 二叉树本身就是一种递归结构,所以通过递归来遍历这棵树,如何递归遍历呢?
是这样的,先遍历左子树,左子树又可以分解为,左子树、根和右子树,直到把所以左子树的部分遍历完,然后就遍历根,再遍历右子树,右子树又可以分解为,左子树、根和右子树
如下图:

代码实现如下:

void BinaryTreeInOrder(BTNode* root){	// 遍历到NULL就返回	if (root == NULL)	{		printf("NULL ");		return;	}	// 左子树交给BinaryTreePrevOrder这个函数去遍历	BinaryTreeInOrder(root->left);	// 遍历根	printf("%c ", root->data);	// 右子树交给BinaryTreePrevOrder这个函数去遍历	BinaryTreeInOrder(root->right);}

代码运行结果如下:

?后序遍历(递归实现)

?中序遍历指的是先遍历左子树,再遍历根,再遍历右子树。
?思想: 二叉树本身就是一种递归结构,所以通过递归来遍历这棵树,如何递归遍历呢?
是这样的,先遍历左子树,左子树又可以分解为,左子树、右子树和根,直到把所以左子树的部分遍历完,然后遍历右子树,右子树又可以分解为,左子树、右子树和根,最后遍历根。
如下图:

代码实现如下:

void BinaryTreePostOrder(BTNode* root){	if (root == NULL)	{		printf("NULL ");		return;	}	// 左子树交给BinaryTreePrevOrder这个函数去遍历	BinaryTreePostOrder(root->left);	// 右子树交给BinaryTreePrevOrder这个函数去遍历	BinaryTreePostOrder(root->right);	//遍历根	printf("%c ", root->data);}

代码运行结果如下:

?层序遍历

? 层序遍历: 设二叉树的根节点所在层数为1,层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树根节点,然后从左到右访问第2层上的节点,接着是第三层的节点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历。

层序遍历用到的是队列来解决,先将根入队,然后把根取出,取出的同时分别再把不为空左节点右节点入队,直到队列为空时就说明二叉树已经遍历完了。为了方便大家理解我在这里做了个动图演示一下:

再看一下代码实现如下:

void BinaryTreeLevelOrder(BTNode* root){	if (root == NULL)	{		printf("NULL");		return;	}	queue<BTNode*>q;	q.push(root);	while (!q.empty())	{		BTNode* front = q.front();		q.pop();		printf("%c ", front->data);		if (front->left)			q.push(front->left);		if (front->right)			q.push(front->right);	}}

代码运行结果如下:

?二叉树的节点个数和高度

?二叉树的节点个数

?此问题可以分解为求左子树节点个数+右子树节点个数+1,然后左子树节点个数又可以继续分,所以这里可以用递归来求解这个问题,下面我们就来实现一下这个接口

代码如下:

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

代码运行结果如下:

?二叉树的叶子节点个数

❄️问题可以分解为求左子树叶子节点个数+右子树叶子节点个数,也是一个递归的问题,这里就直接实现了。

代码如下:

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层节点个数

☔️求解第k层节点个数其实就是求解左子树的第k-1层节点个数+右子树的第k-1层节点个数,当k==1时,就可以直接返回1,节点为空就返回0。

代码实现如下:

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

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

?这里我们只需要前序遍历一遍二叉树即可,直到找到x就返回。

代码实现如下:

BTNode* BinaryTreeFind(BTNode* root, BTDataType x){	if (root == NULL)		return NULL;	if (root->data == x)		return root;	BTNode* leftRet = BinaryTreeFind(root->left, x);	if (leftRet)		return leftRet;	BTNode* rightRet = BinaryTreeFind(root->right, x);	if (rightRet)		return rightRet;}

?二叉树的创建与销毁

?二叉树的创建

?问题: 通过前序遍历的数组"ABD##E#H##CF##G##"
给定一串字符串,#代表的是空树,其他的都是节点。
这里我们只需要前序遍历这串字符串来构建这棵树即可。
同样是用递归来解决这个问题
treeNode->left = BinaryTreeCreate(s, pi); 让当前这个节点的左指向给递归构建左子树
**treeNode->right = BinaryTreeCreate(s, pi);**让当前这个节点的右指向给递归构建左子树
如果当前节点为空就直接返回NULL

代码实现如下:

BTNode* BinaryTreeCreate(BTDataType* s, int* pi){	if (s[*pi] == "#")	{		(*pi)++;		return NULL;	}	BTNode* treeNode = (BTNode*)malloc(sizeof(BTNode));	treeNode->data = s[(*pi)++];	treeNode->left = BinaryTreeCreate(s, pi);	treeNode->right = BinaryTreeCreate(s, pi);}	

?二叉树的销毁

?二叉树的销毁我们可以通过层序遍历来把节点逐个释放掉,由于与上面的层序遍历很相似,这里就不过多介绍了,直接上代码

void BinaryTreeDestory(BTNode** root){	if (*root == NULL)		return;	queue<BTNode*>q;	q.push(*root);	while (!q.empty())	{		BTNode* front = q.front();		q.pop();				if (front->left)			q.push(front->left);		if (front->right)			q.push(front->right);		free(front);		front = NULL;	}}

?总结

这篇博客就主要介绍了二叉树的链式结构及实现,还有一些相关的问题,二叉树有关的问题递归会用到比较多,因为二叉树本身就是由递归来创建的。今天就介绍到这,喜欢的话,欢迎点赞、支持和指正~

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/123727.html

相关文章

  • 数据结构初阶叉树】:叉树相关性质和经典习题(用C语言实现,附图详解)

    摘要:当集合为空时,称该二叉树为空二叉树。也就是说,如果一个二叉树的层数为,且结点总数是,则它就是满二叉树。完全二叉树完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。 ...

    Martin91 评论0 收藏0
  • LeetCode通关:连刷三十九道叉树,刷疯了!⭐四万字长文搞定叉树,建议收藏!⭐

    分门别类刷算法,坚持,进步! 刷题路线参考:https://github.com/youngyangyang04/leetcode-master 大家好,我是拿输出博客来督促自己刷题的老三,这一节我们来刷二叉树,二叉树相关题目在面试里非常高频,而且在力扣里数量很多,足足有几百道,不要慌,我们一步步来。我的文章很长,你们 收藏一下。 二叉树基础 二叉树是一种比较常见的数据结构,在开始刷二叉树...

    honhon 评论0 收藏0
  • 数据结构叉树(顺序结构+链式结构+堆排序+Topk问题)

    摘要:完全二叉树完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。链式存储二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。而完全二叉树更适合使用顺序结构存储。 目录 树概念及结构 树的概念 树的相关概念 树的表示 ​ 树在实际中的运用(表示文件系统的目...

    DoINsiSt 评论0 收藏0
  • 叉树链式结构

    摘要:文章目录前言二叉树的链式结构二叉树的遍历方式前序遍历中序遍历后序遍历二叉树前中后序遍历练习前序遍历练习中序遍历练习后序遍历练习利用前序遍历中序遍历结合二叉树其他操作二叉树结点个数二叉树叶子结点个数二叉树第层节点个 ...

    fantix 评论0 收藏0
  • js 中二叉深度遍历与广度遍历(递归实现与非递归实现)

    摘要:树中结点的最大层次称为树的深度或高度。二叉树有深度遍历和广度遍历,深度遍历有前序中序和后序三种遍历方法。二叉树的前序遍历可以用来显示目录结构等中序遍历可以实现表达式树,在编译器底层很有用后序遍历可以用来实现计算目录内的文件及其信息等。 树的简介 栈、队列、链表等数据结构,都是顺序数据结构。而树是非顺序数据结构。树型结构是一类非常重要的非线性结构。直观地,树型结构是以分支关系定义的层次结...

    Yuanf 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<