模拟实现链式二叉树及其结构学习——【数据结构】

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

模拟实现链式二叉树及其结构学习——【数据结构】,数据结构,c语言,算法

W...Y的主页 😊

代码仓库分享 💕


之前我们实现了用顺序表完成二叉树(也就是堆),顺序二叉树的实际作用就是解决堆排序以及Topk问题。

今天我们要学习的内容是链式二叉树,并且实现链式二叉树,这篇博客与递归息息相关!

目录

链式存储

二叉树链式结构的实现

链式二叉树的快速创建

二叉树的遍历

前序、中序以及后序遍历

前序遍历的实现

中序遍历的实现

后序遍历实现

节点个数以及高度

总结点个数

叶子节点个数

第k层节点个数

整个代码模板以及验证


链式存储

什么是链式存储,就是用链来指示元素的逻辑关系。链式结构又分为二叉链和三叉链,而我们今天学习的是二叉链表,又称链式二叉树。
模拟实现链式二叉树及其结构学习——【数据结构】,数据结构,c语言,算法

我们一般用链表来表示一棵二叉树,通常的方法是链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
    struct BinTreeNode* _pLeft; // 指向当前节点左孩子
    struct BinTreeNode* _pRight; // 指向当前节点右孩子
    BTDataType _data; // 当前节点值域
}

对于链式二叉树,我们与其他前面的链表、顺序表、堆……数据结构有所不同,我们针对这一块并不是增删查改,为什么呢?

模拟实现链式二叉树及其结构学习——【数据结构】,数据结构,c语言,算法

因为链式二叉树的存储方式,就是把每一个节点封装在结构体中然后进行链接, 而我们进行增删查改没有必要在这么复杂的结构中实现,当我有每个节点的左右指针时,我可以随心所欲,在哪里都可以进行插入删除。如果非得使用增删查改,我们就可以使用简单一些的数据结构进行。

所以我们学习链式二叉树是为了给我们后面的高级数据结构AVL、红黑树打基础的。所以我们也要认真学!!!

二叉树链式结构的实现

链式二叉树的快速创建

我们为了快速实现链式二叉树,从中感受到链式二叉树的结构,我们快速手动生成一个链式二叉树。

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
	int val;
}BTNode;
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;
}
int main(void)
{
	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 0;
}

我们创建了链式二叉树的基本结构,左指针右指针以及存储的值,然后开辟空间将里面的所有内容初始化。在main函数中手动插入了1、2、3、4、5、6封装在结构体中,然后依照下图进行链接快速得到一个链式二叉树。模拟实现链式二叉树及其结构学习——【数据结构】,数据结构,c语言,算法

 下面依照创建完成的链式二叉树继续学习。

二叉树的遍历

前序、中序以及后序遍历

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

按照规则,二叉树的遍历有:前序/中序/后序的递归结构遍历:
1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树前。
2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中(间)。
3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。
模拟实现链式二叉树及其结构学习——【数据结构】,数据结构,c语言,算法

由于被访问的结点必是某子树的根,所以N(Node)、L(Left subtree)和R(Right subtree)又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。 

前序遍历的实现

针对前序遍历,我们记住先访问左树,再访问根,最后再访问右树。我们可以先手动遍历一遍,将一颗大树分解成三部分(左树、根、右树),再将左树看作树继续分成左树右树与根,右数也一样,将其一直进行分解,直到左右树为空为止即可停止。模拟实现链式二叉树及其结构学习——【数据结构】,数据结构,c语言,算法

// 二叉树前序遍历
void PreOrder(BTNode* root)
{
    if (root == NULL)
	{
		return;
	}
	printf("%d ", root->val);
	PrevOrder(root->left);
	PrevOrder(root->right);
}

 在前序遍历中,我们使用递归进行。如果root为NULL证明树为空,直接返回即可。当进入下面代码时,前序遵循的是根、左树、右树。所以我们先将根打印出来,然后遍历左树。当进入左树递归时,root->left进入左树,那根的左子节点就变成了左树的根,打印出来继续递归,依次类推。而右树也是一样的,将左树遍历完后,我们将递归右数,先将左树递归的所有函数销毁,进入root->right中进行递归,根的右子节点成为右树的根,打印出进行递归,一直遵循根、左树、右树进行。

