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

目录

一，二叉树的销毁 

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

BTee.h

BTee.c

Queue.h

Queue.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 了，只要捋清楚思路了，就很简单了；

经过了9个阶段的学习，二叉树的初阶部分也是迎来了结尾，为什么说是初阶部分呢？因为一些更复杂的树的内容不太方便用 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;
}

同志们！二叉树（初阶）的知识就到这了，加油！

二叉树（初阶）阶段就到这里了；

后面博主会陆续更新；

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

完结。。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.xdnf.cn/news/142320.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

LeetCode力扣020:有效的括号

LeetCode力扣020:有效的括号

有效的括号 实现思路 设立判定条件遍历的范围 代码实现 class Solution(object):def isValid(self, s):""":type s: str:rtype: bool"""nlen(s)for i in range(0,n-1):if s[i]( and s[i1]!):return Falseif s[i][ and s[i1]!]:return Falseif s…
阅读更多...
02Redis的命令行客户端和桌面客户端的下载和安装

02Redis的命令行客户端和桌面客户端的下载和安装

Redis桌面客户端 安装完成Redis服务,我们就可以在Redis的客户端操作Redis的数据库实现数据的CRUD了,客户端分为三类命令行客户端, 图形化桌面客户端,编程客户端 命令行客户端 Redis安装完成后就自带了命令行客户端: redis-cli [options] [commonds] -h选项&#xff1a;指定…
阅读更多...
Jenkins+Allure+Pytest的持续集成

Jenkins+Allure+Pytest的持续集成

一、配置 allure 环境变量 1、下载 allure是一个命令行工具&#xff0c;可以去 github 下载最新版&#xff1a;https://github.com/allure-framework/allure2/releases 2、解压到本地 3、配置环境变量 复制路径如&#xff1a;F:\allure-2.13.7\bin 环境变量、Path、添加 F:\a…
阅读更多...
从零开始的 MyBatis 拦截器之旅：实战经验分享

从零开始的 MyBatis 拦截器之旅：实战经验分享

文章目录 MyBatis拦截器可以做什么&#xff1f;Mybatis核心对象介绍四大核心对象如何实现&#xff1f;接口讲解Interceptor接口intercept方法plugin方法setProperties 完整SQL打印拦截器实战拦截器实现拦截器注册 MyBatis拦截器可以做什么&#xff1f; MyBatis拦截器是MyBatis…
阅读更多...
生而强大：STM32H7

生而强大：STM32H7

阅读更多...
软件测试面试题 —— 整理与解析（4）

软件测试面试题 —— 整理与解析（4）

&#x1f60f;作者简介&#xff1a;博主是一位测试管理者&#xff0c;同时也是一名对外企业兼职讲师。 &#x1f4e1;主页地址&#xff1a;【Austin_zhai】 &#x1f646;目的与景愿&#xff1a;旨在于能帮助更多的测试行业人员提升软硬技能&#xff0c;分享行业相关最新信息。…
阅读更多...
自动化测试：为什么需要框架

自动化测试：为什么需要框架

前两天跟老板出去做pre-sales. 主要是去卖我们的自动化测试服务&#xff0c;工具用的是HP UFT。做过自动化的人应该知道&#xff0c;UFT在自动化测试领域已经算是最好的工具之一了。客户是个有技术背景的人&#xff0c;所以不那么好忽悠。我们准备了一大堆自动化测试优点的幻灯…
阅读更多...
推荐一个AI人工智能技术网站（一键收藏，应有尽有）

推荐一个AI人工智能技术网站（一键收藏，应有尽有）

1、Mental AI MentalAI&#xff08;https://ai.ciyundata.com/&#xff09;是一种基于星火大模型和文心大模型的知识增强大语言模型&#xff0c;专注于自然语言处理&#xff08;NLP&#xff09;领域的技术研发。 它具备强大的语义理解和生成能力&#xff0c;能够处理各种复杂的…
阅读更多...
【效率提升】maven 转 gradle 实战 | 京东云技术团队

【效率提升】maven 转 gradle 实战 | 京东云技术团队

一、灵魂三问 1、gradle 是什么&#xff1f; 一个打包工具&#xff0c; 是一个开源构建自动化工具&#xff0c;足够灵活&#xff0c;可以构建几乎任何类型的软件&#xff0c;高性能、可扩展、能洞察等。其中洞察&#xff0c;可以用于分析构建过程中数据&#xff0c;提供分析参…
阅读更多...
想学python找不到合适的书籍？它来了！入门python只需要这一本书就够了！

想学python找不到合适的书籍？它来了！入门python只需要这一本书就够了！

