【数据结构】二叉树之链式结构

这篇具有很好参考价值的文章主要介绍了【数据结构】二叉树之链式结构。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【数据结构】二叉树之链式结构,数据结构,数据结构,算法
🔥博客主页 小羊失眠啦.
🎥系列专栏《C语言》 《数据结构》 《Linux》《Cpolar》
❤️感谢大家点赞👍收藏⭐评论✍️


【数据结构】二叉树之链式结构,数据结构,数据结构,算法

一、前置说明

在学习二叉树各种各样的操作前,我们先来回顾一下二叉树的概念:

二叉树是度不超过2的树,由根结点和左右2个子树组成,每个子树也可以看作一颗二叉树,又可以拆分为根结点和左右两颗子树…

【数据结构】二叉树之链式结构,数据结构,数据结构,算法

是不是很熟悉,一个大问题可以拆分为两个子问题,每个子问题又可以拆分为更小的子问题,这样层层拆分到不可拆分(遇到空树)的过程,不就是递归吗!因此,我们可以得出:

树是递归定义的,后续树的各种操作正是围绕着这一点进行的。

二、二叉树的遍历

我们先从最简单的操作----遍历学起。所谓二叉树遍历(Traversal)就是按照某种特定的规则,依次对二叉树中的结点进行相应的操作,并且每个节点有且只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一,也是二叉树上进行其它运算的基础。二叉树的遍历分为四种:前序遍历中序遍历后序遍历层序遍历

2.1 前序遍历

前序遍历(Preorder Traversal)又称先根遍历,即先遍历根结点,再遍历左子树,最后遍历右子树。而对于子树的遍历,也服从上述规则。利用递归,我们可以很快地写出代码:

//前序遍历
void PrevOrder(BTNode* root) {
	//遇到空树,递归终点
    if (root == NULL) {
		printf("NULL ");

		return;
	}
    //对根节点进行操作(此处为打印)
	printf("%d ", root->val);
    //递归遍历左子树
	PrevOrder(root->left);
    //递归遍历右子树
	PrevOrder(root->right);
}

为了更好地理解这个过程,我们可以画出递归展开图如下:

【数据结构】二叉树之链式结构,数据结构,数据结构,算法

2.2 中序遍历

中序遍历(Inorder Traversal)又称中根遍历,即先遍历左子树,再遍历根结点,最后遍历右子树。同样,子树的遍历规则也是如此。递归代码如下:

void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

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

2.3 后序遍历

后序遍历(Inorder Traversal)又称后根遍历,即先遍历左子树,再遍历右子树,最后遍历根结点。照葫芦画瓢,递归代码如下:

void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

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

2.4 层序遍历

除了上面的前中后序遍历,还可以对二叉树进行层序遍历。所谓层序遍历就是从所在二叉树的根节点出发,首先访问第1层的根节点,然后从左到右访问第2层上的节点,接着是第三层的节点,以此类推。这样自上而下,自左向右逐层访问树的结点的过程就是层序遍历。

【数据结构】二叉树之链式结构,数据结构,数据结构,算法

与前面三种遍历不同,层序遍历属于广度优先遍历,因此我们可以利用队列先进先出的特性,将每个结点一层一层依次入队,然后依次出队进行操作即可。具体演示及代码如下:

【数据结构】二叉树之链式结构,数据结构,数据结构,算法

void LevelOrder(BTNode* root)
{
	Que q;
	QueueInit(&q);

	if (root)
		QueuePush(&q, root);

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

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

		QueuePop(&q);
	}
	printf("\n");

	QueueDestroy(&q);
}

【数据结构】二叉树之链式结构,数据结构,数据结构,算法

三、二叉树的结点个数

3.1 二叉树的总结点数

一颗二叉树的结点数我们可以看作是根结点+左子树结点数+右子树结点数,那左右子树的结点数又是多少呢?按照相同的方法继续拆分,层层递归直到左右子树为空树,返回空树的结点数0即可。递归代码如下:

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