递归图解如下:模拟实现链式二叉树及其结构学习——【数据结构】,数据结构,c语言,算法

模拟实现链式二叉树及其结构学习——【数据结构】,数据结构,c语言,算法 虽然代码非常简洁,但是理解起来不太容易,我们不能只记住代码如何写,应该理解其中的原理才行。

模拟实现链式二叉树及其结构学习——【数据结构】,数据结构,c语言,算法

中序遍历的实现

只要我们理解了前序遍历,那么中序后序都是非常简单的存在。只需记住:左树、根、右树,然后写出递归即可

模拟实现链式二叉树及其结构学习——【数据结构】,数据结构,c语言,算法

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

 有没有发现这串代码与前序遍历非常相似,只是将两行代码交换位置就可以实现。我们先将左树的内容递归完然后打印,再打印根的,最后再打印右树的即可。可以参考前置遍历进行推理。

这里如果实在理解不了的可以认为调用InOrder(root->left)是遍历打印左树,printf是打印根,而调用递归InOrder(root->right)是为了遍历打印右树。

后序遍历实现

模拟实现链式二叉树及其结构学习——【数据结构】,数据结构,c语言,算法

我相信大家已经知道函数怎么写了,那我就直接给模板:

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

 下面我们更进一步的学习链式二叉树的结构,上强度!!!

节点个数以及高度

总结点个数

我们需要建立一个函数,求出整个二叉树所有的节点个数。

有人一定会想直接全部遍历一遍然后创建一个全局变量用来统计个数就可以了。没错这个方法是可行的,我们刚才说的二叉树的遍历,然后在这里用一遍不就拿下来了。

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

我们直接遍历整棵树,先遍历左树、再遍历右数,每遍历一个节点size++即可。

但是这个函数有一个极大的缺点,当我们使用函数时,我们可以在任意一个位置去调用,全局变量是存储在静态区的,不会随着函数的结束而销毁,当我们调用过一次后, 再一次去调用此函数,如果没有及时将size归零,结果将会累加起来成为错误的结果。

我们应该优化一下程序:

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

直接使用递归,将左右子树包含在返回值中,我们在后面加上1,如果递归成功将+1,然后返回最后递归之和。

我们可以做个比喻:在一个大学中校长想要统计全校的人数,校长不可能亲自挨家挨户访问查人,它会通知每个院的院长,然后院长通知每个系的系主任,由系主任通知导员,最后由导员通知每个班的班长来统计人数。一级一级的下放任务。而这个递归也是如此,统计总节点个数就是一级一级下方给各个节点计数。模拟实现链式二叉树及其结构学习——【数据结构】,数据结构,c语言,算法 

叶子节点个数

需要求出链式二叉树的叶子节点个数,叶节点或终端节点:度为0的节点称为叶节点;

大致原理都是一样的,只是条件不同。我们需要叶子节点就必须是度为0的节点,所以一个节点的root->right == NULL && root->left == NULL 这是必要条件,然后我们就应该去遍历二叉树的左子树与右子树去寻找满足条件的节点。最后求出左右子树的叶子节点之和即可。

代码实现:

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

第k层节点个数

当我们需要某一层的节点个数,我们也需要创建一个函数来进行,那我们应该怎么弄呢?

还是一级一级去派遣,假设我们需要第三层的节点个数,当我们刚进入在第一层时,我们距离目标层数还有两层之差,当我们遍历到第二层时,我们距离目标还有一层,当我们进入目标层后我们就要进行遍历节点, 统计出左右子树k层节点之和返回即可。

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

需要注意的是我们先得使用assert进行断言,防止树为空。


整个代码模板以及验证

下面是增章全部代码以及测试用例:

#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
	int val;
}BTNode;

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 PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	printf("%d ", root->val);
	PrevOrder(root->left);
	PrevOrder(root->right);
}

