数据结构---二叉树(C语言)

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

数据结构---二叉树(C语言)

1. 二叉树

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

1.1 二叉树的遍历

从二叉树的定义来看,二叉树是递归定义的,因此我们可以用递归的形式来遍历二叉树。

1.1.1二叉树前中后序遍历(递归版)

访问根结点的顺序不同。

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


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


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

1.1.2 层序遍历

层序遍历是按照二叉树的高度,一层一层遍历,需要借助队列来完成。但是C语言没有这样的数据结构,需要我们自己来提前写一个。(本例子不提供队列的实现)文章来源地址https://www.toymoban.com/news/detail-460270.html

//层序遍历
void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	//根节点入队
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		//先获取队首元素,再出队,左右孩子不为空,入队
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front->left)
		{
			QueuePush(&q, front->left);
		}
		if (front->right)
		{
			QueuePush(&q, front->right);
		}
		printf("%d ", front->data);

	}
	QueueDestroy(&q);

}

1.2 二叉树的其他相关接口

1.2.1 求二叉树的结点数量

//求二叉树的结点数量
int NodeSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	return 1+NodeSize(root->left)+NodeSize(root->right);
}

1.2.2 求叶子结点个数

//求叶子结点个数
int LeafSize(BTNode* root)
{
	//防止空树
	if (root == NULL)
		return 0;
	//是叶子
	if (root->left == NULL && root->right == NULL)
		return 1;
	//不是叶子
	return 	LeafSize(root->left)+LeafSize(root->right);
}

1.2.3 求树高

//求树高
int TreeDepth(BTNode* root)
{
	//避免空树
	if (root == NULL)
		return 0;
	int depth_left = 1 + TreeDepth(root->left);
	int depth_right = 1 + TreeDepth(root->right);
	return depth_left > depth_right ? depth_left : depth_right;
}

1.2.4 求第k层结点个数

//求第k层结点个数
int BinaryTreeLevelKSize(BTNode* root,int k)
{
	//空树
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1; 
	int count = BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
	return count;
}

1.2.5 查找二叉树值为k的结点

//查找二叉树值为x的结点
BTNode* BinaryTreeFind(BTNode* root, int x)
{
	//防止二叉树为空
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;
	BTNode* ret1 = BinaryTreeFind(root->left, x);
	if (ret1 != NULL)
		return ret1;
	BTNode* ret2 = BinaryTreeFind(root->right, x);
	if (ret2 != NULL)
		return ret2;

	return NULL;
}

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

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

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

相关文章

  • [数据结构 -- C语言] 二叉树(BinaryTree)

    目录 1、树的概念及结构 1.1 树的概念 1.2 树的相关概念(很重要) 1.3 树的表示 2、二叉树的概念及结构 2.1 概念 2.2 特殊二叉树 2.3 二叉树的性质(很重要) 2.4 练习题 2.5 二叉树的存储结构 2.5.1 顺序存储 2.5.2 链式存储 3、二叉树的顺序结构及实现 3.1 二叉树的顺序结构 3.2 堆的

    2024年02月16日
    浏览(45)
  • 【数据结构初阶】八、非线性表里的二叉树(二叉树的实现 -- C语言链式结构)

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】七、非线性表里的二叉树(堆的实现 -- C语言顺序结构)-CSDN博客  ==========

    2024年02月08日
    浏览(48)
  • 二叉树的实现(C语言数据结构)

    目录 一、以下是我们需要实现的功能 二、以下是我们具体功能的实现 1.创建新的结点 2.通过数组生成二叉树  3.先序遍历 4.中序遍历 5.后序遍历   6.层序遍历 7.计算二叉树的结点个数 8.查找指定值为x的结点 9.查找第K层的结点个数 10.统计二叉树叶子结点的个数 11.判断是否为

    2024年02月04日
    浏览(36)
  • 【C语言 数据结构】堆与二叉树(下)

    接着上次的,这里主要介绍的是堆排序,二叉树的遍历,以及之前讲题时答应过的简单二叉树问题求解 给一组数据,升序(降序)排列 思路 思考:如果排列升序,我们应该建什么堆? 首先,如果 排升序 ,数列最后一个数是 最大数,我们的思路是通过 向上调整 或者 向下调

    2024年01月19日
    浏览(47)
  • 【C语言 数据结构】二叉树的遍历

    所谓先序遍历二叉树,指的是从根结点出发,按照以下步骤访问二叉树的每个结点: 访问当前结点; 进入当前结点的左子树,以同样的步骤遍历左子树中的结点; 遍历完当前结点的左子树后,再进入它的右子树,以同样的步骤遍历右子树中的结点; 先序遍历这棵二叉树的过

    2024年02月04日
    浏览(42)
  • c语言数据结构——树形结构之树和二叉树

    二叉树有什么用? 二叉树应用非常广泛。 在操作系统源程序中,树和森林被用来构造文件系统。我们看到的window和linux等文件管理系统都是树型结构。在编译系统中,如C编译器源代码中,二叉树的中序遍历形式被用来存放C 语言中的表达式。其次二叉树本身的应用也非常多,

    2023年04月18日
    浏览(41)
  • 数据结构入门(C语言版)二叉树链式结构的实现

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

    2023年04月23日
    浏览(46)
  • 数据结构入门(C语言版)二叉树概念及结构(入门)

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

    2023年04月14日
    浏览(40)
  • 【数据结构】二叉树OJ题(C语言实现)

    ✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅ ✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨ 🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿 🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟 🌟🌟 追风赶月莫停留 🌟🌟 🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀 🌟🌟 平芜尽处是春山

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

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

    2023年04月21日
    浏览(43)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包