当前位置: 首页 > news >正文

数据结构_链式二叉树(Chained binary tree)基础

✨✨所属专栏:数据结构✨✨

✨✨作者主页:嶔某✨✨

 二叉树的遍历

前序、中序以及后序遍历

学习二叉树结构,最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则,依次对二叉树中的结点进行相应的操作,并且每个结点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一,也是二叉树上进行其它运算的基础。
按照规则,二叉树的遍历有:前序/中序/后序的递归结构遍历:

1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中(间)。
3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

由于被访问的结点必是某子树的根,所以N(Node)、L(Left subtree)和R(Right subtree)又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{if (root == NULL){	printf("# ");return;}printf("%c ",root->_data);BinaryTreePrevOrder(root->_left);BinaryTreePrevOrder(root->_right);
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{if (root == NULL){printf("# ");return;}BinaryTreePrevOrder(root->_left);printf("%c ", root->_data);BinaryTreePrevOrder(root->_right);
}
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{if (root == NULL){printf("# ");return;}BinaryTreePrevOrder(root->_left);BinaryTreePrevOrder(root->_right);printf("%c ", root->_data);
}

层序遍历

层序遍历:除了前序遍历、中序遍历、后序遍历外,还可以对二叉树进行层序遍历。设二叉树的根结点所在层数为1,层序遍历就是从所在二叉树的根结点出发,首先访问第一层的树根结点,然后从左到右访问第2层上的结点,接着是第三层的结点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历。

这里与前、中、后序遍历不同的是:层序遍历用的迭代而非递归。创建一个队列,将整个树的根节点入队,之后再将根节点的左右节点入队。让上一层节点带动下一层,父节点将子女节点带入队,之后将父节点拿出队列,这样就实现了层序遍历。

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{assert(root);Queue q;QueueInit(&q);QueuePush(&q,root);while (QueueSize(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);printf("%c ", front->_data);if (front->_left)QueuePush(&q,front->_left);if(front->_right)QueuePush(&q,front->_right);}
}

 其他函数

通过前序遍历数组创建二叉树

 判断下标为i的字符是否为'#',如果不为'#'那就新malloc一个节点将数据放进去,新节点的左右节点分别再递归赋值。

BTNode* BinaryTreeCreate(BTDataType* a,int* pi)
{if (a[*pi] == '#'){(*pi)++;return NULL;}BTNode* new = (BTNode*)malloc(sizeof(BTNode));if (new == NULL){perror("malloc is fail");return NULL;}new->_data = a[(*pi)++];new->_left = BinaryTreeCreate(a, pi);new->_right = BinaryTreeCreate(a, pi);return new;
}

销毁二叉树

如果当前节点为空那么就释放,如果当前节点不为空,那么就先递归释放左右子树,左右子树释放后再将根节点释放并置空。

// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{if (*root == NULL){free(*root);return;}BinaryTreeDestory(&(*root)->_left);BinaryTreeDestory(&(*root)->_right);free(*root);*root = NULL;
}

二叉树节点个数

如果当前节点为空返回0,如果当前节点不为空返回其左右子树的节点个数+1。

// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{if (root == NULL)return 0;return BinaryTreeSize(root->_left)+ BinaryTreeSize(root->_right) + 1;
}

二叉树叶子节点个数

如果节点的左右节点都为空返回1,否则返回左右子树的叶子节点个数。

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL)return 0;if (root->_left == NULL && root->_right == NULL)return 1;return BinaryTreeLeafSize(root->_left)+ BinaryTreeLeafSize(root->_right);
}

二叉树第k层节点个数

第k层节点的个数,可以看作第一层的左右节点的第k-1层节点个数,因此当k == 1时此层就是要计算再内的节点。

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == NULL)return 0;if (k == 1)return 1;return BinaryTreeLevelKSize(root->_left, k - 1)+ BinaryTreeLevelKSize(root->_right, k - 1);
}

二叉树查找值为x的节点

