数据结构—链式二叉树-C语言

🕗 发布于 2024-07-16 07:10 数据结构 c语言 链表

代码位置：test-c-2024: 对C语言习题代码的练习 (gitee.com)

一、前言：

在现实中搜索二叉树为常用的二叉树之一，今天我们就要通过链表来实现搜索二叉树。实现的操作有：建二叉树、前序遍历、中序遍历、后序遍历、求树的节点个数、求树的高度、求k层节点个数、查找节点、层序遍历，判断是否是完全二叉树，二叉树的销毁。

二、代码实现：

2.0-开辟空间函数及结构体：

对于链表我们可以定义一个开辟空间的函数以便于后继的操作。对于结构体成员中我们需要包含节点值data和左右子树节点。

代码如下：

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include "Queue.h"

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

BTNode* BuyNode(BTDataType x)//开辟空间
{
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
if (node == NULL)
{
perror("malloc node");
return NULL;
}

node->data = x;
node->left = NULL;
node->right = NULL;

return node;
}

2.1-建二叉树：

对于建二叉树我们需要手动搓一个二叉树。

建的树如图所示：

代码如下：

BTNode* CreatTree()//建二叉树
{
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;
}

2.2-前序遍历：

二叉树前序遍历规则为：先访问根节点在访问左子树最后访问右子树。我这里是通过函数递归实现的访问。

代码如下：

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

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

2.3-中序遍历：

二叉树中序遍历规则为：先访问左子树在访问根节点最后访问右子树。我这里是通过函数递归实现的访问。

代码如下：

void InOrder(BTNode* root)//中序遍历
{
if (root == NULL)
{
printf("NULL ");
return;
}

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

2.4-后序遍历：

二叉树后序遍历规则为：先访问左子树在访问右子树最后访问根节点。我这里是通过函数递归实现的访问。

代码如下：

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

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

2.5-求树的节点个数：

这里是通过三目操作符以及递归来实现的统计节点个数。原理是如果该节点不是空节点则整体个数加1，然后继续访问下一子树，直到遍历完为止。

代码如下：

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

2.6-求树的高度：

这里是通过leftHeight和rightHeight来存储左右子树高度值，然后在return中通过三目运算符来返回高的那一子树在加1（这里加1是节点本身占一个高度）

代码如下：

int TreeHeight(BTNode* root)
{
if (root == NULL)
return 0;
int leftHeight = TreeHeight(root->left);
int rightHeight = TreeHeight(root->right);

return leftHeight> rightHeight
? leftHeight + 1
: rightHeight + 1;
}

2.7-求k层节点个数：

这里是通过递归传k-1是为了找到k层的所有节点若存在则返回1，不存在返回0然后将所有返回值相加返回即是第k层的节点个数。

代码如下：


int TreeLeave(BTNode* root,int k)//求k层节点个数
{
assert(k > 0);
if (root == NULL)
{
return 0;
}
if(k==1)
{
return 1;
}

return TreeLeave(root->left, k - 1) +TreeLeave(root->right, k - 1);
}

2.8-查找节点：

这里是通过递归遍历一遍树查找是否存在查找值若存在则返回该节点，若不存在则返回NULL。（注：这个函数只能查找出该值前序遍历第一次出现的位置）

代码如下：


BTNode* BinaryTreeFind(BTNode* root, BTDataType x)//查找
{
if (root == NULL)
{
return 0;
}
if (root->data == x)
{
return root;
}
BTNode* p = BinaryTreeFind(root->left, x);
if(p)
return p;
BTNode * q=BinaryTreeFind(root->right, x);
if (q )
return q;

return NULL;
}

2.9-层序遍历：

这里需要用到队列以前的博客里我们实现过队列，所以这里我们可以当个CV工程师将以前的代码复制过来即可。

队列代码：

#pragma once

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

typedef struct BinaryTreeNode* QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}QNode;

typedef struct Queue
{
QNode* head;
QNode* tail;
int size;
}Queue;

