51dev.com IT技术开发者社区

51dev.com 技术开发者社区

5.3 删除二叉搜索树的最大元素和最小元素

5.3 删除二叉搜索树的最大元素和最小元素

在5.2中完成了树的遍历,这一节中将对如何从二叉搜索树中删除最大元素和最小元素做介绍:我们要想删除二分搜索树的最小值和最大值,就需要先找到二分搜索树的最小值和最大值,其实也还是很容易的,因为根据二叉搜索树的特点,它的左子树一定比当前节点要小,所以二叉搜索树的最小值一定是左子树一直往下走,一直走到底。...

uni-app开发小程序准备阶段

uni-app开发小程序准备阶段

开始之前,开发者需先下载安装如下工具:HBuilderX:官方IDE下载地址下面开发工具根据需求进行安装: 微信小程序开发工具安装 https://developers.weixin.qq.com/miniprogram/dev/devtools/download.html支付宝...

5.2二叉搜索树遍历(前序、中序、后序、层次、广度优先遍历)

5.2二叉搜索树遍历(前序、中序、后序、层次、广度优先遍历)

 前言:在上一节中,我们对树及其相关知识做了了解,对二叉搜索树做了基本的实现,下面我们继续完善我们的二叉搜索树。对于二叉树,有深度遍历和广度遍历,深度遍历有前序、中序以及后序三种遍历方法,广度遍历即我们寻常所说的层次遍历,如图:因为树的定义本身就是递归定义,所以对于前序、中序以及后序这三种...

5.1二叉搜索树基础

5.1二叉搜索树基础

前言:本文通过先通过了解一些二叉树基础知识,然后在转向学习二分搜索树。树(Tree)是n(n>=0)个节点的有限集。n=0时称为空树。在任意一颗非空树中:(1)有且仅有一个特定的称为根(Root)的节点;(2)当n>1时,其余节点可分为m(m>0)个互不相交的有限集T1、T2、.....

4.3递归运行的机制:递归的微观解读

4.3递归运行的机制:递归的微观解读

前言:在4.1节和4.2节中我们分别通过数组以及链表对递归进行了应用,那时我们只是对递归进行了宏观理解--递归是将问题化为更小问题的子过程。这一节我们对在4.1节中递归在数组中的应用和4.2节中递归在链表中的应用进行微观解读:1)我们先来看看4.1节中的代码实现,如下图:为了更好的进行分析,我们将上...

4.2链表的天然递归结构性质

4.2链表的天然递归结构性质

有关链表,参考之前的文章学习。要求:使用递归删除链表中指定的所有元素值。假设有这么一个链表,如下图:分析:基于链表的宏观语意(递归是问题更小的子过程)进行分析我们可以把上述链表看成是一个头结点后面挂接了一个更小的链表组成,如下图:此时我们可以把链表概括成如下的链表结构:1、在一个头结点+更小的链表基...

4.1递归基础与递归的宏观语意

4.1递归基础与递归的宏观语意

1.什么是递归本质上,将原来的问题,转化为更小的同一问题2.例子分析假设我们需要对数组进行求和操作(只是为了更好理解递归程序)要求如下:求解从索引为0到n-1的数组元素和。分析:为了能求解从索引为0到n-1的数组元素和,可以分解为第0个数加上索引从1到n-1的数组元素和,如下:此时求解索引从1到n-...

3.7链表应用--基于链表实现队列--尾指针

3.7链表应用--基于链表实现队列--尾指针

在开始栈的实现之前,我们再来看看关于链表的只在头部进行的增加、删除、查找操作,时间复杂度均为O(1)。  对于队列这种数据结构,需要在线性结构的一端插入元素,另外一端删除元素。因此此时基于链表来实现队列,则有一端的时间复杂度为O(n)。因此我们不能使用之前已经实现的链表结构,我们...

3.6链表应用--基于链表实现栈

3.6链表应用--基于链表实现栈

在上几小节中我们实现了基本的链表结构,并在上一节的底部给出了有关链表的源码,此处在贴一次吧,猛戳在开始栈的实现之前,我们再来看看关于链表的只在头部进行的增加、删除、查找操作,时间复杂度均为O(1),基于链表的这几个优势,我们在此基础上实现栈。 前言,在写本小节之前,我们已经实现了一个基于静...

3.5链表----链表中元素的删除(只删除一个元素情况)

3.5链表----链表中元素的删除(只删除一个元素情况)

该部分与上一节是息息相关的,关于如何在链表中删除元素,我们一步一步来分析:假设我们需要在链表中删除索引为2位置的元素,此时链表结构为: 若要删除索引为2位置的元素,需要获取索引为2位置的元素之前的前置节点(此时为索引为1的位置的元素),因此我们需要设计一个变量prev来记录前置节点。1.初...

3.4链表----链表中元素的获取、查询和修改

3.4链表----链表中元素的获取、查询和修改

本节是在上一小节的基础上继续完善我们的链表相关方法的编写,在本节中我们着重对如何获取链表中元素、查询元素以及修改元素进行学习。由于我们使用了虚拟头结点,而我们每次都需要从第一个真实节点开始,因此需要首先得到虚拟头结点的下一个节点是谁,然后在此基础上进行遍历工作,相关代码如下://获取链表的第inde...

3.3链表----在链表中添加元素详解--使用链表的虚拟头结点

3.3链表----在链表中添加元素详解--使用链表的虚拟头结点

在上一小节中关于在链表中头部添加元素与在其他位置添加元素在逻辑上有所差别,这是由于我们在给链表添加元素时需要找到待添加元素位置的前一个元素所在的位置,但对于链表头来说,没有前置节点,因此在逻辑上就特殊一些,操作方式也就有所差别,需单独处理。为了针对头结点的操作方式与其他方式一致:接下来我们就一步一步...

3.2链表----在链表中添加元素详解

3.2链表----在链表中添加元素详解

1.1基本的链表结构:1.2对于链表来说,若想访问链表中每个节点则需要把链表的头存起来,假如链表的头节点为head,指向链表中第一个节点,如图:1.3使用代码表示此时的链表//定义头节点privateNodehead;//节点个数privateintsize;//无参数构造函数publicLinke...

3.1链表----链表(Linked List)入门

3.1链表----链表(Linked List)入门

在分析链表之前,我们先来对之前的动态数组、栈、队列总结一下:(1)底层依托于静态数组(2)依靠resize解决固定容量问题 (3)是一种假的的动态数据结构1.什么是链表可以从以下两个部分来理解什么是链表(1)最简单的动态数据结构,是一种真正的动态数据结构;(2)是一种数据的存储方式,数据存...

2.5循环队列

2.5循环队列

在正式进行循环队列学习之前,我们先来看看在顺序队列中删除队首元素出现的问题(1)设一个容量为capacity=8,size=5(a,b,c,d,e)的数组,左侧为队首、右侧为队尾。(2)出队一个元素后,需整体往前移动一位#出队  #2整体前移一位关于该种操作方式我们很容易得出时间...