采取前序遍历,如果根节点的值等于x,返回root,否则先判断左子树有无符合节点,若有返回对应的节点,反之返回另一个子树的对应节点,若左右字数都没有对应节点,最终将返回空

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL)return NULL;if (root->_data == x)return root;BTNode* ret1 = BinaryTreeFind(root->_left, x);if (ret1 != NULL)return ret1;return BinaryTreeFind(root->_right, x);	
}

判断二叉树是否为完全二叉树

建立一个队列,和层序遍历一样,当遇到空节点时,跳出循环,开始判断。如果再空节点的后面还有非空节点,那么这棵树就不是完全二叉树。反之此树空节点之后的所有的节点都为空,那么此树为完全二叉树。

// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{assert(root);Queue q;QueueInit(&q);QueuePush(&q, root);while (QueueSize(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front == NULL)break;QueuePush(&q, front->_left);QueuePush(&q, front->_right);}while (QueueSize(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front){Destory(&q);return false;}}return true;
}

本期博客到这里就结束了,如果有什么错误,欢迎指出,如果对你有帮助,请点个赞,谢谢!

相关文章:

数据结构_链式二叉树(Chained binary tree)基础

✨✨所属专栏:数据结构✨✨ ✨✨作者主页:嶔某✨✨ 二叉树的遍历 前序、中序以及后序遍历 学习二叉树结构,最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则,依次对二叉树中的结点进行相应的操作&#xff…...

python梯度下降法求解三元线性回归系数,并绘制结果

import numpy as np import matplotlib.pyplot as plt # 生成随机数据 np.random.seed(0) X1 2 * np.random.rand(100, 1) X2 3 * np.random.rand(100, 1) X3 4 * np.random.rand(100, 1) y 4 3 * X1 5 * X2 2 * X3 np.random.randn(100, 1) # 合并特征 X_b np.hsta…...

Linux基础(五):常用基本命令

从本节开始,我们正式进入Linux的学习,通过前面的了解,我们知道我们要以命令的形式使用操作系统(使用操作系统提供的各类命令,以获得字符反馈的形式去使用操作系统。),因此,我们是很有…...

原始字面常量(C++11)

原始字面常量(C11) 文章目录 原始字面常量(C11)前言一、原始字面量二、代码示例总结 前言 字面量一般是指数值(12、454等)和字符串(“Hw”、“h\t”),但是有时候我们想表…...

C++|设计模式(〇)|设计模式的六大原则

这里文章只做简要描述,作为扫盲 在软件开发过程中,遵循一定的设计原则可以帮助开发者创建更加灵活、可维护和可扩展的系统。设计模式的六大原则是面向对象设计的核心理念,本文将详细介绍这些原则,并结合实例说明它们的重要性和应用…...

【排序算法】——归并排序(递归与非递归)含动图

