数据结构学习分享之链式二叉树(一)

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

💓博主CSDN主页:杭电码农-NEO💓

⏩专栏分类:数据结构学习分享⏪

🚚代码仓库:NEO的学习日记🚚

🌹关注我🫵带你了解更多数据结构的知识
  🔝🔝


数据结构学习分享之链式二叉树(一)


1. 前言

在学习链式二叉树之前,大家一定要对函数栈帧的建立与销毁有一定的了解,因为链式二叉树这一块会涉及很多递归的问题,递归会不断建立栈帧,再不断销毁.理解了函数的栈帧的建立与销毁可以帮助我们理解二叉树的内容如果你对函数栈帧没有概念,请跳转函数栈帧的创建与销毁

其实普通的二叉树的增删查改没有什么意义,因为二叉树用来存储数据太复杂了,我们一般在它的基础上增加一些性质才有意义,比如说很经典点的搜索二叉树等

注:二叉树的内容开始真正上强度了!


2. 链式二叉树的结构

我们之前说过,特殊的二叉树,比如完全二叉树(堆)非常适合用数组的形式来表示,而普通的二叉树就非常适合用链式结构来表示:

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//链式二叉树

typedef char BTDataType;

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

这里我们直接定义一个链式结构,里面有两个指针分别指向节点的左孩子和右孩子,data用来存储值


当然定义完二叉树的结构后,我们还应该将它初始化指向和初始化赋值以便于我们后面使用,这里我们定义一个下图一样的二叉树:

数据结构学习分享之链式二叉树(一)


这里我们初始化节点的时候应该先将左右孩子指针都给置空,把所有节点初始化完成后再根据需要将节点链接起来:这里我们需要两个函数:

BTNode* BuyNode(BTDataType x)//这个函数用于为新节点开辟空间并且初始化
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	newnode->data = x;
	newnode->left = newnode->right = NULL;
	return newnode;
}

上面这个函数用于为节点开辟空间并且初始化内容

BTNode* CreatBinaryTree()//手动创建一共二叉树
{
	BTNode* nodeA = BuyNode('A');
	BTNode* nodeB = BuyNode('B');
	BTNode* nodeC = BuyNode('C');
	BTNode* nodeD = BuyNode('D');
	BTNode* nodeE = BuyNode('E');
	BTNode* nodeF = BuyNode('F');

	nodeA->left = nodeB;
	nodeA->right = nodeC;
	nodeB->left = nodeD;
	nodeC->left = nodeE;
	nodeC->right = nodeF;
	return nodeA;
}

而上面这个函数用于将初始化完成后的值修改指针指向,使他变成我们想要的二叉树.像叶子节点D,E,F在开辟空间时已经将左右孩子置空了,所以这里修改指针指向时不用再刻意置空了!


做好这些后,我们的二叉树结构就基本建立完成了,现在我们接着往下看.


3. 二叉树的遍历

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

  1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
  2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中(间)。
  3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

我们一一来讲解:


3.1 二叉树前序遍历

我们用我们上面定义的二叉树来举例子:

数据结构学习分享之链式二叉树(一)

前序遍历是先访问根节点,再访问左孩子最后有孩子,我们假设将所有的NULL(空节点)编个号,这样好理解:那么对于这个二叉树的前序遍历顺序应该是:A B D 2 3 1 C E 4 5 F 6 7.将所有空节点去掉后就得到: ABDCEF.


3.2 前序遍历代码实现及其解释

这个代码解释起来比较费劲,这里我先给出代码,再做解释:

void PreOrder(BTNode* root)//前序遍历二叉树,递归的方法(中左右)
{
	if (root == NULL)//节点为空就打印NULL后再返回
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->data);//要体现出我们在遍历,这里将值打印出来
	PreOrder(root->left);
	PreOrder(root->right);
}

这里我们使用了递归的手法,前序遍历时,我们将打印内容放在最前面,然后再去递归它的左右孩子,因为这个地方不好解释,所以我建议大家自己去画图理解,这里博主把我自己画的图分享给大家:主要分为两个部分,那就是递归往后走的部分和函数调用完返回的部分

数据结构学习分享之链式二叉树(一)

你自己画出的递归展开图其实也就是一个二叉树的形状.我们在电脑上打印出来结果,可以看见和我们之前预想的结果是相同的:

数据结构学习分享之链式二叉树(一)


3.2 二叉树中序遍历

和前序一样,我们先把中序情况的顺序写出来,再来实现代码:

2 D 3 B 1 A 4 E 5 C 6 F 7.将所有空指针去掉可以得到:DBAECF

我们再来写写中序遍历的代码:

void MidOrder(BTNode* root)//中序遍历二叉树,递归(左中右)
{
	if (root == NULL)
	{
		printf("NULL");
		return;
	}
	MidOrder(root->left);
	printf("%c ", root->data);
	MidOrder(root->right);
}

是的没错!中序遍历就是在前序遍历的基础上将打印函数放在了中间位置,这很巧妙,但是你也得画图去理解,不能只是认为中序遍历就把printf放在中间! 有了前面前序遍历画图的抛砖引玉,这里的递归图就交给你们自己来画

这里还是运行结果看看能不能和我们的猜想对上

