链式二叉树及相关操作(前,中,后,层序遍历)

这篇具有很好参考价值的文章主要介绍了链式二叉树及相关操作(前,中,后,层序遍历)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

欢迎来到 Claffic 的博客 💞💞💞

链式二叉树及相关操作(前,中,后,层序遍历)

“春来无事,只为花忙。”

前言:

上一期给大家介绍了二叉树的一种顺序结构:堆,这一期承接上一期,给大家继续介绍二叉树的另一种结构:链式结构。


目录

🐽Part1:链式二叉树? 

1.前情提要 

2.创建一颗二叉树

🐷Part2:相关操作实现

1.遍历操作

1.1前序遍历

1.2中序遍历

1.3后序遍历

1.4层序遍历

2.其他操作

2.1二叉树结点个数

2.2二叉树高度

2.3第k层结点个数 

2.4判断是否为完全二叉树

2.5查找为x的结点

2.6二叉树销毁 


Part1:链式二叉树? 

1.前情提要 

这里的链式二叉树其实就是利用每个结点的左孩子和右孩子关系来创建的,方便快速手搓一个简单的二叉树。

2.创建一颗二叉树

其实方法很简单:

确定结点的结构 --> 根据左右孩子关系链接

//结点的结构
typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;
//新结点的创建
BTNode* BuyNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->data = x;
	newnode->left = NULL;
	newnode->right = NULL;

	return newnode;
}

//链接
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;
}

到这里,这颗二叉树的样子就有了:

链式二叉树及相关操作(前,中,后,层序遍历)

Part2:相关操作实现

1.遍历操作

遍历可以清晰的明确二叉树的结构。

二叉树的遍历是按照某种特定的规则,依次对二叉树中的结点进行相应的操作,并且每个结点只操作一次。 

按照规则,二叉树的遍历(按访问顺序)有: 

前序遍历:根节点-->左节点-->右结点;
中序遍历:左节点-->根节点-->右结点;

后序遍历:左节点-->右结点-->根节点;

层序遍历:简单说,就是二叉树由上到下,由左到右遍历。

1.1前序遍历

由于每次遍历都是 根节点-->左节点-->右结点,所以非常适合用递归来实现遍历。

链式二叉树及相关操作(前,中,后,层序遍历)

前序遍历图解

面对二叉树遍历,既要看到大树,又能看到小树; 

可以看出,首先由顶部根节点进入,再递归左边,遇到空结点返回,再递归右结点... ...依次反复

那么就可以上代码了:

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

为了更详细的理解,这里画一下代码的递归图解:

链式二叉树及相关操作(前,中,后,层序遍历)代码递归图解 

学会了前序遍历,剩余的中序遍历和后序遍历也就会了,它们之间只有访问结点的顺序不同。

1.2中序遍历

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

1.3后序遍历

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

1.4层序遍历

层序遍历与前三种遍历不同;

这里直接上演示图吧:

链式二叉树及相关操作(前,中,后,层序遍历)简单解释: 

双亲结点弹出,两个孩子节点就入 队列

是的,这里用到了队列 先入先出 的特点。

上代码: 

// 层序遍历
void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);

	if (root)
		QueuePush(&q,root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%d ", front->data);
		if (front->left)
			QueuePush(&q, front->left);

		if (front->right)
			QueuePush(&q, front->right);
	}

	QueueDestroy(&q);
}

2.其他操作

2.1二叉树结点个数

这里利用了分治思想,

即让每个根节点去统计孩子结点个数,再依次向上汇报;

还是利用递归:

// 二叉树节点个数  分治思想
int BinaryTreeSize(BTNode* root)
{
	return root == NULL ? 0 :
				   BinaryTreeSize(root->left)
				   + BinaryTreeSize(root->right)
				   + 1; // +1是自己
}

2.2二叉树高度

二叉树的高度,是取左子树和右子树高度中最大者,

所以可以先利用递归分别保存左右子树的高度,再返回较大值:

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

2.3第k层结点个数 

同样的,第k层结点个数包含左子树结点个数与右子树结点个数:

//第k层节点个数
int BinaryTreeKLevel(BTNode* root, int k)
{
	assert(k > 0);

	if (root == NULL)
		return 0;
	if (k == 1) // 顶部根节点的特殊情况
		return 1;
	return BinaryTreeKLevel(root->left, k - 1) 
		+ BinaryTreeKLevel(root->right, k - 1);
}

2.4判断是否为完全二叉树

还记得完全二叉树吗?

它的特点是 空结点连续 ,我们就可以利用这一个特点来判断;

判断一层连不连续,正好用到前面的层序遍历思想,利用 队列 来实现:

// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);

	if (root)
		QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		if (front == NULL)
		{
			break;
		}
		else
		{
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
		}
	}
	//判断
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		if (front)
		{
			QueueDestroy(&q);
			return false;
		}
	}

	QueueDestroy(&q);
	return true;
}

2.5查找为x的结点

分左右结点来查找,若有多个满足条件的结点,返回先找到的结点指针:

//查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;
	BTNode* lret = BinaryTreeFind(root->left, x);
	if (lret)
		return lret;
	BTNode* rret = BinaryTreeFind(root->right, x);
	if (rret)
		return rret;

	return NULL;
}

2.6二叉树销毁 

这个销毁也是要逐个销毁的,也要用到递归,分左子树销毁和右子树销毁:

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

代码已上传至 我的gitee

拿走不谢~ 


总结:

链式二叉树的实现~ 主要掌握四种遍历:前中后序遍历层序遍历,尽量搞懂是如何递归的,才会有更深刻的记忆~

码文不易 

如果你觉得这篇文章还不错并且对你有帮助,不妨支持一波哦  💗💗💗文章来源地址https://www.toymoban.com/news/detail-415042.html

到了这里,关于链式二叉树及相关操作(前,中,后,层序遍历)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 按照前序遍历创建二叉树及树的四种遍历方式

    一.二叉树的介绍         二叉树的特点是二叉树的每个结点的度都不大于2,可以视为每个结点都有左孩子和右孩子。故二叉树结点的数据结构为   二.二叉树的特点     1.设根结点所在的层数为第1层,则第i层最多有个结点。     2.深度为k的二叉树最多有个结点。    

    2024年02月04日
    浏览(38)
  • 数据结构(C语言实现)——二叉树的概念及二叉树顺序结构和链式结构的实现(堆排序+TOP-K问题+链式二叉树相关操作)

    前面学习了数据结构中线性结构的几种结构,顺序表,链表,栈和队列等,今天我们来学习一种非线性的数据结构——树。由于二叉树是数据结构中的一个重点和难点,所以本文着重介绍二叉树的相关概念和性质,以及二叉树的应用。 树是一种非线性的数据结构,它是由n(

    2023年04月21日
    浏览(45)
  • 二叉树层序遍历

    目录 一、什么是层序遍历 二、层序遍历的实现 三、判断一棵树是否为完全二叉树 总结: 学习二叉树结构,最简单的就是遍历。 所谓二叉树遍历就是按照某种规则对二叉树中的节点进行相应操作,每个节点值操作一次。 遍历是二叉树的重要运算之一,也是二叉树进行其它运

    2024年02月13日
    浏览(38)
  • 二叉树题目:二叉树的层序遍历 II

    标题:二叉树的层序遍历 II 出处:107. 二叉树的层序遍历 II 4 级 要求 给你二叉树的根结点 root texttt{root} root ,返回其结点值自底向上的层序遍历(即从左到右,按从叶结点所在层到根结点所在层逐层遍历)。 示例 示例 1: 输入: root   =   [3,9,20,null,null,15,7] texttt{root = [3

    2024年02月11日
    浏览(37)
  • day15 层序遍历 翻转二叉树 对称二叉树

    题目链接:102 二叉树的层序遍历 题意 根据二叉树的根节点root,返回其节点值的层序遍历 借助队列实现,因为队列是先进先出的逻辑,符合层序遍历一层一层遍历的思想 代码 题目链接:226 翻转二叉树 题意 根据二叉树的根节点root,翻转二叉树,将节点是左右孩子进行翻转

    2024年01月22日
    浏览(48)
  • ★102. 二叉树的层序遍历

    很巧妙的,又学习了一种层次遍历的方法, 就是说根据当前的队列的长度去遍历,遍历的当前队列的长度就是该层次的节点个数。

    2024年02月05日
    浏览(45)
  • Java层序遍历二叉树

    二叉树准备: 力扣

    2024年01月23日
    浏览(33)
  • 41 二叉树的层序遍历

    给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。 提示: 树中节点数目在范围 [0, 2000] 内 -1000 = Node.val = 1000

    2024年02月07日
    浏览(47)
  • DS:树及二叉树的相关概念

                                                     创作不易,兄弟们来波三连吧!!            树是一种非线性的数据结构,它是由n(n=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。

    2024年03月13日
    浏览(67)
  • LeetCode 0103.二叉树的锯齿形层序遍历:层序遍历 + 适时翻转

    力扣题目链接:https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/ 给你二叉树的根节点 root ,返回其节点值的 锯齿形层序遍历 。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。   示例 1: 示例 2: 示例 3:   提示: 树中节点数目在范

    2024年02月20日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包