你真的会数据结构吗:二叉树

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

❀❀❀ 文章由@不准备秃的大伟原创 ❀❀❀

♪♪♪ 若有转载,请联系博主哦~ ♪♪♪

❤❤❤ 致力学好编程的宝藏博主,代码兴国!❤❤❤

        halo铁汁们,没错又是你们人见人爱,花见花开的大伟啊,今天也是周六,大伟心情也是非常的美妙啊~ 所以就迫不及待的给大家来更新我们的博客啦,那么今天要学习的内容就是大家早已棋盘不已的二叉树啦,但是在学习二叉树之前,铁汁们有没有把堆认真的学完呢?没有?赶快去看!:堆 

        OK,那么废话不多说,我们开始今天的学习内容吧!

        那么我们上一篇博客也是简单的介绍了一下二叉树的基本概念,那么今天我们就来看一看二叉树的一些操作以及代码的实现。

        首先呢,我们先来思考一下一个很重要的问题:我们的二叉树,用什么方法实现好呢?是数组,还是链式结构?

        回想一下,我们的堆是不是用数组的方法实现的,但是有一点不知道大家有没有注意到大伟上一篇在介绍堆时说的一句话:“堆的逻辑结构是啥样的?和完全二叉树一个样”,也就是说,我们的完全二叉树也就是用和堆一样的实现方法:数组(这样可以保证数据浪费量很小,大家可以想一想为什么)。

        那么问题来了,如果是别的二叉树呢?如果深度比较深,但是最后一层只有一个数据呢?这个时候的空间浪费是不是就是比较大了? 所以,普通的二叉树(当然包括完全二叉树)我们使用链式结构实现就比较银杏。

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

        铁汁们还记得上一篇博客里面我们提到的二叉树是怎么实现的吗?没错,左孩子右兄弟法,于是我们结构体中就需要一个left指针,一个right指针,还需要一个当前节点的数据data。OK,前提需要已经准备好了,现在,开码!

        BT.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef char BTDataType;

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

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树(直接在.c中实现)
BTNode* BTCreate();
// 二叉树销毁
void BinaryTreeDestory(BTNode* root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root,int x);
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root);

        BT.c

                手动创建一个二叉树:

BTNode* BTCreate()
{
	BTNode* n1 = BuyBTNode(1);
	BTNode* n2 = BuyBTNode(2);
	BTNode* n3 = BuyBTNode(3);
	BTNode* n4 = BuyBTNode(4);
	BTNode* n5 = BuyBTNode(5);
	BTNode* n6 = BuyBTNode(6);
	BTNode* n7 = BuyBTNode(7);

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

        逻辑结构如下:你真的会数据结构吗:二叉树,你真的学懂了数据结构?,数据结构,c语言,算法

                销毁二叉树:

void BinaryTreeDestory(BTNode* root)
{
	if (root == NULL) return;
    BinaryTreeDestory(root->left);
    BinaryTreeDestory(root->right);
//从根节点开始,递归释放左右节点
    free(root);
}

                二叉树节点个数: 

int BinaryTreeSize(BTNode* root)
{
//若根不为空,则递归向下找,每到一个节点加一
	return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

                 二叉树叶子节点个数:

int BinaryTreeLeafSize(BTNode* root)
{
//若根为空
	if (root == NULL) return 0;
//若根不为空,但是没有孩子节点,才加一
	if (root && root->left == NULL && root->right == NULL) return 1;
//递归向下寻找
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

                二叉树第k层节点个数:

int BinaryTreeLevelKSize(BTNode* root, int k)
{
//若当前节点为空,则返回为0
	if (root == NULL) return 0;
//若寻找到需要的寻找的层数的某一个节点,则返回1
	if (k == 1) return 1;
//从根依次往下找,并且使的k == 1时,就是需要的层数
	return BinaryTreeLevelKSize(root->left, --k) + BinaryTreeLevelKSize(root->right, --k);
}

                二叉树查找值为x的节点:

BTNode* BinaryTreeFind(BTNode* root,int x)
{
	if (root == NULL) return false;
	if (root->data == x) return root;
//若需要寻找的值不是根节点,则需要记录一下后面的值为x的节点,以便于返回上一层
	BTNode* ret1 = BinaryTreeFind(root->left, x);
	if (ret1) return ret1;

	BTNode* ret2 = BinaryTreeFind(root->right, x);
	if (ret2) return ret2;

return NULL;
}

        铁汁们肯定还不知道前序遍历是个啥玩意吧,哈哈。那么乘次机会,大伟把前序遍历,中序遍历,后序遍历已经层序遍历都给大家讲一讲:

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

1. 前序遍历 —— 访问根结点的操作发生在遍历其左右子树之前。

2. 中序遍历 —— 访问根结点的操作发生在遍历其左右子树之中(间)。

3. 后序遍历 —— 访问根结点的操作发生在遍历其左右子树之后。

4. 层序遍历 —— 从根节点开始按照一层一层的访问节点 

        实例如下图: 你真的会数据结构吗:二叉树,你真的学懂了数据结构?,数据结构,c语言,算法

        前序遍历是: 1 2 4 N N 5 N N 3 6 N N 7 N N

        中序遍历是: N 4 N 2 N 5 N 1 N 6 N 3 N 7 N

        后序遍历是: N N 4 N N 5 2 N N 6 N N 7 3 1

         层序遍历是: 1 2 3 4 5 6 7 N N N N N N N N        

                 二叉树前序遍历 :

        根据逻辑,我们知道每个最小子树,前序遍历都是 左-根-右的方式遍历的,那接下来我们来看看代码:

void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
//先打印当前根节点
	printf("%d ", root->data);
//再向下往左找
	BinaryTreePrevOrder(root->left);
//再向下往右找
	BinaryTreePrevOrder(root->right);

}

                二叉树的中序遍历:

void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
//先从根节点往左找
	BinaryTreeInOrder(root->left);
//等左边最小子树找完了再打印
	printf("%d ", root->data);
//再往右找
	BinaryTreeInOrder(root->right);
}

                二叉树的后序遍历:

void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
//先从根节点往左找
	BinaryTreePostOrder(root->left);
//再找向右找
	BinaryTreePostOrder(root->right);
//等右边最小子树找完了再打印
	printf("%d ", root->data);
}

                二叉树的层序遍历: 

        这个就比较困难了,其实也没有什么很好的方法,不过一般人估计也不会想到,大伟这里就直接给大家答案吧:我们需要借助队列来实现二叉树的层序遍历,那么思路是什么样子的呢?

         其实我们实现层序就是要借助队列的性质:后进先出,我们就先把根节点放进队列,然后放根的左节点,再放右节点,将根打印出来后出队列,将队头出队列,将根改为队列的的头,再进当前队头的左右节点,依次循环,直到队列为空。代码简单(这里就不给队列的一系列的操作了,忘记的,或者想去复习复习的铁汁们点这里 :-> 队列)

