【数据结构】二叉树的销毁 & 二叉树系列所有源代码(终章)

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

目录

一,二叉树的销毁 

二,二叉树系列所有源代码

BTee.h

BTee.c

Queue.h

Queue.c


一,二叉树的销毁 

【数据结构】二叉树的销毁 & 二叉树系列所有源代码(终章),数据结构,开发语言,算法,c语言,排序算法

二叉树建好了,利用完了,也该把申请的动态内存空间给释放了,那要如何释放呢?

【数据结构】二叉树的销毁 & 二叉树系列所有源代码(终章),数据结构,开发语言,算法,c语言,排序算法

我们还是以这棵树为例,要把这棵树销毁掉,其实就是把树上的结点全部释放掉,但是呢这个释放的顺序挺讲究的,对于树,我们的思想首先就是,前序遍历,中序遍历,后序遍历,层序遍历的思想,那这棵树到底用什么思想好呢?

我们先来分析一下,要释放以(1)为根结点的树就相当于释放左子树(2)和右子树(4)和自身的结点,然后呢以(2),(4)为根结点的树也是同理,层层递归下去,这不就符合后序遍历的思想吗,先左子树-->右子树-->根结点!所以销毁这棵树的思路就是后序遍历的思路

既然思路已经确定了,我们就要开始实现了!

大事化小:先释放结点的左子树,再释放其右子树然后在释放本身结点!

结束条件:当结点为空时返回 NULL ;

源代码

//二叉树的销毁
void BinaryTreeDestory(BTNode* root)
{
    //判空
	if (root == NULL)
	{
		return NULL;
	}
    //释放左子树
	BinaryTreeDestory(root->left);
    //释放右子树
	BinaryTreeDestory(root->right);
    //释放本身结点
	free(root);
}

 这就 ok 了,只要捋清楚思路了,就很简单了;

【数据结构】二叉树的销毁 & 二叉树系列所有源代码(终章),数据结构,开发语言,算法,c语言,排序算法

经过了9个阶段的学习,二叉树的初阶部分也是迎来了结尾,为什么说是初阶部分呢?因为一些更复杂的树的内容不太方便用 c 语言来讲解展示,等后面博主介绍完了 c++ 再来絮叨絮叨,同志们莫急,革命的道路还需一步一步向前走!

【数据结构】二叉树的销毁 & 二叉树系列所有源代码(终章),数据结构,开发语言,算法,c语言,排序算法

二,二叉树系列所有源代码

我们总共历经了九个阶段的学习,二叉树已是随便拿捏了!下面是这九个阶段以及二叉树初阶部分的所以源代码:

BTee.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>

typedef int BTDataType;
//二叉链
typedef struct BinaryTreeNode
{
	BTDataType data; // 当前结点值域	
	struct BinaryTreeNode* left; // 指向当前节点左孩子
	struct BinaryTreeNode* right; // 指向当前节点右孩子
}BTNode;

//动态创立新结点
BTNode* BuyNode(BTDataType x);
//创建二叉树
BTNode* GreatBTree();
//前序遍历
void PrevOrder(BTNode* root);
//中序遍历
void InOrder(BTNode* root);
//后序遍历
void PostOrder(BTNode* root);
//结点个数
int	SumNode(BTNode* root);
//叶子结点个数
int LeafNode(BTNode* root);
//二叉树高度
int HeightTree(BTNode* root);
//二叉树第k层结点个数
int BTreeLeveSize(BTNode* root, int k);
//二叉树查找值为x的结点
BTNode* BTreeFine(BTNode* root, int x);
//层序遍历
void LevelOrder(BTNode* root);
//二叉树的销毁
void BinaryTreeDestory(BTNode* root);
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BTCreate(BTDataType* a,int* i);
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root);

BTee.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"BTree.h"
#include"Queue.h"
//动态创立新结点
BTNode* BuyNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	assert(newnode);
	newnode->data = x;
	newnode->left = NULL;
	newnode->right = NULL;
	return newnode;
}