3.2 二叉树的叶子结点数

左右子树都为空的结点即是叶子结点。这里分为两种情况:左右子树都为空左右子树不都为空

  1. 当左右子树都为空时,则这颗树的叶子结点数为1(根节点)。

  2. 当左右子树不都为空,即根结点不是叶子结点时,这棵树的叶子结点数就为左子树叶子结点数+右子树叶子结点数(空树没有叶子结点)。

int TreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;

	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}

	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

3.3 二叉树第k层结点数

类似的,一颗树第k层的结点数我们可以拆分为其左子树第k-1层结点+右子树第k-1层结点。这样层层递归下去,直到k==1求树的第1层结点数时返回1(树的第1层只有根结点),而如果在递归过程中遇到空树就返回0(空树没有结点)。例如下面一颗树:

【数据结构】二叉树之链式结构,数据结构,数据结构,算法

int TreeKLevel(BTNode* root, int k)
{
	assert(k > 0);

	if (root == NULL)
		return 0;

	if (k == 1)
	{
		return 1;
	}

	return TreeKLevel(root->left, k - 1)
		+ TreeKLevel(root->right, k - 1);
}

【数据结构】二叉树之链式结构,数据结构,数据结构,算法

四、二叉树的高度/深度

树中结点的最大层次称为二叉树的高度。因此,一颗二叉树的高度我们可以看作是

1(根结点)+左右子树高度的较大值。层层递归下去直到遇到空树返回0即可,递归代码如下:

int TreeHeight(BTNode* root)
{
	if (root == NULL)
		return 0;

	return fmax(TreeHeight(root->left), TreeHeight(root->right)) + 1;
}

【数据结构】二叉树之链式结构,数据结构,数据结构,算法

五、二叉树的查找

二叉树的查找本质上就是一种遍历,只不过是将之前的打印操作换为查找操作而已。我们可以使用前序遍历来进行查找,先比较根结点是否为我们要查找的结点,如果是,之间返回;如果不是,遍历左子树和右子树,返回其查找的结果;如果都找不到,返回空指针。代码如下:

// 二叉树查找值为x的结点
BTNode* TreeFind(BTNode* root, int x)
{
	if (root == NULL)
		return NULL;

	if (root->val == x)
		return root;

	BTNode* ret = NULL;
	ret = TreeFind(root->left, x);
	if (ret)
		return ret;

	ret = TreeFind(root->right, x);
	if (ret)
		return ret;

	return NULL;
}

六、二叉树的创建和销毁

最后,我们再来看看如何来创建和销毁一颗二叉树。我们前面说过:二叉树是递归定义的。有了前面的基础,二叉树的创建和销毁也就不是什么难事了。

BTNode* BuyNode(int x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	node->val = x;
	node->left = NULL;
	node->right = NULL;

	return node;
}

// 二叉树销毁
void TreeDestroy(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}

	TreeDestroy(root->left);
	TreeDestroy(root->right);
	free(root);
	//root = NULL;
}

本次的内容到这里就结束啦。希望大家阅读完可以有所收获,同时也感谢各位铁汁们的支持。文章有任何问题可以在评论区留言,小羊一定认真修改,写出更好的文章~~

【数据结构】二叉树之链式结构,数据结构,数据结构,算法文章来源地址https://www.toymoban.com/news/detail-763183.html