void LevelOrder(BTNode* root)
{
	Queue q;
	if (root == NULL)
		return;
//队列初始化
	QueueInit(&q);
//入队列
	QueuePush(&q, root);
//若队列不为空
	while (!QueueEmpty(&q))
	{
		printf("%d\n", QueueFront(&q)->val);

		BTNode* a = root->left;
		BTNode* b = root->right;
//出队列的头
		QueuePop(&q);
//若左不为空
		if (a)
			QueuePush(&q, a);
//若右不为空		
        if (b)
			QueuePush(&q, b);
//若不为空,则根改为当前队列的头
		if (!QueueEmpty(&q))
			root = QueueFront(&q);

	}
}

                 判断二叉树是不是完全二叉树:

        其实我们判断二叉树是不是完全二叉树也有很多办法,但是大伟这里讲一种不是很常见的方法,但是是很容易理解的方法:那就是先假设二叉树是一个完全二叉树,然后通过最后一层所有孩子节点的下标的索引来判断,若有下标索引超过实际二叉树的总节点个数,那么这个二叉树就不是完全二叉树了。代码如下:

bool BinaryTreeComplete(BTNode* root, int index,int n) {
    //n为二叉树的总节点个数
	// 如果当前节点为空,直接返回 true
	if (root == NULL) {
		return true;
	}

	// 如果当前节点的索引超过节点总数,则返回 false
	if (index >= n) {
		return false;
	}

	// 递归检查左子树和右子树
	return BinaryTreeComplete(root->left, 2 * index + 1,n) &&
		BinaryTreeComplete(root->right, 2 * index + 2,n);
}

                OK,到这里我们所有的二叉树的基本操作就写完了,那么接下来,来玩玩?

        test.c

        

