数据结构-二叉树的链式存储

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

二叉树的链式结构

二叉树的存储结构有顺序结构和链式结构两种,顺序结构我已经在上篇进行了详细的讲解,地址:数据结构-二叉树的顺序存储与堆(堆排序),本篇我们就主要讲解二叉树的链式存储。

二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链,其结构如下图:
数据结构-二叉树的链式存储
三叉链在后面讲解红黑树时再讲解,本篇我们主要先来以二叉链来学习一下二叉树的实现。

链式结构的遍历

我们知道二叉树的结构不是线性的,每一个节点都有两个子树,那如果我们想要访问一个二叉树中的所以元素时,我们应该以什么样的规律去访问呢,是先访问根节点还是先访问子树?这就涉及到了二叉树的遍历问题。
所谓遍历(Traversal)是指沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问 题。 遍历是二叉树上最重要的运算之一,是二叉树上进行其它运算之基础。
遍历顺序一共分为4种,分别是:

  1. NLR:前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。先根遍历
  2. LNR:中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中(间)。中根遍历
  3. LRN:后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。后根遍历
  4. 层序遍历:设二叉树的根节点所在层数为1,层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树根节点,然后从左到右访问第2层上的节点,接着是第三层的节点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历。

简单来说,前,中,后序遍历就是以访问根节点的时间不同来划分的
前序:根->左子树->右子树
中序:左子树->根->右子树
后续:左子树->右子树->根

不同的遍历顺序有什么差异呢,比如我们现在想要遍历下面这个二叉树
数据结构-二叉树的链式存储
我们可以发现不同的遍历顺序访问元素的顺序确实是不一样的。
二叉树的前,中,后序遍历属于深度优先的遍历方式,一般用递归实现。
层序遍历属于广度优先的遍历方式,一般借助队列实现。
他们的实现我就放在后面链式存储的实现中了。

二叉树链式存储的实现

在实现二叉树之前,我们要先创建一个二叉树节点的结构体类型,然后我们可以通过根节点对这个二叉树进行操作。

typedef char BTDataType;
typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* left;  // 指向当前节点左孩子
	struct BinaryTreeNode* right; // 指向当前节点右孩子
	BTDataType data;              // 当前节点值域
}BTNode;

二叉树节点的创建

BTNode* CreateTreeNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	node->data = x;
	node->left = NULL;
	node->right = NULL;
	return node;
}

1.动态开辟一个空间存放我们节点的值,把左右指针置空,返回节点的地址。
(该接口可以用来创建二叉树的所有节点)

前序遍历

根据根,左子树,右子树的顺序访问二叉树的所以值

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

1.先判断节点是否为空,空就返回。
2.前序遍历,先访问根节点,那就是节点当前的值,在访问左子树,再访问右子树,使用递归的方法实现。

大伙可以看下面的流程图来更好的理解前序遍历的递归过程
我们还是遍历上图中的哪个二叉树。
数据结构-二叉树的链式存储

中序遍历

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

1.判断是否为空树。
2.先递归访问左树,再访问节点自身,在访问右树。

我们还是来看图来观察一下递归的过程
数据结构-二叉树的链式存储

后序遍历

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

1.判断节点是否为空,空就返回。
先访问左子树,再访问右子树,再访问自己。

老规矩,直接上图
数据结构-二叉树的链式存储

二叉树元素个数

可以使用任意一种遍历顺序遍历二叉树,然后统计节点的个数

void TreeSize(BTNode* root, int* size)
{
	if (root == NULL)
	{
		return;
	}
	(* size)++;
	TreeSize(root->left,size);
	TreeSize(root->right,size);
}

需要注意的是,如果我们在函数里面定义size,那么在遍历递归时,我们是无法实现size叠加的功能的,因为每调用一次,就会对size进行一次临时拷贝,改变这个拷贝的值过后,当这一层的调用完成,栈帧销毁,size也被销毁了,改变没有起到任何效果,所以我们要在函数外面定义size,然后传入size的地址,通过地址就可以对size进行改变了。
如果我们不想在外面定义size,还要一种方法

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

即使用递归的方法计算节点个数,节点的个数就等于左子树的节点个数加右子树的节点个数在加自己的这一个,如果是空节点就返回0。

叶节点的个数

叶节点就是度为0的节点,即没有子树,与计算节点个数的递归方法类似,我们也可以使用递归的方法计算叶节点的个数

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

1.如果一个节点为空,那它的叶节点个数肯定为0
2.如果一个节点的左子树和右子树同时为空,说明这是一个叶节点,如果不是,就计算它的左子树的叶节点和右子树的叶节点之和就是当前节点以下的所以叶节点。
3.根节点进入函数后,就先判断根节点是不是叶节点,如果不是,就计算根节点左右子树的叶节点的和,形成递归。

第k层节点的个数

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

同样是使用递归的方法
1.如果节点为空,那节点的个数就为0.
2.如果我们要计算第k层的元素个数,我们先从根节点开始,假设我们每向下一层k就减1,那么当k=1时,表示我们来到了第k层,然后计算k=1时的节点个数返回相加即可。

查找元素

BTNode* TreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	BTNode* lret = TreeFind(root->left, x);
	if (lret)
	{
		return lret;
	}
	BTNode* rret = TreeFind(root->right, x);
	if (rret)
	{
		return rret;
	}
	return NULL;
}

1.如果节点为空,就返回空。
2.如果节点的值等于要查找的值,就返回节点的坐标。
3.如果节点不为空,值也不是我们要查找的值,就查找节点的左子树,如果查找的结果不为空,就代表找到了,就返回。
4.如果左子树的查找结果为空,就查找右子树,如果找到就返回,找不到就返回空。

