数据结构—链式二叉树-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语言的个人见解以及自我实现。若有大佬发现哪里有问题可以私信或评论指教一下我这个小萌新。非常感谢各位友友们的点赞,关注,收藏与支持,我会更加努力的学习编程语言,还望各位多多关照,让我们一起进步吧!

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

免费开源的工业物联网(IoT)解决方案

什么是 IoT&#xff1f; 物联网 (IoT) 是指由实体设备、车辆、电器和其他实体对象组成的网络&#xff0c;这些实体对象内嵌传感器、软件和网络连接&#xff0c;可以收集和共享数据。 IoT 设备&#xff08;也称为“智能对象”&#xff09;范围广泛&#xff0c;包括智能恒温器等…

FastAPI 学习之路(四十四)WebSockets

我们之前的分析都是基于http的请求&#xff0c;那么如果是websockets可以支持吗&#xff0c;答案是可以的&#xff0c;我们来看下是如何实现的。 from fastapi import WebSocket, FastAPI from fastapi.responses import HTMLResponseapp FastAPI()html """&…

架构师机器学习操作 (MLOps) 指南

MLOps 是机器学习操作的缩写&#xff0c;是一组实践和工具&#xff0c;旨在满足工程师构建模型并将其投入生产的特定需求。一些组织从一些自主开发的工具开始&#xff0c;这些工具在每次实验后对数据集进行版本控制&#xff0c;并在每个训练周期后对检查点模型进行版本控制。另…

新手-前端生态

文章目录 新手的前端生态一、概念的理解1、脚手架2、组件 二、基础知识1、HTML2、css3、JavaScript一、基础语法1、javaScript的引入2、认识输出语句3、学会处理报错 二、变量1、如何使用变量 2、变量的命名规范3、推荐的变量命名法4、变量默认值5、变量常见的错误6、变量声明提…

Prometheus 云原生 - 微服务监控报警系统 (Promethus、Grafana、Node_Exporter)部署、简单使用

目录 开始 Prometheus 介绍 基本原理 组件介绍 下文部署组件的工作方式 Prometheus 生态安装&#xff08;Mac&#xff09; 安装 prometheus 安装 grafana 安装 node_exporter Prometheus 生态安装&#xff08;Docker&#xff09; 安装 prometheus 安装 Grafana 安装…

人工智能算法工程师(中级)课程14-神经网络的优化与设计之拟合问题及优化与代码详解

大家好&#xff0c;我是微学AI&#xff0c;今天给大家介绍一下人工智能算法工程师(中级)课程14-神经网络的优化与设计之拟合问题及优化与代码详解。在机器学习和深度学习领域&#xff0c;模型的训练目标是找到一组参数&#xff0c;使得模型能够从训练数据中学习到有用的模式&am…

设计模式总结(设计模式的原则及分类)

1.什么是设计模式&#xff1f; 设计模式(Design pattern)代表了最佳的实践&#xff0c;通常被有经验的面向对象的软件开发人员所采用。设计模式是软件开发人员在软件开发过程中面临的一般问题的解决方案。这些解决方案是众多软件开发人员经过相当长的一段时间的试验和错误总结…

【ACM 独立出版,高录用EI稳检索】2024年大数据与数字化管理国际学术会议 (ICBDDM 2024,8月16-18)

2024年大数据与数字化管理国际学术会议 (ICBDDM 2024)&#xff0c;将于2024年8月16-18日在中国上海召开。 “大数据与数字化管理”作为会议主题&#xff0c;旨在聚焦这一跨学科领域中最新的理论研究、技术进展、实践案例和未来趋势。本主题探讨的研究方向涵盖了大数据的收集、…

使用uni-app和Golang开发影音类小程序

在数字化时代&#xff0c;影音内容已成为人们日常生活中不可或缺的一部分。个人开发者如何快速构建一个功能丰富、性能优越的影音类小程序&#xff1f;本文将介绍如何使用uni-app前端框架和Golang后端语言来实现这一目标。 项目概述 本项目旨在开发一个个人影音类小程序&#…

