logo标签列表

在BST中查找所有关键字位于给定范围内的子树

algorithmbinary-search-treetree-traversalrange-query
5
我在最近的面试中得到了这个问题：给定一个二叉搜索树（BST），其节点包含一个整数值，找到所有子树，其中节点落在整数X（最小值）和Y（最大值）之间，其中X
我已经解决了这个问题的变体，例如 - 打印在给定范围内的BST键。但是无法弄清楚这个问题，因为它涉及查找满足非常特定约束条件的主图/树的所有连接子图。任何指针/帮助/伪代码将不胜感激。
附加说明：
1.问题定义了具有左指针、右指针和整数值的节点数据结构。没有办法标记节点。 2.被要求用Java解决此问题。 3.当我说子树/子图时，我指的是一组连接的节点，而不是不相交节点列表。很抱歉造成困扰。
请通过选择答案来回应，以便我们知道给定问题的最佳答案。 - Sumeet
4个回答
1
这个问题其实很简单。为了避免子树重叠，我在每个节点上都加了一个标记字段，初始值为false。
算法如下：
使用DFS方法从根节点开始遍历BST。如果在DFS中遇到一个未标记且满足约束条件（介于X和Y之间）的节点，则存在以该节点为根的子树解，但我们不知道该子树有多大。因此，需要执行以下操作：
将其左右子节点传递给另一个名为check的方法，该方法将执行以下操作：
遍历以该节点为根的子树，并按照DFS方式遍历，只要满足约束条件并且遇到的节点未被标记即可。一旦违反任何一个条件，就返回。
现在，原始的DFS方法可能会在已标记的顶点上调用，但if条件将计算为false。因此，达到了目标。
我使用JAVA语言解决了它，对于键位于10和21之间（不包括）的条件。下面是代码：
还有一件事，如果在“以X为根，带有子节点的子树”之后没有打印任何内容，则表示该子树仅具有单个节点。
class BST
{
 public Node insert(Node x,int key)
 {
     if(x==null)
      return new Node(key,null,null,false);
     else if(key>x.key)
     {
         x.right=insert(x.right,key);
         return x;
     }
     else if(key<x.key)
     {
         x.left=insert(x.left,key);
         return x;
     }
     else {x.key=key;return x;}
 }

 public void DFS(Node x)
 {
     if(x==null)
     return;
     if(x.marked==false&&x.key<21&&x.key>10)
     {
         System.out.println("Subtree rooted at "+x.key+" with childs as");
         x.marked=true;
         check(x.left);
         check(x.right);
     }
     DFS(x.left);
     DFS(x.right);

 }
 public void check(Node ch)
 {
     if(ch==null)
      return;
     if(ch.marked==false&&ch.key<21&&ch.key>10)
     {
         System.out.println(ch.key);
         ch.marked=true;
         check(ch.left);
         check(ch.right);
     }
     else return;

 }
 public static void main(String []args)
 {
     BST tree1=new BST();
     Node root=null;
     root=tree1.insert(root,14);
     root=tree1.insert(root,16);
     root=tree1.insert(root,5);
     root=tree1.insert(root,3);
     root=tree1.insert(root,12);
     root=tree1.insert(root,10);
     root=tree1.insert(root,13);
     root=tree1.insert(root,20);
     root=tree1.insert(root,18);
     root=tree1.insert(root,23);   
     root=tree1.insert(root,15);
     tree1.DFS(root);
 } 
}
class Node
{
 Node left,right;
 int key;
 boolean marked;
 Node(int key,Node left,Node right,boolean b)
 {
  b=false;   
  this.key=key;
  this.left=left;
  this.right=right;
 }
}

如有任何问题，请随时提出。

1
具体的解决方案取决于子树的定义。考虑以下二叉搜索树：
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（因为当前节点包含在给定范围内）。如果我们不能拆分树，则只需传播递归调用的结果。
最后，如果两个子节点都存在。如果其中一个不在范围内，我们将其切断（如果允许）。如果不允许，我们将位于给定范围内的子树添加到结果列表中。
1
这可以通过递归完成，我们保留子树列表并在找到符合要求的子树时进行追加。当以参数节点为根的子树完全在范围内时，递归函数返回true。调用者（即父节点）决定在子节点的递归调用返回true或false时该怎么做。例如，如果当前节点值在范围内，且其子节点的子树也完全在范围内，则我们只需返回true。但是，如果其中一个子节点的子树在范围内，而另一个不在范围内，则我们返回false（因为当前节点子树并非全部都在范围内），但我们也将在范围内的子节点追加至列表中。如果当前节点值不在范围内，则我们返回false，但我们还会检查左侧或右侧的子节点，并将其追加到子树列表中（如果它符合要求）。
def subtree_in_range(root, x, y):
  def _subtree_in_range(node):
    in_range=True
    if node:
      if node.val>=x and node.val<=y:
        if not _subtree_in_range(node.left):
          in_range=False
          if node.right and _subtree_in_range(node.right):
            l.append(node.right)
        elif not _subtree_in_range(node.right):
          in_range=False
          if node.left:
            l.append(node.left)
      else:
        in_range=False
        s=node.left
        if node.val<x:
          s=node.right
        if s and _subtree_in_range(s):
          l.append(s)
    return in_range

  l=[]
  if _subtree_in_range(root):
    l.append(root)
  return l
1
当进行范围搜索时，用某种通用语言编写的范围搜索工作函数可能是这样的：
function range(node, results, X, Y) 
{
    if node is null then return
    if node.key is in [X, Y] then results.add(node.key)
    if node.key < Y then range(node.right, results, X, Y)
    if node.key > X then range(node.left, results, X, Y)
}

对于子树版本问题，我们需要存储子树根节点而不是键，并跟踪我们是否在子树中。后者可以通过在范围调用中传递子树父节点来解决，这也是新结构创建所需的。期望的函数如下。正如您所看到的，主要变化是一个额外的参数和node.key in [X, Y]分支。
function range_subtrees(node, parent, results, X, Y) 
{
    if node is null then return

    node_clone = null 

    if node.key is in [X, Y] then 
        node_clone = node.clone()
        if parent is null then 
            results.add(node_clone)
        else
            parent.add_child(node_clone)

    if node.key < Y then range_subtrees(node.right, node_clone, results, X, Y)
    if node.key > X then range_subtrees(node.left, node_clone, results, X, Y)
}

这应该创建一个子树根节点的集合，每个子树都是原始树结构的副本。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接