//创建二叉树
BTNode* GreatBTree()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);

	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;

	return node1;
}

//前序遍历
void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	printf("%c ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}

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

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

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


//结点个数
int SumNode(BTNode* root)
{
	return root == NULL ? 0 : SumNode(root->left) + SumNode(root->right) + 1;
}

//叶子结点个数
int LeafNode(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left==NULL && root->right==NULL)
	{
		return 1;
	}
	else
	{
		return LeafNode(root->left) + LeafNode(root->right);
	}
}

//二叉树高度
int HeightTree(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int left = HeightTree(root->left);
	int right = HeightTree(root->right);
	return left > right ? left + 1 : right + 1;
}

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

//二叉树查找值为x的结点
BTNode* BTreeFine(BTNode* root, int x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	if (BTreeFine(root->left, x) == NULL)
	{
		return BTreeFine(root->right, x);
	}
	else
	{
		return BTreeFine(root->left, x);
	}
}

//层序遍历
void LevelOrder(BTNode* root)
{
	Queue q;
	// 初始化队列 
	QueueInit(&q);
	// 队尾入队列 
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q)->data);
		BTNode* cur = QueueFront(&q);
		// 队头出队列
		QueuePop(&q);
		if (cur->left)
		{
			QueuePush(&q, cur->left);
		}
		if (cur->right)
		{
			QueuePush(&q, cur->right);
		}
	}
}

//二叉树的销毁
void BinaryTreeDestory(BTNode* root)
{
	//判空
	if (root == NULL)
	{
		return NULL;
	}
	//释放左子树
	BinaryTreeDestory(root->left);
	//释放右子树
	BinaryTreeDestory(root->right);
	//释放本身结点
	free(root);
}

void _BinaryTreeCreate(BTNode* node, BTDataType* a,int* pi)
{
	if (node == NULL)
	{
		return;
	}
	node->left= BuyNode(a[(*pi)++]);
	node->right= BuyNode(a[(*pi)++]);
}

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
	if (a == NULL)
	{
		return NULL;
	}
	BTNode* node1= BuyNode(a[(*pi)++]);
	_BinaryTreeCreate(node1, a, pi);
	return node1;
}

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BTCreate(BTDataType* arr, int*i)
{
	if (arr[(*i)] == '#')
	{
		(*i)++;
		return NULL;
	}
	BTNode* root = BuyNode(arr[(*i)++]);
	root->left = BTCreate(arr, i);
	root->right = BTCreate(arr, i);
	return root;
}

// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{
	Queue q;
	// 初始化队列 
	QueueInit(&q);
	// 队尾人队列 
	QueuePush(&q,root);
	while(QueueFront(&q))
	{
		BTNode* cur = QueueFront(&q);
		// 队头出队列 
		QueuePop(&q);
		QueuePush(&q, cur->left);
		QueuePush(&q, cur->right);
	}
	while (!QueueEmpty(&q))
	{
		// 队头出队列 
		QueuePop(&q);
		if (QueueFront(&q) != NULL)
		{
			BinaryTreeDestory(root);
			return 0;
		}
	}
	return 1;
}

下面是【栈】的源代码,二叉树的层序遍历用的着,这边也发给大家了:

Queue.h

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include"BTree.h"

typedef BTNode* QDataType;
//结点
typedef struct QListNode
{
	struct QListNode* next;
	QDataType data;
}QNode;

// 队列
typedef struct Queue
{
	QNode* front; // 队头
	QNode* rear; //队尾
	int size;
}Queue;

// 初始化队列 
void QueueInit(Queue* q);
// 队尾人队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 判空
int QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);

Queue.c

#define _CRT_SECURE_NO_WARNINGS 1
#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"

// 初始化队列 
void QueueInit(Queue* q)
{
	assert(q);
	q->front = q->rear = NULL;
	q->size = 0;
}

// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	newnode->next = NULL;
	newnode->data = data;
	if (q->front /*= q->rear*/ == NULL)//谨记判断不要用此等格式
	{
		q->front = q->rear = newnode;
	}
	else
	{
		q->rear->next = newnode;
		q->rear = newnode;
	}
	q->size++;
}
// 队头出队列 
void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	if (q->front->next == NULL)
	{
		free(q->front);
		q->front = q->rear = NULL;
	}
	else
	{
		QNode* next = q->front->next;
		free(q->front);
		q->front = next;
	}
	q->size--;
}
// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->front->data;
}
// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->rear->data;
}
// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
	assert(q);
	return q->size;
}
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0 
int QueueEmpty(Queue* q)
{
	assert(q);
	return q->size == 0;
}
// 销毁队列 
void QueueDestroy(Queue* q)
{
	assert(q);

	QNode* cur = q->front;
	QNode* next = NULL;
	while (cur)
	{
		next = cur->next;
		free(cur);
		cur = next;
	}
	cur = NULL;
	q->rear = NULL;
}

同志们!二叉树(初阶)的知识就到这了,加油!

【数据结构】二叉树的销毁 & 二叉树系列所有源代码(终章),数据结构,开发语言,算法,c语言,排序算法

二叉树(初阶)阶段就到这里了;

后面博主会陆续更新;

如有不足之处欢迎来补充交流!

完结。。文章来源地址https://www.toymoban.com/news/detail-717204.html


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

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

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

相关文章

  • 【数据结构】二叉树的介绍和二叉树堆

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

    2024年01月20日
    浏览(52)
  • 【数据结构】树,二叉树,满二叉树,完全二叉树的定义和二叉树的基本操作

    🎊专栏【数据结构】 🍔喜欢的诗句:更喜岷山千里雪 三军过后尽开颜。 🎆音乐分享【勋章】 大一同学小吉,欢迎并且感谢大家指出我的问题🥰 目录 ⭐树 🏳️‍🌈定义  🏳️‍🌈注意 🍔树的基本术语 ⭐二叉树 🏳️‍🌈定义 🎆二叉树和树的区别 🏳️‍🌈二叉树

    2024年02月05日
    浏览(70)
  • 【数据结构】二叉树的链式存储结构

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

    2024年02月09日
    浏览(45)
  • 【数据结构】二叉树的概念及结构

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

    2023年04月23日
    浏览(43)
  • 【数据结构】二叉树的顺序结构-堆

    普通的二叉树是不适合用数组来存储的,因为可能会存在大量的空间浪费。而 完全二叉树 更适合使用顺序结构存储。 现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储,需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事,一个是数据结构,一个

    2024年02月09日
    浏览(52)
  • 数据结构:二叉树的顺序结构--堆

    朋友们、伙计们,我们又见面了,本期来给大家解读一下二叉树--堆的相关知识点,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! C 语 言 专 栏:C语言:从入门到精通 数据结构专栏:数据结构 个  人  主  页 :stackY、 目录 前言: 1.堆的概念及

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

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

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

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言 一、二叉树的存储结构 二、二叉树链式结构的实现 2.1手动构建一课树 2.2二叉树的遍历 三、二叉树链式结构的实现 3.1前序遍历(递归) 3.2中序遍历(递归) 3.3后序遍历(递归) 3.4层序遍历(非递

    2024年02月03日
    浏览(58)
  • 数据结构——树的概念、二叉树的概念

    现在是北京时间的2023年6月7号15点28分,刚考完了一课期末考试,回到宿舍就立马准备发布这篇博客。距离完成本周复习指标还差两篇博客。加油! 树是一种非线性的数据结构,它是由n(n=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的

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

      Yan-英杰的主页 悟已往之不谏 知来者之可追    C++程序员,2024届电子信息研究生 目录 前序、中序以及后序遍历 前序遍历 中序遍历 后序遍历                  学习二叉树结构,最简单的方式就是遍历。所谓 二叉树遍历 (Traversal) 是按照某种特定的规则,依次对二叉

    2023年04月23日
    浏览(44)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包