二叉搜索树 BST：查找、插入与删除
二叉搜索树 BST：查找、插入与删除 在普通二叉树里，左右孩子的位置本身并不一定携带数值上的顺序信息。也就是说，虽然我们能遍历整棵树，但如果想高效查找某个值，普通二叉树未必比线性扫描好多少。二叉搜索树...
标签：数据结构教程
线索二叉树：让遍历更高效的思路
线索二叉树：让遍历更高效的思路 学二叉树遍历时，我们已经知道，前序、中序、后序遍历最自然的写法通常是递归。即使不用递归，也往往需要额外借助栈来保存访问状态。这说明一件事：普通二叉链表虽然能很好地表达父...
二叉树遍历：前序、中序、后序与层序
二叉树遍历：前序、中序、后序与层序 学完树的基本概念之后，二叉树里最先必须掌握的一件事，就是遍历。因为二叉树本身只是节点和左右孩子之间的组织关系，真正要做查找、统计、打印、构造、序列化时，第一步几乎总...
树的基本概念与存储结构
树的基本概念与存储结构 如果说前面的顺序表、链表、栈、队列都还属于“一条线上的世界”，那么从树开始，数据结构学习就正式进入了“层级世界”。树最大的不同在于，它不再只是简单地表示前后顺序，而是能够表示从...
稀疏数组、广义表与矩阵压缩存储
稀疏数组、广义表与矩阵压缩存储 在线性结构和字符串这些基础内容之后，数据结构学习很快就会碰到一个现实问题：并不是所有数据都适合“老老实实一个位置存一个值”这种最直白的方式。很多时候，原始数据虽然看起来...
串：字符串的存储与基础操作
串：字符串的存储与基础操作 在线性结构里，串看起来像是一个很熟悉、甚至有点“太常见以至于容易被忽略”的主题。因为无论是 C 里的字符数组，还是 Java、Go、Python 里的字符串对象，我们几乎每...
队列与双端队列：先进先出结构及其变体
队列与双端队列：先进先出结构及其变体 如果说栈代表的是“最近进入的内容最先处理”，那么队列代表的就是另一种同样高频、但完全不同的秩序：先进先出。最早进入队列的元素，应该最先离开；后来进入的元素，则排在...
栈：后进先出结构与典型应用
栈：后进先出结构与典型应用 学完顺序表和链表之后，一个很自然的问题就是：这些基础结构本身能不能进一步抽象成更有明确访问约束的模型？答案当然可以，而栈就是最经典的第一类。它不再允许你像线性表那样在任意位...
链表：单链表、双链表与循环链表
链表：单链表、双链表与循环链表 学完顺序表之后，很多人会自然产生一个问题：既然数组按下标访问这么快，为什么还需要链表？答案就在顺序表最明显的短板里。顺序表依赖连续空间，访问位置很快，但一旦要在中间插入...
顺序表与动态数组：最常见的线性表起点
顺序表与动态数组：最常见的线性表起点 如果说线性结构是很多数据结构学习的起点，那么顺序表几乎就是这个起点里的“第一站”。因为它背后的思路既直观又高频：把一组逻辑上有先后顺序的元素，按照连续的存储位置放...