最新Qt6的下载与成功安装详细介绍

引言 Qt6 是一款强大的跨平台应用程序开发框架&#xff0c;支持多种编程语言&#xff0c;最常用的是C。Qt6带来了许多改进和新功能&#xff0c;包括对C17的支持、增强的QML和UI技术、新的图形架构&#xff0c;以及构建系统方面的革新。本文将指导你如何在Windows平台上下载和安…

Webpack看这篇就够了

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 非常期待和您一起在这个小…

PostgreSQL安装/卸载(CentOS、Windows)

说明&#xff1a;PostgreSQL与MySQL一样&#xff0c;是一款开源免费的数据库技术&#xff0c;官方口号&#xff1a;The World’s Most Advanced Open Source Relational Database.&#xff08;世界上最先进的开源关系数据库&#xff09;&#xff0c;本文介绍如何在Windows、Cen…

一款好用的特殊字符处理工具

跟mybatis代码的时候&#xff0c;偶然发现的一款特殊字符处理工具java.lang.StringTokenizer。平常&#xff0c;我们看到的mybatis mapper.xml里面各种换行各种缩进&#xff0c;但日志文件里面的sql都是整整齐齐的。没有换行符&#xff0c;缩进等。就是利用该工具做的格式化处理…

Java设计模式的7个设计原则

Java设计模式的7个设计原则是面向对象设计领域中的重要指导方针&#xff0c;它们旨在提高软件系统的可维护性、可扩展性、可复用性和灵活性。以下是这7个设计原则的详细解释&#xff1a; 1. 开闭原则&#xff08;Open-Closed Principle, OCP&#xff09; 定义&#xff1a;一个…

git常用命令及git分支

git常用命令及git分支 git常用命令设置用户签名初始化本地库查看本地库状态将文件添加到暂存区提交到本地库查看历史记录版本穿梭 git分支什么是分支分支的好处分支的操作查看分支创建分支切换分支删除分支合并分支合并冲突 git常用命令 设置用户签名 //设置用户签名 git con…

axios 下载大文件时,展示下载进度的组件封装——js技能提升

之前面试的时候&#xff0c;有遇到一个问题&#xff1a;就是下载大文件的时候&#xff0c;如何得知下载进度&#xff0c;当时的回复是没有处理过。。。 现在想到了。axios中本身就有一个下载进度的方法&#xff0c;可以直接拿来使用。 下面记录一下处理步骤&#xff1a; 参考…

超市管理系统 需求分析与设计 UML 方向

一、项目介绍 1.1项目背景 随着经济一体化和电子商务的迅速发展&#xff0c;网络传播信息的速度打破了传统信息传递的模式&#xff0c;互联网的高速发展和计算机应用在各个高校进展迅速&#xff0c;更多信息化产品的突飞猛进&#xff0c;让现代的管理模式也发生了巨大的变化&…

技术成神之路:设计模式(七)状态模式

1.介绍 状态模式&#xff08;State Pattern&#xff09;是一种行为设计模式&#xff0c;它允许一个对象在其内部状态改变时改变其行为。这个模式将状态的相关行为封装在独立的状态类中&#xff0c;并将不同状态之间的转换逻辑分离开来。 2.主要作用 状态模式的主要作用是让一个…

开始Linux之路

人生得一知己足矣&#xff0c;斯世当以同怀视之。——鲁迅 Linux操作系统简单操作指令 1、ls指令2、pwd命令3、cd指令4、mkdir指令(重要)5、whoami命令6、创建一个普通用户7、重新认识指令8、which指令9、alias命令10、touch指令11、rmdir指令 及 rm指令(重要)12、man指令(重要…

数据结构进阶:使用链表实现栈和队列详解与示例(C, C#, C++)

文章目录 1、 栈与队列简介栈&#xff08;Stack&#xff09;队列&#xff08;Queue&#xff09; 2、使用链表实现栈C语言实现C#语言实现C语言实现 3、使用链表实现队列C语言实现C#语言实现C语言实现 4、链表实现栈和队列的性能分析时间复杂度空间复杂度性能特点与其他实现的比较…