14-数据结构-二叉树的创建以及前中后遍历,以及结点和叶子节点的计算(C语言)

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

概述:

        二叉树,这里采用孩子链表存储法,即一个数据域和两个左右孩子指针域。随后递归进行遍历即可。在创建二叉树的时候,先创建各个二叉树结点(这里的结点采用动态分配,因此结点为指针变量),随后,再根据逻辑结构图,手动通过左右指针域,链接到对应位置即可。

代码如下:

#include <stdio.h>
#include <string.h>
#include <stdlib.h> 
//二叉树结点 
typedef struct BTnode
{
	int data;
	struct BTnode *lchild,*rchild;
}BTnode;

BTnode* BuyNode(int x)
{
	//创建树的结点空间,动态分配。 
	BTnode* node =(BTnode*)malloc(sizeof(BTnode));
	//给结点赋值,指针域置空 
	node->data=x;
	node->lchild=NULL;
	node->rchild=NULL;
	return node; 
} 
//创建二叉树
BTnode* CreatTree()
{
	//创建树的结点 
	BTnode* node1 =BuyNode(1);//因为BuyNode是动态分配的空间,因此用指针接收	
	BTnode* node2 =BuyNode(2);
	BTnode* node3 =BuyNode(3);
	BTnode* node4 =BuyNode(4);
	BTnode* node5 =BuyNode(5);
	//手动链接起来。
	node1->lchild=node2;
	node1->rchild=node3;
	node2->lchild=node4;
	node2->rchild=node5; 
	
	//链接完毕,返回头指针,即根结点
	return node1; 
} 
//打印树-前序遍历 
void PreOrder(BTnode* root)
{
	if(root == NULL)
	{
		printf("# ");
		return;//返回调用的上一级 
	}
	printf("%d ",root->data);
	PreOrder(root->lchild);
	PreOrder(root->rchild);
} 
void InOrder(BTnode* root)//中序遍历 
{
	if(root == NULL)
	{
		printf("# ");
		return;//返回调用的上一级 
	}
	
		
		InOrder(root->lchild);  //左 
		printf("%d ",root->data);//根 
		InOrder(root->rchild);//右 
	
} 
void PostOrder(BTnode* root)//后序遍历 
{
	if(root == NULL)
	{
		printf("# ");
		return;//返回调用的上一级 
	}
	
		PostOrder(root->lchild);//左 
		PostOrder(root->rchild);// 右 
		printf("%d ",root->data);//根 
	
} 
//计算树的结点,分治思想,分工,最后汇总。
int BTtreeSize(BTnode* root)
{
	if(root ==NULL)//树是空的,就返回0 
	return 0;
	else//不是空的,就进行左右子树遍历再加1,因为要给本身加上。空根不加一,但这里非空,必定+1; 
	{
		//递归到叶子节点时,叶子节点的左右子树都为空,返回0,0+0+1=1,因此叶子节点再往上一层返回即可。 
		return	BTtreeSize(root->lchild)+BTtreeSize(root->rchild)+1;	
	}	
} 
//计算树的叶子节点
int LeafSizes(BTnode* root)
{
	//是空根就返回0
	if(root ==NULL)
	return 0;
	//符合叶子结点特征,即结点的左右子树均为空,则返回1,即记录上 
	if(root->lchild ==NULL && root->rchild==NULL )
	return 1;
	else
	//都不符合,便进入左右子树,进行递归计算,最后汇总即可。 
	return LeafSizes(root->lchild)+LeafSizes(root->rchild);	
	//实在不明白,画个递归图,就明白了。 
} 

int main()
{
	BTnode* root=CreatTree();
	//遍历递归打印时,每个结点调用结束,销毁空间,返回上一级调用位置。
	//直到所有结点遍历结束,临时空间逐个销毁。 
	printf("前序遍历:");
	PreOrder(root);
	printf("\n中序遍历:");
	InOrder(root);
	printf("\n后序遍历:");
	PostOrder(root); 
	//计算树的结点 
	int count=BTtreeSize(root);
	printf("\n树有%d个结点",count);
	int leafcount=LeafSizes(root);
	printf("\n树有%d个叶子结点",leafcount);
	return 0;
 } 