二叉树销毁

void BinaryTreeDestory(BTNode** pproot)
{
	if (*pproot == NULL)
	{
		return NULL;
	}
	BinaryTreeDestory(&(*pproot)->left);
	BinaryTreeDestory(&(*pproot)->right);
	free(*pproot);
	pproot = NULL;
}

销毁二叉树需要把二叉树的每个节点都销毁,所以首先,我们的销毁顺序应该是后序。
其次,我们节点里存放的是左右孩子的指针,如果我们传节点的指针类型的话,那么函数里面的左右孩子的地址就是一份临时拷贝,在函数里我们用这个拷贝的地址释放节点没问题但是我们无法对每个节点的指针进行置空,所以销毁二叉树时我们要传二级指针。

二叉树的层序遍历

层序遍历就是一层一层的遍历,在链式储存中,我们一般借助队列来实现层序遍历。
我们先把我们前面实现的栈的代码复制到我们现在的工程中(链接在数据结构-栈和队列详解),然后包含好栈的头文件。
我们利用的就是队列的先进先出的性质,
1.先让根入队。
2.出队头的数据,再让队头数据的左右孩子入队。
看一下下面的流程图就明白了
数据结构-二叉树的链式存储
图里的小红圆圈代表空(手不太稳,可能与圆有那么一点点的偏差),我们每从队头删除掉一个元素,就让这个元素的两个孩子入队,直到队列为空为止,最后我们访问的顺序刚好就是层序遍历的顺序,下面我们就对这个代码进行实现吧。

void TreeLevelOrder(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);
		}
	}
	printf("\n");
	QueueDestory(&q);
}

1.首先我们要创建一个队列,对队列进行初始化。
2.让二叉树的根入队(注意修改队列元素的类型)。
3.判断队列是否为空,如果队列为空,说明遍历已经结束了,换一个行然后销毁队列。
4.如果队列不为空,就让把队头的节点拷贝出来,然后删除队头的节点,把刚刚拷贝的节点的数据打印一遍,然后让拷贝接节点的左右孩子先后入队。如果孩子没有子节点,相当于把NULL入队,并不影响结果。

判断是否为完全二叉树

其思想与二叉树的层序遍历类似,如果一个树不是完全二叉树时,那么但我们对它进行层序遍历时,其节点的中间就会有NULL,我们就可以通过这一点来判断是否为完全二叉树。
数据结构-二叉树的链式存储

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;
		}
		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front)
		{
			return false;
		}
	}
	QueueDestory(&q);
	return true;
}

1.前半部分与二叉树的层序遍历一样,建队列,根入队,队列不为空,进入while循环,在循环中删队头节点,然后让该节点的左右孩子入队。
2.这里循环停止的条件还要加上一个即堆顶的元素为空,在跳出循环后,有两种情况,第一种是队列已经空了,节点之间没有空,表明是一个完全二叉树,返回true,第二种情况是队列并不为空,只是在访问队头节点时访问到了NULL,这时我们要再次进行循环,如果队列不为空,我们就进入循环挨个查找并删除队头的节点,如果发现一个不为空的节点,就说明节点之间有NULL相隔,说明不是完全二叉树,返回false。文章来源地址https://www.toymoban.com/news/detail-433731.html

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

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

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

相关文章

  • 数据结构:二叉树的链式结构

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

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

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

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

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

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

    树是一种非线性的数据结构,它是由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. 二叉树的遍历 2.1 前序、中序以及后序遍历 2.2 层序遍历 3. 节点个数及高度等 4. 二叉树的创建和销毁 在学习二叉树的基本操作前,需先要创建一棵二叉树,然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入,为了降低大家学习成

    2024年02月08日
    浏览(40)
  • 数据结构初阶--二叉树的链式结构

    目录 一.二叉树链式结构的概念 二.二叉树链式结构的功能实现 2.1.链式二叉树的定义 2.2.链式二叉树的构建 2.3.链式二叉树的遍历 2.3.1.先序遍历 2.3.2.中序遍历 2.3.3.后序遍历 2.3.4.层序遍历 2.4.链式二叉树的求二叉树的结点数量 法一:计数法 法二:分治法 2.5.链式二叉树的求二

    2024年02月12日
    浏览(43)
  • 数据结构:二叉树的链式结构的实现

      目录  1.通过前序遍历构建二叉树 2. 二叉树的销毁  3.二叉树的遍历 4. 二叉树的节点个位和二叉树的叶子节点个位数 5. 二叉树的的k层节点数和查找值为x的节点 6. 判断二叉树是否为完全二叉树和求二叉树的高度h 二叉树的前序遍历 二叉树的中序遍历 二叉树的后序遍历

    2024年02月12日
    浏览(44)
  • 【数据结构】二叉树的链式结构的实现 -- 详解

    在学习二叉树的基本操作前,需先要创建一棵二叉树,然后才能学习其相关的基本操作。为了降低大家学习成本,此处手动快速创建一棵简单的二叉树,快速进入二叉树操作学习。 注意 :上述代码并不是创建二叉树的方式。 学习二叉树结构,最简单的方式就是遍历。所谓

    2024年02月12日
    浏览(40)
  • 【数据结构】二叉树的链式实现及遍历

    后文所有代码中的二叉树结点: 前,中,后序遍历都可以采用分治递归的思想解决,将根节点和它的孩子结点分别处理。 此处仅利用递归展开图分析前序遍历,中序和后序也是相同的思想: 层序遍历需要利用队列来进行,如果二叉树跟结点不为空,则让 指向它的一个指针入

    2024年02月07日
    浏览(48)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包