想学python找不到合适的书籍&#xff1f;看了视频还是不知如何下手&#xff1f; 《python王者归来》 它来了&#xff01;由清华大学出版社出版&#xff01;入门python只需要这一本书就够了&#xff01; 【PDF版领取见文末】 这是一本python入门书。无论你是计算机专业的大学生…
阅读更多...
C语言之字符函数字符串函数篇（1）

C语言之字符函数字符串函数篇（1）

目录 前言 求字符串长度 strlen strlen统计的是字符串\0之前的字符串长度 字符指针 strlen的返回值是无符号整型 strlen的三种模拟实现 计数器 函数递归 指针_指针 长度不受限制的字符串函数 strcpy strcpy会将源字符串中的 \0 拷贝到目标空间 strcpy参数目标空…
阅读更多...
echarts添加点击事件

echarts添加点击事件

实现效果&#xff1a;点击图表&#xff0c;弹出该数据下对应得详情 官方文档&#xff1a; 封装的图表组件中&#xff1a; 点击获取点击得对象&#xff0c;进而将需要的参数传给父组件&#xff0c;在父组件中再去请求接口获取更多信息 this.chart.on(click, (params)> {th…
阅读更多...
Docker 安装Redis（集群）

Docker 安装Redis（集群）

3主3从redis集群配置 1、新建6个docker容器 redis 实例 docker run -d --name redis-node-1 --net host --privilegedtrue -v /data/redis/share/redis-node-1:/data redis:6.0.8 --cluster-enabled yes --appendonly yes --port 6381 docker run -d --name redis-node-2 --ne…
阅读更多...
聚焦云原生安全|如何为5G边缘云和工业互联网应用筑牢安全防线

聚焦云原生安全|如何为5G边缘云和工业互联网应用筑牢安全防线

9月22日&#xff0c;2023年中国信息通信业发展高层论坛5G工业互联网分论坛在北京顺利举办。 作为国内云原生安全领导厂商&#xff0c;安全狗受邀出席此次活动。 据悉&#xff0c;中国信息通信业发展高层论坛是致力于研究信息通信业发展新问题、新趋势&#xff0c;推动信息通信…
阅读更多...
使用vite插件进行低代码平台自定义开发（手机版自定义范例）

使用vite插件进行低代码平台自定义开发（手机版自定义范例）

前言 Youtube上的前端网红「Theo」在React文档仓库发起了一个Pull request&#xff0c;号召React文档不要再默认推荐CRA(create react app)&#xff0c;而是应该将Vite作为构建应用的首选。 vite的影响力已经从vue蔓延到了react&#xff0c;可见在前端工程化开发中&#xff0c…
阅读更多...
如何使用ArcGIS Pro将等高线转DEM

如何使用ArcGIS Pro将等高线转DEM

通常情况下&#xff0c;我们拿到的等高线数据一般都是CAD格式&#xff0c;如果要制作三维地形模型&#xff0c;使用栅格格式的DEM数据是更好的选择&#xff0c;这里就为大家介绍一下如何使用ArcGIS Pro将等高线转DEM&#xff0c;希望能对你有所帮助。 创建TIN 在工具箱中选择“…
阅读更多...
如何构建基于大模型的App

如何构建基于大模型的App

ChatGPT 的出现让大模型再一次成为业界的关注热点&#xff0c;然而&#xff0c;并不是每个组织都要去训练及生成大模型的&#xff0c;而且各个组织的技术积累和计算资源也不太允许这样去做。更多的时候&#xff0c; 我们还是基于大模型开发业务应用。所谓智能原生&#xff08;A…
阅读更多...
SpringMVC-请求与相应

SpringMVC-请求与相应

一、环境准备 <dependencies><dependency><groupId>javax.servlet</groupId><artifactId>javax.servlet-api</artifactId><version>3.1.0</version><scope>provided</scope> //确定范围避免与tomcat冲突</de…
阅读更多...
vivado乘法器IP核进行无符号与有符号数相乘问题的验证

vivado乘法器IP核进行无符号与有符号数相乘问题的验证

本文验证乘法器IP核Multiplier进行无符号(unsigned)与有符号数(signed)相乘的正确性&#xff0c;其中也遇到了一些问题&#xff0c;做此记录。 配套工程&#xff1a;https://download.csdn.net/download/weixin_48412658/88354179 文章目录 问题的讨论验证过程IP核配置例化乘…
阅读更多...
python+nodejs+php+springboot+vue 导师双选系统

python+nodejs+php+springboot+vue 导师双选系统

为了直观显示系统的功能&#xff0c;运用用例图这样的工具显示分析的结果。分析的导师功能如下。导师管理导师选择信息&#xff0c;管理项目&#xff0c;管理项目提交并对学员提交的项目进行指导。 为了直观显示系统的功能&#xff0c;运用用例图这样的工具显示分析的结果。分析…
阅读更多...
最新文章

Copyright @ 2022~2023