-
数据结构与算法 & 二叉树工具
2020-03-18 17:22:33在计算机科学中,二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。 ![在这里插入图片描述]...一、二叉树
1.定义(百度):
在计算机科学中,二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。
2.二叉树的特点
二叉的分类很多,特性也不少。这里不准备细说。
1)二叉树只有一个根节点
2)二叉树的每个节点会有两个孩子。分为左孩子、右孩子。两个还是不一定必须拥有。二、二叉树的生成
1.二叉树数据结构实现
二叉树可以看成每个节点的组成,那么这个节点要有存储数据的地方,要有指向左右孩子的指针。
所以可以这样生成:typedef struct B_TREE { USER_TYPE data;//用户自定义数据类型 struct B_TREE *left;//指向左孩子 struct B_TREE *right;//指向右孩子 }B_TREE;
2.二叉树数据的表示
- 给每个节点标上序号,但是需要完全二叉树才能将每个节点位置表示清楚。所以容易造成空间浪费。
2. 父节点(左孩子,右孩子)模式
上面的二叉可以这样表述为: A(B, O(M( ,C))
这种方式比较节省空间,但是也让处理该二叉树麻烦起来。因为我们加入了左右括号和逗号,使得识别难度增加了。
该模式有 “字符”,‘’左括号‘,“右括号”,“逗号”’
接下来分析一下该模式的各个状态:
最后我们生成一个自动状态变迁图。
依照这个图我们开始编码:#define B_TREE_STATUS_START 1 //开始状态 #define B_TREE_STATUS_ROOT 2 //根状态 #define B_TREE_STATUS_LEFTBRACKET 3 //左括号状态 #define B_TREE_STATUS_RIGHTBRACKET 4 //右括号状态 #define B_TREE_STATUS_ALPHA 5 //字母状态 #define B_TREE_STATUS_COMMA 6 //逗号状态 #define B_TREE_STATUS_END 7 //结束状态
状态的判定:
while (arg.ok && !arg.finished) { arg.index += skipBlank(str + arg.index);//跳过空格 switch (arg.status) { case B_TREE_STATUS_START: dealBTreeStart(&arg, str[arg.index]); break; case B_TREE_STATUS_ROOT: dealBTreeRoot(&arg, str[arg.index]); break; case B_TREE_STATUS_LEFTBRACKET: dealBTreeLeftbracket(&arg, str[arg.index]); break; case B_TREE_STATUS_RIGHTBRACKET: dealBTreeRightbracket(&arg, str[arg.index]); break; case B_TREE_STATUS_ALPHA: dealBTreeAlpha(&arg, str[arg.index]); break; case B_TREE_STATUS_COMMA: dealBTreeComma(&arg, str[arg.index]); break; case B_TREE_STATUS_END: if (arg.bracketMatch != 0) { errMess = "括号不匹配!"; arg.ok = FALSE; break; // 这个break;用来跳出switch // 这个break;不是用来结束循环的! } *root = arg.root; arg.finished = TRUE; break; default: break; } }
状态的转换:
//开始状态 static void dealBTreeStart(B_TREE_ARG *arg, int ch) { if (isalpha(ch)) { dealRoot(arg, ch);//进入根状态 } else { errMess = "不能是空树!"; arg->ok = FALSE;//错误 } }
//解决根状态 static void dealRoot(B_TREE_ARG *arg, int ch) { arg->node = arg->root = createNode(ch); arg->status = B_TREE_STATUS_ROOT;//转换到根状态,记录下来。 arg->index++;//为判断下个字符检测 }
基本思路: 原状态(已知) --> 判断字符类型 – > 处理该字符 --> 转换原状态 --> 进入下一个字符
其它各状态略!3.二叉树生成
从上面的自动转态变迁图,我们知道了如何处理用户给予的二叉树数据表达形式。那么我们怎么生成二叉树呢?
二叉树难的地方就是,怎么将各个节点连接起来?谁是左孩子?谁是右孩子?A(B(D(F, G), J(, L(K, ))), C(E(H,I)))
观察这个你发现了啥?
1.区别左右孩子的标志是“逗号”。逗号后面的数据一定是右孩子。
2.字符后面的有左括号,那么该字符一定有孩子。那么怎么确认每个节点的父节点呢?
我们这里采用堆栈空间存储每个父节点。
A,是父节点,入栈,B是父节点,入栈,D是父节点,入栈;当前栈内: 底,ABD,顶
G是右孩子,且后面是右括号,父节点D出栈;当前栈内: 底,AB,顶
J是父节点,入栈,L是父节点,入栈;当前栈内: 底,ABJL,顶
L孩子遍历结束,出栈,J孩子遍历结束,出栈,B孩子遍历结束,出栈;当前栈内: 底,A,顶
…
就这样,实现父节点的寻找。尤其我们创造过一种堆栈工具。正好可以使用。数据结构与算法 & 堆栈工具再结合上述发现,就能很好生成一个二叉树了。
static B_TREE *createNode(int ch) { B_TREE *node = NULL; node = (B_TREE *) calloc(sizeof(B_TREE), 1); // 为了节省时间,这里不处理申请空间失败的问题。 node->data = ch; node->left = node->right = NULL; return node; } static void dealNode(B_TREE_ARG *arg, int ch) { B_TREE *parent; arg->node = createNode(ch); // 找到其父节点,将node置位父的左、右孩子 parent = (B_TREE *) readTop(arg->stack); if (LEFT_CHILD == arg->whichChild) { parent->left = arg->node; } else { if (NULL != parent->right) { free(arg->node); errMess = "二叉树不存在第三个子节点!"; arg->ok = FALSE; return; } parent->right = arg->node; } arg->status = B_TREE_STATUS_ALPHA; arg->index++; }
注意: 这里有一个堆栈空间的容量申请问题。
可以简单处理为用户输入数据长度;也可以遍历字符,找到括号匹配数目,确定容量。三、二叉树遍历与获得树高
1.二叉树遍历
- 先根序遍历 :根,左孩子,右孩子
- 中根序遍历:左孩子, 根,右孩子
- 后根序遍历 :左孩子,右孩子, 根
简单来说,就是将二叉树看成一个多个左右子二叉树组合。
实现思路:就是递归了。简单介绍先根序,代码如下:
//先根遍历 void firstRootVisit(const B_TREE *root) { if (NULL == root) { return; } printf("%c ", root->data); firstRootVisit(root->left); firstRootVisit(root->right); }
F1,输出A,向左孩子走;调用F2,输出B,向左孩子走;调用F3,输出D,向左孩子走;调用F4,输出F,向左孩子走;
调用F5,root 为0,(黑线),退回到F4,向右孩子走;调用F6,root 为0,(黑线),退回到F3,
向右孩子走;调用F7,输出G,等等//中根遍历 void middleRootVisit(const B_TREE *root) { if (NULL == root) { return; } middleRootVisit(root->left); printf("%c ", root->data); middleRootVisit(root->right); } //后跟遍历 void lastRootVisit(const B_TREE *root) { if (NULL == root) { return; } lastRootVisit(root->left); lastRootVisit(root->right); printf("%c ", root->data); }
2.二叉树获得树高
基本思路:
1.遍历
2.记录当前递归深度。
3.比较每次最深深度
4.返回最深深度
我们知道,递归调用时,每调用一次,是深入一层,返回时仍是当初深度。但是如何比较每次深入的最大深度呢?
使用静态存储变量。//树深 static int treeDeep(const B_TREE *root, int level) { static int maxLevel = 0;//保存最大深度 if (root == NULL) { return maxLevel;//结束 } maxLevel = maxLevel < level ? level : maxLevel;//当前深度和最大深度比较 treeDeep(root->left, level + 1);//向左孩子方向,进入下一深度 treeDeep(root->right, level + 1);//向右孩子方向,进入下一深度 return maxLevel; } //最大数深 int getTreeDeep(const B_TREE *root) { return treeDeep(root, 1); }
四、总结
1.编程需要考虑长远性。工具终会使用。
2.递归很巧妙。一定要多分析,从而掌握。
3.灵活多变,不拘泥·。
笔者水平有限,目前只能描述以上问题,如果有其他情况,可以留言,有错误,请指教,有继续优化的,请分享,谢谢!
本篇文章是否有所收获?阅读是否舒服?又什么改进建议?希望可以给我留言或私信,您的的分享,就是我的进步。谢谢。
完整代码有点长,准备弄个文档。或链接。2020年03.18 家
-
谭浩强C语言程序设计,C++程序设计,严蔚敏数据结构,高一凡数据结构算法分析与实现.rar
2013-06-13 22:35:212.1 算法的概念 21 2.2 简单算法举例 21 2.3 算法的特性 24 2.4 怎样表示一个算法 24 2.4.1 用自然语言表示算法 24 2.4.2 用流程图表示算法 24 2.4.3 三种基本结构和改进的流程图 28 2.4.4 用N-S 流程图表示算法 29 ... -
湖南文理学院2019上学期(大三下)计算机科学与技术专业网络安全,密码学复习提纲(可直接打印).pdf
2019-07-19 10:16:19A.RSA 算法可用于某种数字签名方案 B.RSA 算法的运算速度比 DES 慢 C.RSA 算法是一种对称加密算法 D.RSA 的安全性主要基于素因子分解的难度 分组密码有多个工作模式,它们也对保密安全性影响很大,其中,只能... -
最权威的C++教程_C++_Primer_Plus中文第五版+C++_Primer中文第四版(都含源码+习题)(共4分卷)分卷1
2010-06-23 17:33:55它还提供了高效的通用算法库,这些算法可用于STL容器,也可用于常规数组。模板类 valarray为数值数组提供了支持。 第17章:输入、输出和文件 本章复习C++ I/O,并讨论如何格式化输出。读者将要学习如何使用类... -
最权威的C++教程_C++_Primer_Plus中文第五版+C++_Primer中文第四版(都含源码+习题)(共4分卷)分卷2
2010-06-23 17:47:19它还提供了高效的通用算法库,这些算法可用于STL容器,也可用于常规数组。模板类 valarray为数值数组提供了支持。 第17章:输入、输出和文件 本章复习C++ I/O,并讨论如何格式化输出。读者将要学习如何使用类... -
最权威的C++教程_C++_Primer_Plus中文第五版+C++_Primer中文第四版(都含源码+习题)(共4分卷)分卷3
2010-06-23 18:03:39它还提供了高效的通用算法库,这些算法可用于STL容器,也可用于常规数组。模板类 valarray为数值数组提供了支持。 第17章:输入、输出和文件 本章复习C++ I/O,并讨论如何格式化输出。读者将要学习如何使用类... -
软件工程-理论与实践(许家珆)习题答案
2011-01-12 00:49:42A) 作为需求分析阶段用户与开发者之间交流信息的工具 B) 对系统的数据结构进行描述 C) 对目标系统的层次结构进行描述 D) 作为分析和设计的工具 8. 数据字典是数据流图中所有元素的定义的集合,一般由以下四类... -
操作系统(内存管理)
2009-09-20 12:55:25以下是该算法的略述: 清单 5. 主分配程序的伪代码 1. If our allocator has not been initialized, initialize it. 2. Add sizeof(struct mem_control_block) to the size requested. 3. start at managed_... -
算法这部分内容非常重要,如果你不知道如何学习算法的话,可以看下我写的: 算法学习书籍+资源推荐 。 如何刷Leetcode? 常见算法问题总结: 几道常见的字符串算法题总结 几道常见的链表算法题总结 剑指 offer ...
-
算法这部分内容非常重要,如果你不知道如何学习算法的话,可以看下我写的: 算法学习书籍+资源推荐 。 如何刷Leetcode? 常见算法问题总结: 几道常见的字符串算法题总结 几道常见的链表算法题总结 剑指 offer ...
-
算法这部分内容非常重要,如果你不知道如何学习算法的话,可以看下我写的: 算法学习书籍+资源推荐 。 如何刷Leetcode? 常见算法问题总结: 几道常见的字符串算法题总结 几道常见的链表算法题总结 剑指 offer ...
-
C++程序设计语言(特别版)--详细书签版
2012-04-23 07:13:03本版本是高清版,是第1版第18次印刷,是书签最全最好的版本。 基本信息 原书名: The C++ Programming ...16.2.2 有基类的容器 388 16.2.3 stl容器 391 16.3 向量 392 16.3.1 类型 393 16.3.2 迭代器 394 16.3.3... -
C++程序设计语言(特别版)--课后习题源代码
2012-04-23 07:37:34提供的是本书的课后习题源代码,也就是《C++程序设计语言(特别版)题解》的源代码。非书中源代码。 本版本是高清版,是第1版第18次印刷,是书签最全最好的版本。 基本信息 原书名: The C++ ...16.2.2 有基类的... -
维基百科:数学基础(zslcn周生烈编译摘注评)
2014-02-06 21:54:45其自古以来 一直是作为 理性探讨真理性和严谨性的一种范型,并作为 其他科学(特别是物理学)的工具,甚至是基础。在19世纪中,数学的 趋于更高抽象的 许多开发,带来了新的挑战和悖论,迫切需要对数学真理的本性和准则... -
数据结构(C++)有关练习题
2008-01-02 11:27:1831 习题9 排序------------------------------------------------------------------------------------34 第1部分 C++基本知识 各种数据结构以及相应算法的描述总是要选用一种语言工具。在计算机科学... -
C++程序设计语言(特别版)--源代码
2012-04-23 07:33:51提供的是书中的源代码,非课后练习源代码。 本版本是高清版,是第1版第18次印刷,是书签最全最好的版本。 基本信息 原书名: The C++ Programming ...16.2.2 有基类的容器 388 16.2.3 stl容器 391 16.3 向量 392... -
c语言编写单片机技巧
2009-04-19 12:15:17答:对于复杂而开发时间紧的项目时,可以采用C语言,但前提是要求对该MCU系统的C语言和C编译器非常熟悉,特别要注意该C编译系统所能支持的数据类型和算法。虽然C语言是最普遍的一种高级语言,但不同的MCU厂家其... -
内存管理内存管理内存管理
2011-04-04 20:16:26如前所述,被映射的内存的边界(最后一个有效地址)常被称为系统中断点或者当前中断点。在很多 UNIX? 系统中,为了指出当前系统中断点,必须使用 sbrk(0) 函数。sbrk 根据参数中给出的字节数移动当前系统中断点,... -
net学习笔记及其他代码应用
2010-11-16 18:15:09声明方法的存在而不去实现它的类被叫做抽象类(abstract class),它用于要创建一个体现某些基本行为的类,并为该类声明方法,但不能在该类中实现该类的情况。不能创建abstract 类的实例。然而可以创建一个变量,其... -
oracle学习文档 笔记 全面 深刻 详细 通俗易懂 doc word格式 清晰 连接字符串
2017-05-06 20:26:52八、 常用的工具 Sql Plus Sql Developer Oracle Enterprise Manager 第二章 用户和权限 一、 用户介绍 ORACLE用户是学习ORACLE数据库中的基础知识,下面就介绍下类系统常用的默认ORACLE用户: 1. ...
-
Jvm复习-01
-
914. 卡牌分组
-
【ACWing】1012. 友好城市
-
MHA 高可用 MySQL 架构与 Altas 读写分离
-
MySQL NDB Cluster 负载均衡和高可用集群
-
用python爬取百度信息来制作疫情图
-
牛牛量化策略交易
-
F5查询及切换脚本.zip
-
基于Flink+Hudi构建企业亿级云上实时数据湖教程(PC、移动、小
-
微信arm64for树莓派4B+
-
MySQL 备份与恢复详解(高低版本 迁移;不同字符集 相互转换;表
-
使用vue搭建微信H5公众号项目
-
QtitanRibbon3.7z
-
bootstrap-5.0.0-beta2-dist.zip
-
华为1+X——网络系统建设与运维(高级)
-
MySQL 事务和锁
-
使用 Linux 平台充当 Router 路由器
-
文件资源管理器中图标.reg
-
RuntimeError: cuDNN error: CUDNN_STATUS_MAPPING_ERROR RuntimeError: cannot join current thread
-
双向DC-DC变换器设计任务说明书.docx