void QueueInit(Queue* pq);//初始化
void QueueDestory(Queue* pq);//释放销毁
void QueuePush(Queue* pq,QDataType x);//入队
void QueuePop(Queue* pq);//出队
int QueueSize(Queue* pq);//元素个数
bool QueueEmpty(Queue* pq);//判断队空
QDataType QueueFront(Queue* pq);//队头数据
QDataType QueueBack(Queue* pq);//队尾数据

#define _CRT_SECURE_NO_WARNINGS 1

#include "Queue.h"


void QueueInit(Queue* pq)    //初始化
{
assert(pq);

pq->head = pq->tail = NULL;
pq->size = 0;
}

void QueueDestory(Queue* pq)     //释放销毁
{
assert(pq);

QNode* cur =pq->head;
while (cur)
{
pq->head = cur->next;
free(cur);
cur = NULL;
cur = pq->head;
}
pq->head = pq->tail = NULL;
pq->size = 0;
}

void QueuePush(Queue* pq, QDataType x)//入队
{
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc");
return;
}
newnode->data = x;
newnode->next = NULL;

if (pq->head == NULL)
{
assert(pq->tail==NULL);

pq->head = pq->tail=newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
pq->size++;
}

void QueuePop(Queue* pq)//出队
{
assert(pq);
assert(!QueueEmpty(pq));

QNode* del = pq->head;
pq->head = pq->head->next;
free(del);
del = NULL;
if (pq->head == NULL)
{
pq->tail = NULL;
}
pq->size--;
}

int QueueSize(Queue* pq)//元素个数
{
assert(pq);

return pq->size;
}

bool QueueEmpty(Queue* pq)//判断队空
{
assert(pq);

return pq->size == 0;
}

QDataType QueueFront(Queue* pq)//队头数据
{
assert(pq);
assert(!QueueEmpty(pq));

return pq->head->data;
}

QDataType QueueBack(Queue* pq)//队尾数据
{
assert(pq);
assert(!QueueEmpty(pq));

return pq->tail->data;
}

遍历代码如下：

void LevelOrder(BTNode* root)//层序遍历
{
Queue p;
QueueInit(&p);
if(root)
QueuePush(&p, root);
while (!QueueEmpty(&p))
{
BTNode* front = QueueFront(&p);//取队列首元素的值
QueuePop(&p);
printf("%d ", front->data);

if (front->left)//入下一层元素
{
QueuePush(&p, front->left);
}
if (front->right)
{
QueuePush(&p, front->right);
}
}

QueueDestory(&p);
}

层序遍历代码执行的过程如图所示：

2.10-判断是否是完全二叉树：

判断完全二叉树是通过层序遍历和队列来实现。注意这里的层序遍历遇到空树也需要入队，为了判断二叉树是否为完全二叉树。原理：//层序遍历第一次遇到NULL时若后面没有数据节点则是完全二叉树，反之则不是

代码如下：

bool TreeComplete(BTNode* root)//判断是否是完全二叉树
{
Queue pq;
QueueInit(&pq);
QueuePush(&pq, root);
while (!QueueEmpty(&pq))
{
BTNode* front = QueueFront(&pq);
if (QueueFront(&pq) == NULL)
{
break;
}
QueuePop(&pq);

QueuePush(&pq, front->left);
QueuePush(&pq, front->right);
}
//层序遍历第一次遇到NULL时若后面没有数据节点则是完全二叉树，反之则不是
while (!QueueEmpty(&pq))
{
if (QueueFront(&pq) != NULL)
{
QueueDestory(&pq);
return false;
}
QueuePop(&pq);
}
QueueDestory(&pq);
return true;
}

2.11-二叉树的销毁：

二叉树销毁需遍历一遍链表，这里采用后序遍历比较方便，因为另外两个遍历都会因为释放根节点后左右子节点不好释放而产生不必要的麻烦，所以这里最好是使用后序遍历。注意这里只是释放掉了空间，因为这里是一级指针所以这里置空属于局部变量不会影响外部，所以在主函数调用时我们需手动置空。

