数据结构之二叉查找树的定义与实现
二叉查找树基础二叉查找树是指一种满足以下性质的二叉树：
1. 对于每个节点X，该节点的所有左子树节点关键字值小于该节点关键字值
2. 该节点的所有右子树节点关键字值大于该节点关键字值
3. 关键字需要支持“>”、“<”、“==”运算符
对于二叉树ADT，一般需要提供如下操作：
清空二叉
...
表达式树的定义与后缀表达式构造表达式树
发表于
|
分类于
数据结构
表达式树基础知识表达式树是一类树，其基本结构为所有的叶节点为操作树，非叶节点为操作符。如下图所示为一种表达式树：
对于二元操作符，其形成的操作树是一种二叉树。对二叉表达式树进行不同的遍历得到不同的的表达式，当进行前序遍历时，得到的表达式称为前缀表达式，如上图前缀表达式为++a*bc*+*defg；
...
二叉树的前序遍历、中序遍历、后序遍历的递归实现以及非递归实现
发表于
|
分类于
数据结构
二叉树遍历的基本原理先上一张前、中、后序遍历的路径图：图片来源
如上图二叉树的遍历结果为：
前序遍历为：ABDEFGC
中序遍历为：DBFEGAC
后序遍历为：DFGEBCA
由于树的定义是递归定义，因此自然而然遍历思路也是从递归遍历入手。二叉树的递归定义如下：
二叉树是由n个有限节点构成的
...
数据结构之多维数组及特殊矩阵的压缩存储
发表于
|
分类于
数据结构
基本知识多维数组可以认为是线性表的一种推广，其元素本身可以是具有某种结构的数据，但必须是同种元素。数组在实际存储时采取的顺序存储，因此数组可以以$O(1)$的时间复杂度进行访问。对于一维数组，其元素内存地址可通过起始地址+偏移地址的方式直接计算得到；而对于多维数组，根据存储方式的不同，计算元素地址的
...
数据结构之队列的定义与实现
发表于
|
分类于
数据结构
队列基础知识和栈类似，队列也是一种线性表，不过队列是在一端插入在另外一端删除。插入的一端称为队尾，删除的一端称为队头。队列的基本操作是入队和出队。由于队列的插入删除特性，因此队列具有“先进先出(FIFO)”的特点。同理，使用顺序表实现的队列称为顺序队列，使用链表实现的队列称为链式队列。队列采用数组实
...
数据结构之栈的定义与实现
发表于
|
分类于
数据结构
栈基础知识栈(stack)是一种限制插入和删除只能在一端进行的线性表，允许插入删除的一端称为栈顶，另一端称为栈底。栈的基本操作有进栈(push)和出栈(pop)。当栈中不存在任何元素时称为空栈，此时进行出栈操作或者读取栈顶元素是一种错误。栈的实现既可以通过顺序表，也可以使用链表来实现。使用顺序表实现
...