void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	InOrder(root->left);
	printf("%d ", root->val);
	InOrder(root->right);
}
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->val);
}
//总节点个数
//int TreeSize(BTNode* root)
//{
//	static int size = 0;
//	if (root == NULL)
//		return 0;
//	else
//		++size;
//	TreeSize(root->left);
//	TreeSize(root->right);
//	return size;
//}
//int size = 0;
//int TreeSize(BTNode* root)
//{
//	if (root == NULL)
//		return 0;
//	else
//		++size;
//	TreeSize(root->left);
//	TreeSize(root->right);
//	return size;
//}
int TreeSize(BTNode* root)
{
	return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
//叶子节点个数
int TreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	if (root->right == NULL && root->left == NULL)
		return 1;
	return TreeLeafSize(root->right) + TreeLeafSize(root->left);
}
//第k层节点个数
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);
}

int main(void)
{
	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;
	PrevOrder(node1);
	printf("\n");
	InOrder(node1);
	printf("\n");
	PostOrder(node1);
	printf("\n%d", TreeSize(node1));

	printf("\n%d", TreeSize(node1));
	printf("\n%d", TreeLeafSize(node1));
	printf("\n%d", TreeKLevel(node1, 2));
	return 0;
}

代码运行结果如下:

模拟实现链式二叉树及其结构学习——【数据结构】,数据结构,c语言,算法

运行结果分别为前置遍历、中序遍历、后序遍历、总节点个数(两次)、叶子节点个数、第二层节点个数

模拟实现链式二叉树及其结构学习——【数据结构】,数据结构,c语言,算法

 参考下图均正确!!!


以上就是本次博客的全部内容,希望可以帮助到大家!!!支持博主的一键三连一下,谢谢大家❤️文章来源地址https://www.toymoban.com/news/detail-725131.html

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

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

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

相关文章

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

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

    2023年04月21日
    浏览(43)
  • 数据结构学习分享之链式二叉树(二)

    💓博主CSDN主页:杭电码农-NEO💓   ⏩专栏分类:数据结构学习分享⏪   🚚代码仓库:NEO的学习日记🚚   🌹关注我🫵带你了解更多数据结构的知识   🔝🔝 本节是上一节二叉树知识的延申,这一节中会用到队列的相关知识和二叉树的结构配合使用,如果你还没有接触过队列

    2024年02月06日
    浏览(29)
  • 数据结构学习分享之链式二叉树(一)

    💓博主CSDN主页:杭电码农-NEO💓   ⏩专栏分类:数据结构学习分享⏪   🚚代码仓库:NEO的学习日记🚚   🌹关注我🫵带你了解更多数据结构的知识   🔝🔝 在学习链式二叉树之前,大家一定要对函数栈帧的建立与销毁有一定的了解,因为链式二叉树这一块会涉及很多递归的问

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

    目录 一,二叉树的链式结构 二,二叉链的接口实现         1,二叉链的创建         2,接口函数         3,动态创立新结点         4,创建二叉树         5,前序遍历         6,中序遍历         7,后序遍历 三,结点个数以及高度等      

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

    目录 1. 前置说明 2. 二叉树的遍历 2.1 前序、中序以及后序遍历 2.2 层序遍历 3. 节点个数及高度等 4. 二叉树的创建和销毁 在学习二叉树的基本操作前,需先要创建一棵二叉树,然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入,为了降低大家学习成

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

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

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

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

    2024年02月12日
    浏览(40)
  • 数据结构——二叉树的链式存储的实现

                             InitBiTree(BiTree T)——初始化二叉树。                         CreateBiTree(BiTree T)——先序遍历的顺序建立二叉链表。                         PreOrderTraverse(BiTree T)——先序遍历。                         

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

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

    2024年02月07日
    浏览(48)
  • 数据结构入门(C语言版)二叉树链式结构的实现

    简单回顾一下二叉树的 概念: ★ 空树 ★非空:根节点,根节点的左子树、根节点的右子树组成的。 从概念中可以看出,二叉树定义是递归式的,因此后序基本操作中基本都是按照该概念实现的。 下面我们先看二叉树的结构体定义以及创建 首先结构体的定义是元素本身,以

    2023年04月23日
    浏览(46)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包