【数据结构】二叉树(链式)

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

😛作者:日出等日落

📘 专栏:数据结构

          抱怨是一件最没意义的事情。如果实在难以忍受周围的环境,那就暗自努力练好本领,然后跳出那个圈子。

【数据结构】二叉树(链式)

目录

 🎄二叉树

✔二叉树的结构:

 ✔BuyNode(创建二叉树节点):

🎄基本函数操作:

✔PreOrder(前序递归遍历):

✔InOrder(中序递归遍历):

✔PostOrder(后序递归遍历):

 ✔TreeSize(函数结点个数):

✔TreeleafSize(叶子结点个数):

 ✔TreeHeight(树的深度/高度):

 ✔TreeKLevelSize(第k层的结点个数):

✔TreeFind(二叉树查找值为x的值):

✔LevelOrder(层序遍历):

 ✔TreeComplete(判断二叉树是否是完全二叉树):

 ✔TreeDestory(二叉树销毁):


 

 🎄二叉树

二叉树(Binary tree)是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树,且有左右之分。

注:如需详细了解,请看详细二叉树概念博客http://t.csdn.cn/sJWfX

✔二叉树的结构:

二叉树是一个节点root,链接着一个左节点left和一个右节点right

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

 ✔BuyNode(创建二叉树节点):

BTNode* BuyNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail:");
		exit(-1);
	}
	newnode->data = x;
	newnode->left = newnode->right = NULL;
	return newnode;
}

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

	//构造二叉树
	BTNode* n1 = BuyNode(1);
	BTNode* n2 = BuyNode(2);
	BTNode* n3 = BuyNode(3);
	BTNode* n4 = BuyNode(4);
	BTNode* n5 = BuyNode(5);
	BTNode* n6 = BuyNode(6);
	BTNode* n7 = BuyNode(7);

	n1->left = n2;
	n1->right = n4;
	n2->left = n3;
	n3->left = n7;
	n4->left = n5;
	n4->right = n6;

注意上述代码并不是创建二叉树的方式,真正创建二叉树方式后序详解重点讲解。

🎄基本函数操作:

再看二叉树基本操作前,再回顾下二叉树的概念,

二叉树是:

1. 空树

2. 非空:根节点,根节点的左子树、根节点的右子树组成的。

✔PreOrder(前序递归遍历):

前序遍历是每颗子树先遍历root节点,再遍历左子树,最后在遍历右子树

前序遍历:root  左子树 右子树

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

✔InOrder(中序递归遍历):

中序遍历是每颗子树都先遍历左子树,再遍历root节点,最后在遍历右子树。

中序遍历:左子树 root  右子树

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

✔PostOrder(后序递归遍历):

后序遍历是每颗子树都先遍历左子树,再遍历右子树,最后在遍历root节点。

后序遍历:左子树 右子树  root

// 二叉树后序遍历
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

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

 ✔TreeSize(函数结点个数):

二叉树节点的个数,可以看成左子树的节点个数+右子树的节点个数+1(根节点)。

遇到NULL返回0。

//返回二叉树的结点个数
int TreeSize(BTNode* root)
{
	return root == NULL ? 0 :
		TreeSize(root->left) + TreeSize(root->right) + 1;
}

✔TreeleafSize(叶子结点个数):

叶节点代表它没有左右节点了,也就是左右节点皆为NULL

  • 当左右左右节点皆为NULL时返回1
  • 叶节点数等于左子树的叶子个数+右子树的叶子个数
//返回叶子结点个数
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);
}

 ✔TreeHeight(树的深度/高度):

当只有一层的时候,左子树为0,右子树为0层,总层数为 1层。

当有2层时,左子树为1,右子树为1层,总层数为1+1层。

当有3层时,左子树为2,右子树为2层,总层数为2+1层。

....

当有N层时,左子树为N-1层,右子树为N1层,总层数为(N-1)+1层。

这样就可以将树的高度看成较高子树的层高+1(根节点的那一层)。因此将左右子树的层数计算出来,让他们较大的一个+1就是二叉树的高度了。

//返回树的深度
int TreeHeight(BTNode* root)
{
	if (root == NULL)
		return 0;
	int leafHeight = TreeHeight(root->left);
	int rightHeight = TreeHeight(root->right);
	return leafHeight > rightHeight ? leafHeight + 1 : rightHeight + 1;
}

 ✔TreeKLevelSize(第k层的结点个数):

可以通过左右子树,让他们可下降k-1层,k-1层的左孩子与右孩子树就是第k层的结点数

【数据结构】二叉树(链式)

如果k==1,则返回1

如果为NULL,就返回0

//第k层的结点个数 k >= 1
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);
}

✔TreeFind(二叉树查找值为x的值):

依旧不断通过左子树和右子树分别遍历下去

找到等于x的值,就返回那个结点

遇到NULL时,返回NULL

当全部找完依旧没找到,那就返回NULL。

//二叉树查找值为x的值
BTNode* TreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;
	BTNode* ret1 = TreeFind(root->left, x);
	if (ret1)
		return ret1;
	BTNode* ret2 = TreeFind(root->right, x);
	if(ret2)
		return ret2;
		
	return NULL;
}

✔LevelOrder(层序遍历):

这里需要用到队列,队列详细讲解http://t.csdn.cn/vhPtL

  • 先让根节点进入队列
  • 将队头用一个变量保存下来,如果不为NULL就将其打印
  • 再将队头pop一下
  • 当左右节点存在,就将其push进去队列,以此循环

//层序遍历
void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		printf("%d ", front->data);
		QueuePop(&q);
		if (front->left)
			QueuePush(&q, front->left);
		if (front->right)
			QueuePush(&q, front->right);
	}
	printf("\n");
	QueueDestroty(&q);
}

 ✔TreeComplete(判断二叉树是否是完全二叉树):  

这个是建立在层序遍历的基础上的,利用层序遍历,遍历到第一个NULL时,后面都不为NULL才为完全二叉树,如果后面有一个不为NULL,那就不是完全二叉树返回false。文章来源地址https://www.toymoban.com/news/detail-429504.html

// 判断二叉树是否是完全二叉树
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;
		}
		else
		{
			QueuePush(&q,front->left);
			QueuePush(&q,front->right);
		}
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front != NULL)
		{
			QueueDestroty(&q);
			return false;
		}
	}
	QueueDestroty(&q);
	return true;	
}

 ✔TreeDestory(二叉树销毁):

// 二叉树销毁
void TreeDestory(BTNode* root)
{
	if (root == NULL)
		return;
	TreeDestory(root->left);
	TreeDestory(root->right);
	free(root);
 
}

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

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

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

相关文章

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

      个人主页 : 日刷百题 系列专栏 : 〖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)
  • 【数据结构】二叉树的链式存储结构

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

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

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

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

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

    2024年02月08日
    浏览(43)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包