结果:
14-数据结构-二叉树的创建以及前中后遍历,以及结点和叶子节点的计算(C语言),数据结构笔记(C语言),数据结构,算法

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

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

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

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

相关文章

  • 【数据结构】二叉树的相关操作以及OJ题目

    当一个树不是满二叉树或完全二叉树时,它是不适合使用数组存储的,它应该使用链式结构来存储。 再看二叉树基本操作前,再回顾下二叉树的概念,二叉树是: 空树 非空:根节点,根节点的左子树、根节点的右子树组成的。 从概念中可以看出,二叉树定义是递归式的,因

    2024年03月19日
    浏览(47)
  • 【数据结构】树二叉树的概念以及堆的详解

    ✨链接1:【数据结构】顺序表 ✨链接2:【数据结构】单链表 ✨链接3:【数据结构】双向带头循环链表 ✨链接4:【数据结构】栈和队列 百度百科的解释 :树是一种 非线性 的数据结构,它是由n(n≥0)个有限节点组成一个具有层次关系的集合。 把它叫做树是因为它看起来像

    2024年02月16日
    浏览(37)
  • 【数据结构】二叉树的创建和四种遍历(附带详细注释)

    《数据结构系列首页》是数据结构系列文章的首页,其中会 逐步更新 各种数据结构的实现,有兴趣的选手可以一看。 首页中不仅有各种数据结构的实现,还有学习数据结构 必备的基础知识 ,如果有选手觉得自己的基础不太牢固,可以先将搞定基础知识,之后再攻克数据结

    2024年02月05日
    浏览(67)
  • 【数据结构】16 二叉树的定义,性质,存储结构(以及先序、后序、中序遍历)

    一个二叉树是一个有穷的结点集合。 它是由根节点和称为其左子树和右子树的两个不相交的二叉树组成的。 二叉树可具有以下5种形态。 一个二叉树第i层的最大结点数为 2 i − 1 2^{i-1} 2 i − 1 , i ≥ 1 i geq 1 i ≥ 1 每层最大结点可以对应完美二叉树(满二叉树),其所有分支结

    2024年02月20日
    浏览(43)
  • 【数据结构】树、二叉树的概念和二叉树的顺序结构及实现

    之前我们学习了顺序表、链表以及栈和队列这些数据结构,但这些数据结构都是线性的(一对一)。接下来要学习 非线性的数据结构——树(二叉树) ,相比前面的,树的结构更加复杂,话不多说,直接进入正题吧。 树是一种 非线性的数据结构 ,它是 一对多(也有可能是

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

    朋友们、伙计们,我们又见面了,本期来给大家解读一下链式二叉树的相关知识点,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! 数据结构与算法专栏 :数据结构与算法 个  人  主  页 :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日
    浏览(51)
  • 数据结构与算法学习:二叉树的后序遍历的递归与非递归实现,以及非递归实现中的流程控制的说明。

    需求二叉树: 采用二叉树后序遍历非递归算法。设置一个指针p初始指向树根,p先入栈,而后使得p指向它的左孩子p-firstchild,重复操作,使得每个左孩子都依次入栈,同时初始化一个Treenode*类型的指针 pre,这个指针是后序前驱,这个后序前驱用以区分为已访问过的结点和未

    2023年04月22日
    浏览(47)
  • 【数据结构】二叉树的介绍和二叉树堆

    💓作者简介: 加油,旭杏,目前大二,正在学习 C++ , 数据结构 等👀 💓作者主页:加油,旭杏的主页👀 ⏩本文收录在:再识C进阶的专栏👀 🚚代码仓库:旭日东升 1👀 🌹欢迎大家点赞 👍 收藏 ⭐ 加关注哦!💖        树这一概念,在我们刚开始听说的时候会觉得

    2024年01月20日
    浏览(49)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包