目录
一,二叉树的销毁
二,二叉树系列所有源代码
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;
}
同志们!二叉树(初阶)的知识就到这了,加油!
二叉树(初阶)阶段就到这里了;
后面博主会陆续更新;
如有不足之处欢迎来补充交流!文章来源:https://www.toymoban.com/news/detail-717204.html
完结。。文章来源地址https://www.toymoban.com/news/detail-717204.html
到了这里,关于【数据结构】二叉树的销毁 & 二叉树系列所有源代码(终章)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!