数据结构第十三弹---链式二叉树基本操作(上)

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

1、结构定义

实现一个数据结构少不了数据的定义,所以第一步需要定义二叉树的机构。

typedef char BTDataType;//定义数据类型,可以根据需要更改

typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* left;//左指针
	struct BinaryTreeNode* right;//右指针
	BTDataType data;//存储数据
}BTNode;

2、手动创建二叉树

初次学习链式二叉树,对于创建一个二叉树较难理解,所以先手动创建二叉树,学习一些操作之后再来通过函数实现链式二叉树。

//创建结点函数
BTNode* BuyTree(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	newnode->data = x;
	newnode->left = NULL;
	newnode->right = NULL;

	return newnode;
}
//创建结点

	BTNode* A = BuyTree('A');
	BTNode* B = BuyTree('B');
	BTNode* C = BuyTree('C');
	BTNode* D = BuyTree('D');
	BTNode* E = BuyTree('E');
	BTNode* F = BuyTree('F');
//链接结点
	A->left = B;
	A->right = E;
	B->left = C;
	B->right = D;
	E->left = F;

数据结构第十三弹---链式二叉树基本操作(上),数据结构,算法,c语言

3、前序遍历

前序遍历,又称先根遍历。
遍历顺序:根,左子树,右子树。

代码实现

void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->data);//根
	PrevOrder(root->left);//左子树
	PrevOrder(root->right);//右子树
}

此处实现的遍历版本是将空指针也打印出来的版本,更适合新手理解
测试
数据结构第十三弹---链式二叉树基本操作(上),数据结构,算法,c语言

4、中序遍历

中序遍历,又称中根遍历。
遍历顺序:左子树,根,右子树。

代码实现

void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	InOrder(root->left);//左子树
	printf("%c ", root->data);//根
	InOrder(root->right);//右子树
}

测试
数据结构第十三弹---链式二叉树基本操作(上),数据结构,算法,c语言

5、后序遍历

后序遍历,又称后根遍历。
遍历顺序:左子树,右子树,根。

代码实现

void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->left);//左子树
	PostOrder(root->right);//右子树
	printf("%c ", root->data);//根
}

测试
数据结构第十三弹---链式二叉树基本操作(上),数据结构,算法,c语言

6、层序遍历

层序遍历,自上到下,自左到右依次访问数的结点就是层序遍历。

思想(借助一个队列):
1、先将根节点入队,然后开始从队头出数据
2、出队头的数据同时将队头左右子树的结点入队(遇到NULL则不入队)
3、重复第二步,直到队列为空

数据结构第十三弹---链式二叉树基本操作(上),数据结构,算法,c语言
代码实现

void LevelOrder(BTNode* root)
{
	Queue q;//创建爱你队列
	QueueInit(&q);//初始化队列
	if (root)//根节点不为空则入队
		QueuePush(&q, root);
	while (!QueueEmpty(&q))//队列不为空,循环继续
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);//出队
		printf("%c ", front->data);//打印数据

		if (front->left)//如果左子树不为空则入队
			QueuePush(&q, front->left);
		if (front->right)//右子树不为空入队
			QueuePush(&q, front->right);
	}

	QueueDestory(&q);//销毁队列
}

测试
数据结构第十三弹---链式二叉树基本操作(上),数据结构,算法,c语言

7、计算结点个数

计算结点个数时,可以将问题拆成子问题
1、为空时,结点个数为0
2、不为空时,结点个数=左子树结点个数+右子树结点个数+1(根节点)

代码实现

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

测试
数据结构第十三弹---链式二叉树基本操作(上),数据结构,算法,c语言

8、计算叶子结点个数

计算叶子结点个数时,可以将问题拆成子问题
1、为空时,叶子结点个数为0
2、结点左右孩子为空时,叶子结点个数为1
3、结点不为空,叶子结点个数=左子树叶子结点个数+右子树叶子结点个数

代码实现

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);
}

测试
数据结构第十三弹---链式二叉树基本操作(上),数据结构,算法,c语言

9、计算第K层结点个数

计算第K层结点个数时,可以将问题拆分成子问题。
1、为空和非法时,结点个数为0个
2、为第一层时,结点个数为1个
3、不为空且合法时,第K层的结点个数=第K-1层的左子树结点个数+第K-1层的右子树结点个数

代码实现

//第k层结点的个数
int TreeKLevelSize(BTNode* root, int k)
{
	if (k < 1 || root == NULL)//空树或输入k值不合法
		return 0;
	if (k == 1)//第一层结点个数
		return 1;
  //不为空且合法时,第K层的结点个数=第K-1层的左子树结点个数+第K-1层的右子树结点个数
	return TreeKLevelSize(root->left, k - 1) + TreeKLevelSize(root->right, k - 1);
}

测试
数据结构第十三弹---链式二叉树基本操作(上),数据结构,算法,c语言

10、计算树的最大深度

计算树的最大深度时,可以将问题拆成子问题
1、为空时,深度为0
2、不为空时,最大深度为左子树和右子树较大的深度+1(自己)

代码实现

int maxDepth(BTNode* root) {
	if (root == NULL)
		return 0;//为空,深度为0
	int leftDepth = maxDepth(root->left);//记录左子树最大深度
	int rightDepth = maxDepth(root->right);//记录右子树最大深度
    //不为空时,最大深度为左子树和右子树较大的深度+1(自己)
	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

测试
数据结构第十三弹---链式二叉树基本操作(上),数据结构,算法,c语言

总结

本篇博客就结束啦,谢谢大家的观看,如果公主少年们有好的建议可以留言喔,谢谢大家啦!文章来源地址https://www.toymoban.com/news/detail-787524.html

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

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

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

相关文章

  • 【链式二叉树】数据结构链式二叉树的(万字详解)

    前言: 在上一篇博客中,我们已经详解学习了堆的基本知识,今天带大家进入的是二叉树的另外一种存储方式----“链式二叉树”的学习,主要用到的就是“递归思想”!! 前情回顾: 再看二叉树基本操作前,再回顾下二叉树的概念,二叉树是: 空树 非空:根节点,根节点

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

    😛作者:日出等日落 📘 专栏:数据结构           抱怨是一件最没意义的事情。如果实在难以忍受周围的环境,那就暗自努力练好本领,然后跳出那个圈子。 目录  🎄二叉树 ✔二叉树的结构:  ✔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)
  • 【数据结构】二叉树之链式结构

    🔥 博客主页 : 小羊失眠啦. 🎥 系列专栏 : 《C语言》 《数据结构》 《Linux》 《Cpolar》 ❤️ 感谢大家点赞👍收藏⭐评论✍️ 在学习二叉树各种各样的操作前,我们先来回顾一下二叉树的概念: 二叉树是度不超过2的树,由根结点和左右2个子树组成,每个子树也可以看作

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

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

    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)
  • 【数据结构】二叉树 链式结构的相关问题

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

    2024年02月14日
    浏览(57)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包