制作不易,三连支持一下吧!!! 文章目录 前言一.归并排序递归方法实现二.归并排序非递归方法实现 前言 这篇博客我们将介绍归并排序的原理和实现过程。 一、归并排序递归方法实现 基本思想: 归并排序(MERGE-…...

Mysql自增id、uuid、雪花算法id的比较

MySQL自增id: 优点: 1.简单易用 ​ MySQL自增id 由数据库自动生成。 2.效率高 自增id是按顺序递增的,可以提高插入和查询的效率。 3.索引效率高 自增id可以作为主键或索引列,提高查询效率。 缺点: 1.不适用于分布式系统 在分布式…...

【会议征稿,IEEE出版】第九届信息科学、计算机技术与交通运输国际学术会议(ISCTT 2024,6月28-30)

第九届信息科学、计算机技术与交通运输国际学术会议(ISCTT 2024)将于2024年6月28-30日在中国绵阳举行。 ISCTT 2024将围绕 “信息科学”、"计算机技术”、“交通运输” 等最新研究领域,为来自国内外高等院校、科学研究所、企事业单位的专…...

二十八篇:嵌入式系统实战指南:案例研究与未来挑战

嵌入式系统实战指南:案例研究与未来挑战 1. 引言 1.1 嵌入式系统的重要性及其应用广度 在当今快速发展的技术领域中,嵌入式系统扮演着至关重要的角色。这些系统是专门设计的计算机硬件和软件的组合,旨在执行特定任务,如控制、监…...

探索编程乐趣:绘制螺旋图的奇幻之旅

新书上架~👇全国包邮奥~ python实用小工具开发教程http://pythontoolsteach.com/3 欢迎关注我👆,收藏下次不迷路┗|`O′|┛ 嗷~~ 目录 一、引言:编程的魔法世界 二、绘制螺旋图的准备工作 三、代码实战:…...

C# 语法糖

语法糖 var关键字(隐式类型变量):自动属性:简化的事件访问器:Lambda表达式和匿名方法:扩展方法:LINQ查询:异步编程(async和await):嵌套匿名类型&a…...

ubuntu 安装VMtool 实现复制粘贴

如果只是安装一个根本没有用,而是两个命令都要安装 sudo apt-get install open-vm-tools sudo apt-get install open-vm-tools-desktop引用博客...

智慧仓储新动力:EasyCVR+AI视频智能监管系统方案助力仓储安全高效管理

一、背景 随着物流行业的快速发展和智能化水平的提升,智慧仓储视频智能监管系统已成为现代仓储管理的重要组成部分。本系统通过综合运用物联网、视频分析、边缘计算等技术手段,实现对仓储环境的全面监控、智能分析和高效管理。 TSINGSEE青犀视频汇聚Ea…...

gcc源码分析(AST抽象语法树)

文章目录 三、AST相关1、AST(抽象语法树)1.1 树结点的声明1.2 树结点的结构1.2.1 tree_node联合体1.2.2 tree_base结构体1.2.3 tree_common结构体1.2.4 常量结构体1.2.5 **标识符节点**2、符号绑定,作用域与block树节点2.1 lang_identifier结构体2.2 c_binding结构体2.3 scop…...

ES基础概念

本文不介绍如何使用ES(使用ES见:) 1.ES生态圈 ES: Logstash:数据处理服务程序,解析转换加工数据; Kibana:数据展示、集群管理,数据可视化、ES管理与监控、报表等&#xf…...

断更是我的错

打算在暑假每天两个文章,大概是6月20多号开始吧。...

红队攻防渗透技术实战流程:云安全之云原生安全:云堡垒机

红队云攻防实战 1. 云原生安全-防护设备-云堡垒机1. 云原生安全-防护设备-云堡垒机 堡垒机攻防:(意义) https://mp.weixin.qq.com/s/-WcgyVoTCZuPamVtI5MrJw 堡垒机漏洞:(已知)https://avd.aliyun.com/search?q=%E5%A0%A1%E5%9E%92%E6%9C%BA 云堡垒机:(云攻防) http…...

Down with typename

1. 隐式类型名的详情 C20 之前&#xff0c;typename 在一些其他情况下是不必要的: • 指定继承类的基类型时 • 在构造函数中将初始值传递给基类时 • 在类声明中使用类型成员时 #include <iostream> struct Impl {Impl(){ std::cout << "Impl ctor" &…...

CSS3背景与渐变

背景与渐变 background-size background-size 属性用于设置背景图像的尺寸。您可以指定绝对或相对单位,或者使用关键词来控制背景图像在元素背景区域中的大小。 .element {background-size: [length | percentage | cover | contain] | [length | percentage] [length | per…...

线性表——链式存储

单链表&#xff08;有头结点&#xff09; #include<stdio.h> #include<stdlib.h> //定义 typedef struct LNode{int data; //数据域 struct LNode *next; //指针域指向下一个结点&#xff0c;所以是 struct LNode类型 }LNode,*LinkList; //…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序&#xff0c;以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务&#xff0c;提供稳定高效的数据处理与业务逻辑支持&#xff1b;利用 uniapp 实现跨平台前…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

#Uniapp篇:chrome调试unapp适配

chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器&#xff1a;Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...

【Go语言基础【12】】指针:声明、取地址、解引用

文章目录 零、概述&#xff1a;指针 vs. 引用&#xff08;类比其他语言&#xff09;一、指针基础概念二、指针声明与初始化三、指针操作符1. &&#xff1a;取地址&#xff08;拿到内存地址&#xff09;2. *&#xff1a;解引用&#xff08;拿到值&#xff09; 四、空指针&am…...