到了这里,关于【数据结构】二叉树之链式结构的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【数据结构】二叉树——链式结构

    目录  一、前置声明 二、二叉树的遍历 2.1 前序、中序以及后序遍历 2.2 层序遍历 三、节点个数以及高度 3.1 节点个数 3.2 叶子节点个数 3.3 第k层节点个数 3.4 二叉树的高度/深度 3.5 查找值为x的节点 四、二叉树的创建和销毁 4.1 构建二叉树 4.2 二叉树销毁 4.3 判断二叉树

    2024年02月16日
    浏览(44)
  • 【数据结构】二叉树链式结构

    🚀write in front🚀 📜所属专栏:初阶数据结构 🛰️博客主页:睿睿的博客主页 🛰️代码仓库:🎉VS2022_C语言仓库 🎡您的点赞、关注、收藏、评论,是对我最大的激励和支持!!! 关注我,关注我,关注我 , 你们将会看到更多的优质内容!!   在之前的二叉树的顺序结

    2024年02月03日
    浏览(39)
  • 【数据结构】二叉树(链式)

    😛作者:日出等日落 📘 专栏:数据结构           抱怨是一件最没意义的事情。如果实在难以忍受周围的环境,那就暗自努力练好本领,然后跳出那个圈子。 目录  🎄二叉树 ✔二叉树的结构:  ✔BuyNode(创建二叉树节点): 🎄基本函数操作: ✔PreOrder(前序递归遍历):

    2024年02月01日
    浏览(43)
  • 【数据结构】二叉树的链式结构

    学习链式二叉树要知道三种遍历方式,便于对二叉树的节点以及左子树和右子树进行操作。 前序遍历:根、左子树、右子树 中序遍历:左子树、根、右子树 后序遍历:左子树、右子树、根 以下图为例: 得到的结果: 前序遍历:1 2 3 4 5 6 中序遍历:3 2 1 5 4 6 后序遍历:3 2

    2024年02月08日
    浏览(52)
  • 数据结构:二叉树的链式结构

    朋友们、伙计们,我们又见面了,本期来给大家解读一下链式二叉树的相关知识点,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! 数据结构与算法专栏 :数据结构与算法 个  人  主  页 :stackY、 C 语 言 专 栏 :C语言:从入门到精通 目录 前言

    2024年02月07日
    浏览(56)
  • 数据结构——二叉树的链式结构

      个人主页 : 日刷百题 系列专栏 : 〖C语言小游戏〗〖Linux〗〖数据结构〗  〖C语言〗 🌎 欢迎各位 → 点赞 👍+ 收藏 ⭐️+ 留言 📝  ​ 这里我们使用先序遍历的思想来创建二叉树,这里的内容对于刚接触二叉树的朋友可能有些难理解,不妨先看完下面的二叉树各种遍历

    2024年02月05日
    浏览(43)
  • 【数据结构】二叉树 链式结构的相关问题

     本篇文章来详细介绍一下二叉树链式结构经常使用的相关函数,以及相关的的OJ题。 目录 1.前置说明 2.二叉树的遍历 2.1 前序、中序以及后序遍历 2.2 层次遍历 3.节点个数相关函数实现 3.1 二叉树节点个数 3.2 二叉树叶子节点个数 3.3 二叉树第k层节点个数 3.4 在二叉树中查找值

    2024年02月14日
    浏览(56)
  • 【数据结构】二叉树的链式存储结构

    前序遍历,又叫先根遍历。 遍历顺序:根 - 左子树 - 右子树 代码: 中序遍历,又叫中根遍历。 遍历顺序:左子树 - 根 - 右子树 代码 : 后序遍历,又叫后根遍历。 遍历顺序:左子树 - 右子树 - 根 代码 : 除了先序遍历、中序遍历、后序遍历外,还可以对二叉树进行层序遍

    2024年02月09日
    浏览(42)
  • 【数据结构 —— 二叉树的链式结构实现】

    树是一种非线性的数据结构,它是由n(n=0)个有限结点组成一个具有层次关系的集合。 把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。 1.有一个 特殊的结点,称为根结点 ,根节点没有前驱结点 2.除根节点外, 其余结点被分成M(M0)个互不相交

    2024年02月05日
    浏览(54)
  • 【数据结构—二叉树的链式结构实现】

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言 一、二叉树的存储结构 二、二叉树链式结构的实现 2.1手动构建一课树 2.2二叉树的遍历 三、二叉树链式结构的实现 3.1前序遍历(递归) 3.2中序遍历(递归) 3.3后序遍历(递归) 3.4层序遍历(非递

    2024年02月03日
    浏览(56)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包