并查集及其应用
概论 定义 并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题（即所谓的并、查）。比如说，我们可以用并查集来判断一个森林中有几棵树、某个节点是否属于某棵树等。 ...
Posts
查找二叉搜索树的中序后继节点
核心思路 对于一个给定的节点，他的中序后继节点有两种情况: 给定节点存在右子树时，中序后继节点即为右子树中的最小值 若不存在右子树，则中序后继节点为给定节点所在的左子树的祖先 ...
如何检查一个二叉树是否为二叉搜索树
原理 搜索二叉树有2个基本性质可以用于判断： 左子树中的所有值都小于等于根节点的值，而右子树中的数据都大于根节点的值。 二叉搜索树的中序输出后数据按照非递减顺序排列 对于第一个性质，假设根节点数据为7，那么左子树最大不能超过7，而右子树都大于7。 所以我们可以在函数中增加参数minValue和maxValue，用来记录此子树中数据的范围。 ...
删除一个二叉搜索树的节点
三种情况 Case 1 删除的节点没有子节点（即该节点为叶节点） 操作：直接delete Case 2 删除的节点下有一个子节点 操作：用左/右子树代替该节点 Case 3 删除的节点有两个子节点 ...
二叉树的遍历
Tree Traversal Tree traversal is a process of visiting each node in the tree exactly once in some order. 树的遍历有2种方式，Breadth-first（广度优先）和Depth-first（深度优先）。 ...