int main()
{
	BTNode* root = BTCreate();
//总节点个数
	int n = BinaryTreeSize(root);
    printf("%d\n", n)
//前序
	BinaryTreePrevOrder(root);
	printf("\n");
//中序
	BinaryTreeInOrder(root);
	printf("\n");
//后序
	BinaryTreePostOrder(root);
	printf("\n");
	
	if (BinaryTreeComplete(root, 0,n))
		printf("是完全二叉树");
	else
		printf("不是完全二叉树");
	return 0;
}

        我们来看一看结果:你真的会数据结构吗:二叉树,你真的学懂了数据结构?,数据结构,c语言,算法

        是不是和我们想的一模一样呢~ <(* ̄▽ ̄*)/ 

        其实大伟对递归部分的讲解不是十分详细,但是也是希望铁汁们能好好理解,其实我们学到这里最重要的还是代码的练习量,所以当铁汁们没事做的时候,多刷刷题,多理解理解,O不O K?

         到这里本篇博客已经可以是完结了,接着二叉树后面就是排序了,在紧接着就进入c++啦,下篇文章我会对大家介绍数据结构初阶的最后一个内容,请大家继续支持大伟,谢啦!!☆⌒(*^-゜)v 

        ·你要做一个不动声色的大人了。不准情绪化,不准偷偷想念,不准回头看。去过自己另外的生活。你要听话,不是所有的鱼都会生活在同一片海里。---村上春树

        本篇博客也就到此为止了,送大家一碗鸡汤,勉励自己以及这世界上所有追逐梦想的赤子趁年华尚好努力提升自己,莫欺少年穷! 你真的会数据结构吗:二叉树,你真的学懂了数据结构?,数据结构,c语言,算法文章来源地址https://www.toymoban.com/news/detail-856006.html

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

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

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

相关文章

  • 【数据结构和算法】--- 二叉树(3)--二叉树链式结构的实现(1)

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

    2024年01月25日
    浏览(63)
  • 【数据结构】二叉树——链式结构

    目录  一、前置声明 二、二叉树的遍历 2.1 前序、中序以及后序遍历 2.2 层序遍历 三、节点个数以及高度 3.1 节点个数 3.2 叶子节点个数 3.3 第k层节点个数 3.4 二叉树的高度/深度 3.5 查找值为x的节点 四、二叉树的创建和销毁 4.1 构建二叉树 4.2 二叉树销毁 4.3 判断二叉树

    2024年02月16日
    浏览(47)
  • 【数据结构】二叉树——顺序结构

    由于每个节点都 只有一个父节点 ,所以我们可通过双亲来表示一棵树。具体方式通过 数组的形式 实现。 根节点的下标为0 按照层序从上到下排序 每层从左向右递增 表示形式: 二维数组 数据的列标为0 ,只需确定行标,即可锁定位置 根节点的父节点下标为 -1 列标为1存父节

    2024年02月02日
    浏览(56)
  • 数据结构-二叉树-二叉树左右孩子交换(递归)

     注:本文采用队列和递归的算法进行创建和层次遍历。同时不能采用BFS和DFS,因为需要把当前根节点的左孩、右孩勾链并输入才能递归下一个根节点; 队列用于存储此时应该递归的根节点; 格式:每一行尾不能有空格; Description 根据输入利用二叉链表创建二叉树,并将所

    2024年02月04日
    浏览(50)
  • 【数据结构】二叉树链式结构

    🚀write in front🚀 📜所属专栏:初阶数据结构 🛰️博客主页:睿睿的博客主页 🛰️代码仓库:🎉VS2022_C语言仓库 🎡您的点赞、关注、收藏、评论,是对我最大的激励和支持!!! 关注我,关注我,关注我 , 你们将会看到更多的优质内容!!   在之前的二叉树的顺序结

    2024年02月03日
    浏览(41)
  • 【数据结构】 二叉树理论概念!一文了解二叉树!

    🎥 屿小夏 : 个人主页 🔥个人专栏 : 数据结构解析 🌄 莫道桑榆晚,为霞尚满天! 什么是二叉树?二叉树的组成构造是什么样的?我们将由浅入深,循序渐进的方式把二叉树给搞明白,让你彻底了解二叉树! 树是一种非线性的数据结构,它是由n(n=0)个有限结点组成一

    2024年02月05日
    浏览(48)
  • 【数据结构】二叉树的介绍和二叉树堆

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

    2024年01月20日
    浏览(52)
  • 数据结构之二叉树和平衡二叉树

    1、二叉树: 2、平衡二叉树:

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

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

    2024年02月07日
    浏览(42)
  • 深入理解数据结构第三弹——二叉树(3)——二叉树的基本结构与操作

    二叉树(1): 深入理解数据结构第一弹——二叉树(1)——堆-CSDN博客 二叉树(2): 深入理解数据结构第二弹——二叉树(2)——堆排序及其时间复杂度-CSDN博客 前言: 在前面我们讲了堆及其应用,帮助我们初步了解了二叉树的一些原理,但那与真正的二叉树仍有不同,

    2024年04月09日
    浏览(49)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包