概论

定义

并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题（即所谓的并、查）。比如说，我们可以用并查集来判断一个森林中有几棵树、某个节点是否属于某棵树等。

三种情况

1. Case 1

删除的节点没有子节点（即该节点为叶节点）

操作：直接delete

2. Case 2

删除的节点下有一个子节点

操作：用左/右子树代替该节点

3. Case 3

删除的节点有两个子节点

核心思路

对于一个给定的节点，他的中序后继节点有两种情况:

给定节点存在右子树时，中序后继节点即为右子树中的最小值

若不存在右子树，则中序后继节点为给定节点所在的左子树的祖先

原理

搜索二叉树有2个基本性质可以用于判断：

1. 左子树中的所有值都小于等于根节点的值，而右子树中的数据都大于根节点的值。
2. 二叉搜索树的中序输出后数据按照非递减顺序排列

对于第一个性质，假设根节点数据为7，那么左子树最大不能超过7，而右子树都大于7。

所以我们可以在函数中增加参数minValue和maxValue，用来记录此子树中数据的范围。

Tree Traversal

Tree traversal is a process of visiting each node in the tree exactly once in some order.

树的遍历有2种方式，Breadth-first（广度优先）和Depth-first（深度优先）。

树的介绍

树(Tree)作为一种数据结构，具有一种递归性。一个树可以看作是由根节点(root)以及若干子树构成，而子树又可以继续向下分成根和子树，因此树具有递归性。

二叉树(binary tree)是树中的一种，它满足每个节点都有要么2个要么0个子节点的特性。

二叉搜索树(binary search tree)满足左侧子树中储存的值都小于等于root，而右侧子树上的值都大于root，并且递归满足。

Introduction of Queue

队列作为一种抽象数据结构，遵循First-In-First-Out(FIFO)原则。

前缀、中缀与后缀表达式

计算机中一般使用三种表达式，分别是中缀表达式(Infix)、前缀表达式(Prefix)、后缀表达式(Postfix)。

题目背景

我们都知道，在编程语言中，我们常用多种类型的括号，( )圆括号、[ ]方括号、{ }花括号，当括号不匹配时，编译时会发生错误。那么编译器是如何检验括号匹配性的呢？

Introduction of Stack

栈是一种数据结构，属于抽象数据结构(ADT)，遵循Last-In-First-Out(LIFO)原则。