具体的解决方案取决于子树的定义。考虑以下二叉搜索树:
5
3
2
4
8
-
9
我们想要找到范围为
[4,8]
的子树。很明显,
4
节点属于输出结果。但是另一半树呢?如果一个子树涉及到所有子节点,则它是完整的结果。如果一个子树实际上是输入节点的子集,则节点
5
和
8
属于结果,但它们与
3
和
9
节点的连接必须被剥离。
无论如何,以下算法都可以处理这两种情况。预处理器定义WHOLE_SUBTREES
定义了子树是否是具有所有子节点的完整子组件。
static List<BSTNode> FindSubtreesInRange(BSTNode root, int rangeMin, int rangeMax)
{
var result = new List<BSTNode>();
if (IsTreeWithinRange(root, rangeMin, rangeMax, int.MinValue, int.MaxValue, result))
result.Add(root);
return result;
}
static bool IsTreeWithinRange(BSTNode root, int rangeMin, int rangeMax, int treeRangeMin, int treeRangeMax, List<BSTNode> resultList)
{
if (treeRangeMin >= rangeMin && treeRangeMax <= rangeMax)
return true;
if ( treeRangeMin > rangeMax || treeRangeMax < rangeMin)
return false;
if (root.Key < rangeMin)
{
if (root.Right != null && IsTreeWithinRange(root.Right, rangeMin, rangeMax, root.Key + 1, treeRangeMax, resultList))
resultList.Add(root.Right);
return false;
}
if (root.Key > rangeMax)
{
if (root.Left != null && IsTreeWithinRange(root.Left, rangeMin, rangeMax, treeRangeMin, root.Key, resultList))
resultList.Add(root.Left);
return false;
}
if (root.Left == null && root.Right == null)
return true;
if (root.Left == null)
{
#if WHOLE_SUBTREES
if (!IsTreeWithinRange(root.Right, rangeMin, rangeMax, root.Key + 1, treeRangeMax, resultList))
root.Right = null;
return true;
#else
return IsTreeWithinRange(root.Right, rangeMin, rangeMax, root.Key + 1, treeRangeMax, resultList);
#endif
}
if (root.Right == null)
{
#if WHOLE_SUBTREES
if (!IsTreeWithinRange(root.Left, rangeMin, rangeMax, treeRangeMin, root.Key, resultList))
root.Left = null;
return true;
#else
return IsTreeWithinRange(root.Left, rangeMin, rangeMax, treeRangeMin, root.Key, resultList);
#endif
}
var leftInRange = IsTreeWithinRange(root.Left, rangeMin, rangeMax, treeRangeMin, root.Key, resultList);
var rightInRange = IsTreeWithinRange(root.Right, rangeMin, rangeMax, root.Key + 1, treeRangeMax, resultList);
if (leftInRange && rightInRange)
return true;
#if WHOLE_SUBTREES
if (!leftInRange)
root.Left = null;
if (!rightInRange)
root.Right = null;
return true;
#else
if (leftInRange)
resultList.Add(root.Left);
if (rightInRange)
resultList.Add(root.Right);
return false;
#endif
}
这个想法是:如果一个给定节点的只有一个子树在给定范围内,那么它就是新子树的根节点。如果两个子树都在范围内,则它们不是子树的根节点,而是由父级处理相应的决策。
算法从以下开始:我们遍历树并记住键可以在哪些范围内(
treeRangeMin/Max
)。这允许快速检查整个子树是否在给定范围内(
IsTreeWithinRange
方法的第一条语句)。
接下来的两条语句处理当前节点的键不在给定范围内的情况。然后只有其中一个子树可能在范围内。如果是这种情况,则将此子树添加到结果列表中。
接下来,我们检查子树是否存在。如果两个子树都不存在,则当前树完全包含在范围内。
如果只有一个子树存在,则根据是否可以拆分树,操作会有所不同。如果可以拆分树,则发生以下情况:如果子树不在范围内,则将其切断并返回true(因为当前节点包含在给定范围内)。如果我们不能拆分树,则只需传播递归调用的结果。
最后,如果两个子节点都存在。如果其中一个不在范围内,我们将其切断(如果允许)。如果不允许,我们将位于给定范围内的子树添加到结果列表中。