【数据结构与算法】二叉树的深度,节点数,第k层的节点数,遍历,二叉树叶节点的个数

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

【数据结构与算法】二叉树的深度,节点数,第k层的节点数,遍历,二叉树叶节点的个数 

 文章来源地址https://www.toymoban.com/news/detail-402187.html

目录

一.前言

二.二叉树的节点数

二.二叉树的深度

三.二叉树第k层的节点数

四.二叉树的遍历

1.前序遍历

2.中序遍历

3.后序遍历

总结

4.层序遍历

五.二叉树叶节点的个数


一.前言

我们需要先构建个二叉树,方便后续对函数的测试;

还有我们在实现二叉树的这些函数时,尽量少用遍历,这里用的比较多的就是递归和分治思想。

typedef int Tdatatype;

typedef struct Tree
{
	Tdatatype data;
	struct Tree* left;
	struct Tree* right;
}Tree;

Tree* BuyTree(Tdatatype x)
{
	Tree* node = (Tree*)malloc(sizeof(Tree));
	if (node == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	node->data = x;
	node->left = NULL;
	node->right = NULL;

	return node;
}

Tree* CreateTree()    //这里可以自由操控二叉树的构建
{
	Tree* node1 = BuyTree(1);
	Tree* node2 = BuyTree(2);
	Tree* node3 = BuyTree(3);
	Tree* node4 = BuyTree(4);
	Tree* node5 = BuyTree(5);
	Tree* node6 = BuyTree(6);
	Tree* node7 = BuyTree(7);
	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node2->right = node7;
	node4->left = node5;
	node4->right = node6;

	return node1;

}

二.二叉树的节点数

二叉树的节点数=左子树的节点数+右子树的节点数

1.如果root==NULL,则返回0;

2.否则递归调用它的左子树和右子树;

3.然后+1;

详细请看递归调用图:

【数据结构与算法】二叉树的深度,节点数,第k层的节点数,遍历,二叉树叶节点的个数

 

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

二.二叉树的深度

还是利用分治的思想;

1.分别算出左子树和右子树的深度

2.然后比较二者的大小,大的返回

3.不要忘了+1,因为根节点也算是一个深度。

int TreeHeight(Tree* root)
{
	if (root == NULL)   //为空则返回0
		return 0;
	int left = TreeHeight(root->left);  //要用left记录下其返回值,防止多次重复调用,right同
	int right = TreeHeight(root->right);

	return left > right ? left + 1 : right + 1;
}

三.二叉树第k层的节点数

二叉树第k层的节点数=左子树的第k-1层的节点数+右子树第k-1层的节点数

因为二叉树没有第0层,是从第一层开始的,所以k==1时,返回1

int TreeLevel(Tree* root, int k)
{
	if (root == NULL)  //为空则返回0
		return 0;
	if (k == 1)
		return 1;

	int left = TreeLevel(root->left, k - 1);   //左子树第k-1层节点数
	int right = TreeLevel(root->right, k - 1);  //右子树第k-1层节点数

	return left + right;
	
}

四.二叉树的遍历

1.前序遍历

前序遍历:

1.先访问根节点;

2.然后访问左节点;

3.最后访问右节点;

4.如果节点为空,则结束此次递归调用。

void PreOrder(Tree* root)
{
	if (root == NULL)
		return;
	printf("%d  ", root->data);
	PreOrder(root->left);  //访问左节点
	PreOrder(root->right);  //访问右节点
}

2.中序遍历

中序遍历:

1.先访问左节点;

2.然后访问根节点;

3.最后访问右节点;

4.如果节点为空,则结束此次递归调用。

void InOrder(Tree* root)
{
	if (root == NULL)
		return;

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

3.后序遍历

后序遍历:

1.先访问左节点;

2.然后访问右节点;

3.最后访问根节点;

4.如果节点为空,则结束此次递归调用。

void PostOrder(Tree* root)
{
	if (root == NULL)
		return;

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

总结

通过以上代码我们发现:

1.假设前序,中序,后序分别为1,2,3;

2.是哪个序遍历,就按照那个顺序访问根节点,左节点永远在右节点前面;

3.递归也是按照这个顺序。

4.层序遍历

层序遍历就需要用到队列了

1.先入一个节点进队列,此时队列不为空;

2。然后出一个节点,然后删除队列里的一个元素,如果左节点和右节点不为空的话,入它的左节点和右节点;

3.队列为空时跳出循环

【数据结构与算法】二叉树的深度,节点数,第k层的节点数,遍历,二叉树叶节点的个数

 

void LevelOrder(Tree* root)
{
    //创建一个队列,并初始化
	Queue q;
	Queueinit(&q);

	if (root)
		Queuepush(&q, root);
	while (!Queueempty(&q))
	{
		Tree* front = Queuefront(&q);   //出一个数据
		Queuepop(&q);
		printf("%d  ", front->data);

		if (front->left)
			Queuepush(&q,front->left);  //入它的左节点
		if (front->right)
			Queuepush(&q, front->right);  //入它的右节点
	}

	Queuedestroy(&q);  //不要忘记销毁队列
}

五.二叉树叶节点的个数

叶节点就是没有子节点的节点,我们可以分别记录下当前节点的左节点和右节点,如果都为空,那么叶节点的个数+1。

int BinaryTreeLeafSize(Tree* root)
{
	Tree* left = root->left;
	Tree* right = root->right;
	if (left == NULL && right == NULL)
	{
		return 1;
	}
	else
	{
		BinaryTreeLeafSize(root->left);
		BinaryTreeLeafSize(root->right);
	}
}

🐬🤖本篇文章到此就结束了,若有错误或是建议的话,欢迎小伙伴们指出;🕊️👻

😄😆希望小伙伴们能支持支持博主啊,你们的支持对我很重要哦;🥰🤩

😍😁谢谢你的阅读。😸😼

【数据结构与算法】二叉树的深度,节点数,第k层的节点数,遍历,二叉树叶节点的个数

 

到了这里,关于【数据结构与算法】二叉树的深度,节点数,第k层的节点数,遍历,二叉树叶节点的个数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 数据结构与算法-二叉树的遍历

    🌞 “少年没有乌托邦,心向远方自明朗!” 二叉树的遍历是按照一定次序访问二叉树中的所有结点,且每个结点仅被访问一次的过程。遍历线性结构是容易解决的,而二叉树的结构是非线性结构,需要寻找规律,使二叉树的结点排列在一个线性队列上,便于遍历。 由二叉树

    2024年02月08日
    浏览(46)
  • 【数据结构】二叉树的遍历递归算法详解

    我们来写一个函数 BuyNode(x)函数 用于创建二叉树结点。 用动态开辟函数 malloc 函数进行动态开辟,并强制转换为 BTNode 型,用变量 node 来去管理开辟的空间。 我们初始化结点,其 val 即为传入的参数x,左右指针 left 和 right 都设为NULL。 我们在主函数中创建上面这样一颗二叉树

    2024年01月20日
    浏览(46)
  • 【数据结构和算法15】二叉树的实现

    二叉树是这么一种树状结构:每个节点最多有两个孩子,左孩子和右孩子 重要的二叉树结构 完全二叉树(complete binary tree)是一种二叉树结构,除最后一层以外,每一层都必须填满,填充时要遵从先左后右 平衡二叉树(balance binary tree)是一种二叉树结构,其中每个节点的左

    2024年02月16日
    浏览(35)
  • 【数据结构与算法】二叉树的知识讲解

    目录  一,二叉树的结构深入认识  二,二叉树的遍历  三,二叉树的基本运算 3-1,计算二叉树的大小 3-2,统计二叉树叶子结点个数 3-3,计算第k层的节点个数 3-4,查找指定值的结点         二叉树是不可随机访问的,二叉树的结构是通过双亲结点与孩子结点之间的连接进

    2024年02月08日
    浏览(41)
  • 【数据结构】【算法】二叉树、二叉排序树、树的相关操作

    树结构是以分支关系定义的一种层次结构,应用树结构组织起来的数据,逻辑上都具有明显的层次关系。 操作系统中的文件管理系统、网络系统中的域名管理、数据库系统中的索引管理等都使用了树结构来组织和管理数据。 树 Tree 是由n个节点组成的有限集合。在任意一颗非

    2024年02月04日
    浏览(54)
  • 数据结构和算法学习记录——平衡二叉树(基本介绍、平衡因子、平衡二叉树的定义、平衡二叉树的高度)

    目录 基本介绍 平衡因子 平衡二叉树  平衡二叉树的高度  什么是平衡二叉树? 以一个例子来解释一下: 搜索树结点按不同的插入次序,将会导致不同的深度和平均查找长度ASL   在二叉搜索树中查找一个元素:  (a)要找到Jan,需要查找一次;要找到Feb,需要查找两次;

    2023年04月26日
    浏览(66)
  • 【数据结构与算法】力扣:二叉树的层序遍历

    给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。 示例1: 输入:root = [3,9,20,null,null,15,7] 输出:[[3],[9,20],[15,7]] 示例 2: 输入:root = [1] 输出:[[1]] 示例 3: 输入:root = [] 输出:[] 来源:力扣(LeetCode) 链接:https://leetcode.cn/p

    2024年02月13日
    浏览(47)
  • 数据结构上机实验——二叉树的实现、二叉树遍历、求二叉树的深度/节点数目/叶节点数目、计算二叉树度为1或2的节点数、判断二叉树是否相似

       建立一棵二叉树,试编程实现二叉树的如下基本操作。    1.创建一棵一棵二叉算法。    2.对这棵二叉树进行遍历:先序或中序或后序,分别输出结点的遍历序列。    3.求二叉树的深度/节点数目/叶节点数目。(选做一个)    4.计算二叉树中度为1 的结点数;

    2024年02月06日
    浏览(62)
  • 数据结构与算法----详解二叉树的遍历(迭代、递归)

    ❤️ 作者简介 :大家好我是小鱼干儿♛是一个热爱编程、热爱算法的大三学生,蓝桥杯国赛二等奖获得者 🐟 个人主页 :https://blog.csdn.net/qq_52007481 ⭐ 个人社区 :【小鱼干爱编程】 🔥 算法专栏 :算法竞赛进阶指南 💯 刷题网站 :虽然市面上有很多的刷题网站,但是里面

    2024年01月24日
    浏览(54)
  • Java 数据结构篇-二叉树的深度优先遍历(实现:递归方式、非递归方式)

    🔥博客主页: 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍    文章目录         1.0 二叉树的说明         1.1 二叉树的实现         2.0 二叉树的优先遍历说明         3.0 用递归方式实现二叉树遍历         3.1 用递归方式实现遍历 - 前序遍历         3.2 用递归

    2024年02月05日
    浏览(53)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包