数据结构学习分享之链式二叉树(一)


3.3 二叉树的后续遍历

还是老规矩,先将后续遍历的顺序给写出来: 2 3 D 1 B 4 5 E 6 7 F C A.将空指针去掉后得到: DBEFCA

和你猜想的一样,后续遍历的代码就是将printf放在最后[狗头]

void PostOrder(BTNode* root)//后续遍历二叉树(左右中)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%c ", root->data);
}

到这里如果你前两个遍历都画图理解了,相信这个遍历你不画图也能参透里面的奥义了!

结果毫无疑问是能够和我们的猜想对上的:

数据结构学习分享之链式二叉树(一)


4. 二叉树节点个数

二叉树节点个数我们可能会认为很简单,只需要用前序把二叉树走一步,每遇见一个非空节点就加一就可以求出节点个数,很容易写出这样的代码:

int BinaryTreeSize(BTNode* root)
{
  if(root==NULL)
  {
    return;
  }
  int count=0;

  count++;//遍历多少次非空节点就将count加几次
  BinaryTreeSize(root->left);
  BinaryTreeSize(root->right);

但是这样写有一个明显的问题,那就是count是局部变量,变量每一次调用都会创建不同的栈帧空间,也就是说每一个递归函数中的count不能被保存起来,并且我们如果在count前面加上一个static关键字将count放在静态区也是不可取的,因为当我们第一次使用我们的求二叉树节点个数的函数是没有问题的,但是当我们下一次再使用这个函数时,count值不是从0开始,而是从6开始(二叉树有六个元素),第三次调用count就从12开始. 所以这里我们修改一下代码:

void BinaryTreeSize(BTNode* root, int* p)//二叉树节点的个数,这里的p是外面main定义的变量的地址
{
	if (root == NULL)
	{
		return;
	}
	++(*p);
	BinaryTreeSize(root->left,p);
	BinaryTreeSize(root->right, p);
}

这里我们在外部定义一个变量来存储二叉树节点的个数,然后我们把变量的地址传进来就可以很好的修正刚刚的问题,这里还有一种写法,这种写法应该首先掌握:

int BinaryTreeSize2(BTNode* root)//求二叉树节点个数,直接返回节点个数
{
	return root == NULL ? 0 :
		BinaryTreeSize2(root->left) 
		+ BinaryTreeSize2(root->right) + 1;
}

这里如果节点为空就返回0,不为空就接着往后递归,代码比较抽象,还是需要我们画图来理解:

数据结构学习分享之链式二叉树(一)

你们应该自己画图理解一番.


5. 二叉树叶子节点的个数

叶子节点就是左右孩子都为空的节点,首先第一步我们要想到的是,如果数为空,那么我们应该返回0因为它一个节点都没有,第二点是节点的左孩子和右孩子都为空时,我们应该返回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);
	//既不是叶子也不是空就返回左右节点的叶子数
}

这里值得注意的是第一步,root==NULL时,这时其实有两种情况,一种是我们数本身就是空树,第二种是我们的节点是空节点,这两种情况都应该返回0,并且其实这两种情况可以合并为一种情况

这里的递归不难理解,所以就不给大家画递归展开图了(如果你感到困难,也应该自己画一幅图)


6. 二叉树第K层的节点个数

我们还是可以像刚刚一样分析,当数为空树时,我们应该返回0,而这里当K等于1时,也就是第一层,一定为1个节点,所以返回1.当这两种情况都不满足时,那么说明root这棵树的第k层节点在子树里面,这样就可以转换成求左右子树的k-1层的节点个数!

int BinaryTreeLeaveSize(BTNode* root, int k)//返回二叉树第k层节点数
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	//root既不是空,k也不为1时,说明第k层在root的字树中,转换为求左右子树的第k-1层的节点树
	return BinaryTreeLeaveSize(root->left, k - 1) + BinaryTreeLeaveSize(root->right, k - 1);
}

这里只要理解了root既不是空,并且k也不等于1,我们就转换这个问题求左右子树的k-1层的节点数,再画递归展开图理解一下:

假设我们设K=3.

数据结构学习分享之链式二叉树(一)

这里的递归用照片其实也不太好看,在这个版块大家尽量自己画图,没有画图思路的可以看看我是怎么画的,看别人的图理解起来还是很难得


7. 总结

二叉树的内容还没有结束,由于二叉树这一章的内容较多,我将一些内容放在下一节讲,下一节包括:求二叉树的高度,查找值为x的节点,二叉树的层序遍历,判断二叉树是不是完全二叉树.敬请期待!文章来源地址https://www.toymoban.com/news/detail-458785.html

🔎 下期预告:链式二叉树详解(二) 🔍

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

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

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

相关文章

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

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

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

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

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

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

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

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

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

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

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

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

    2024年02月07日
    浏览(59)
  • 【数据结构和算法】--- 二叉树(3)--二叉树链式结构的实现(1)

    在学习二叉树的基本操作前,需先要创建一棵二叉树,然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入,且为了方便后面的介绍,此处手动快速创建一棵简单的二叉树,快速进入二叉树操作学习,等二叉树结构了解的差不多时,我们反过头再来研

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

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

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

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

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

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

    2024年02月05日
    浏览(57)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包