如图所示：

代码如下：

void TreeDestory(BTNode* root)//销毁二叉树
{
if (root == NULL)
return;
TreeDestory(root->left);
TreeDestory(root->right);
free(root);
}

三、结语：

递归效果图展示：

最终效果图为：

上述内容，即是我个人对数据结构-链式二叉树-搜索二叉树-C语言的个人见解以及自我实现。若有大佬发现哪里有问题可以私信或评论指教一下我这个小萌新。非常感谢各位友友们的点赞，关注，收藏与支持，我会更加努力的学习编程语言，还望各位多多关照，让我们一起进步吧！

原文地址：https://blog.csdn.net/h_number_1/article/details/140355894

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：Uniapp自定义动态加载组件(2024.7更新)
下一篇：数电基础 - 触发器

python教程修订版
目前为止 one of the most sõught after for jobs.
阅读更多2024-09-24
Day26笔记-Day25作业讲解&对象的序列化和反序列化&安装第三方库
帮助0基础的小伙伴入门和学习Python！
阅读更多2024-09-24
数据驱动农业——农业中的大数据
AI、物联网、云计算和移动互联网等技术迅速发展，数据量呈爆炸式增长，传统的数据分析方法已无法满足需求。大数据技术在此背景下应运而生，为海量数据的分析提供了新机遇。虽然大数据技术在金融、医疗、交通等领域
阅读更多2024-09-24
深度学习：（七）梯度下降法在神经网络中的应用
详细说明了梯度下降法在神经网络中的应用，并给出公式和参数随机初始化的方法
阅读更多2024-09-24
JDBC封装day02
查询：ResultSet rs = this.executeSQL(SQL语句,Object数组)增，删，改: int i = this.executeUpdate(SQL语句,Object数组)co
阅读更多2024-09-24
【一句话点破】【C++重要题目】基类与派生类的成员变量值被对象调用的结果（二）
【一句话点破】基类/派生类的成员变量由哪个对象初始化的，哪个对象调用该成员变量时就用由它初始化的值 [尤其找准是基类对象or派生类对象的值]
阅读更多2024-09-24
哈里斯表态：承诺支持加密货币投资！
加密风险投资公司Variant的法务主管Jake Chervinsky在X上写道：“这是一种进步，而且是一种好的进步，但哈里斯所说的‘在保护我们的消费者和投资者的同时’可能意味着很多事情。还是想看看政
阅读更多2024-09-24
缓存与数据库如何保持一致及MySQL和Redis的使用场景以及区别
在更新数据库数据后，先删除缓存中的数据，再进行数据库更新操作，这样可以保证在数据库更新期间，缓存中的数据已被删除，下一次查询时会从数据库中读取最新数据，并更新缓存。双写一致性是指在更新数据库数据之前，
阅读更多2024-09-24
vue-animate-onscroll动画库(可来回触发动画)
它是一个 Vue 插件，用于在滚动时触发动画效果。它可以帮助开发者在用户滚动页面时，逐渐展示元素，增强用户体验。基本用法是通过在元素上添加特定的指令，指定动画效果和触发条件。
阅读更多2024-09-24
使用反向代理软件frp在局域网内共享上网
linux服务器借用同局域网的win上的代理工具正常上网
阅读更多2024-09-24

数据结构—链式二叉树-C语言

一、前言：

二、代码实现：

2.0-开辟空间函数及结构体：

2.1-建二叉树：

2.2-前序遍历：

2.3-中序遍历：

2.4-后序遍历：

2.5-求树的节点个数：

2.6-求树的高度：

2.7-求k层节点个数：

2.8-查找节点：

2.9-层序遍历：

2.10-判断是否是完全二叉树：

2.11-二叉树的销毁：

三、结语：

递归效果图展示：

最终效果图为：

相关文章