递归地检索二叉搜索树的子集

Question

对于二叉树 object 我正在使用私有字段

X key;
Y value;
Tree<X,Y> left;
Tree<X,Y> right;

我有一个方法 public Tree<X,Y> subset(X startKey, X endKey) 需要 return 一棵树，包括 startKey 节点和 endKey 节点之间的所有键，以及他们对应的值。这个方法也需要使用递归来执行。

我遇到的问题是我无法找到一种方法来获取以 endKey 结尾的树（可能看起来像 LinkedList），但不包括 endKey.left和 endKey.right。我想我应该首先在根的左树或右树上递归调用该方法，具体取决于 startKey 是大于还是小于根键，所以：

if (this.key.compareTo(startKey) < 0) this.right.subset(startKey, endKey);
else if (this.key.compareTo(startKey > 0) this.right.subset(startKey, endKey);

这将继续在树中导航，直到它到达包含键 startKey 的节点。当我到达那个点时，我将 this 复制到一个新树，这样我就可以避免编辑原始树。这棵新树以 startKey 为根节点，然后与原来的 children 相同。

这就是我卡住的地方。我知道我必须处理的问题是导航到 endKey，确保我停在那里并且不包括 endKey.left 或 endKey.right，以及 return 子集即使方法是来自递归调用的 "unwinding" 也是正确的。我在想，如果我想在 endKey 处停止，我将不得不以某种方式保留对其 parent 节点的引用，以便我可以设置 parent 节点的左侧或右侧child 到 key/value 对，以切断 endKey 的其余 children。但是，由于我实际上没有节点 object，而且我无法添加任何方法或构造函数，所以我不知道如何维护对 parent 的引用树。我也不知道如何在保持 startKey 作为新树的根的同时尝试实现这一目标。

换句话说，我想我已经设法获得了从较低级别开始并一直延伸到原始树底部的树的子集。我怎样才能递归地消除我不想要的底部的 children 和我的新子集 return？

Answer 1

如果你把它当作一个视图你实际上并没有把它剪掉，你只是把方法限制在子集的范围内。当使用 iterator() 例如子图只有自己的 Iterator 实现，它从子图的下限开始，只有 returns hasNext() == false 当达到上限时。用户不会注意到他实际上是在遍历原始树，因为它完全隐藏了。我希望这个例子能让你对此有所了解。

public interface Tree<X, Y> extends Iterable<Tree<X, Y>> {
    X getKey();
    X getValue();
    Tree<X, Y> floor(X key);
    Tree<X, Y> ceiling(X key);
    Tree<X, Y> subTree(X lo, X hi);
    // ...
}

public class TreeImpl<X, Y> implements Tree<X, Y> {
    final X key;
    Y value;
    TreeImpl<X, Y> left, right;

    public TreeImpl(X key, Y value) {
        this.key = key;
        this.value = value;
    }

    @Override
    public Iterator<Tree<X, Y>> iterator() {
        return new TreeItr();
    }

    // Iterator starting at the most left to the most right;
    private class TreeItr implements Iterator<Tree<X, Y>> {
        // ...
    }

    @Override
    public Tree<X, Y> subTree(X lo, X hi) {
        return new SubTree<>(this, lo, hi);
    }

    private static class SubTree<X, Y> implements Tree<X, Y> {
        final Tree<X, Y> backing;
        final X lo, hi;

        public SubTree(Tree<X, Y> backing, X lo, X hi) {
            this.backing = backing;
            this.lo = lo;
            this.hi = hi;
        }

        @Override
        public Iterator<Tree<X, Y>> iterator() {
            return new SubTreeItr(backing.ceiling(lo), backing.floor(hi))
        }

        // Iterator starting at 'from' and returning 'hasNext() == false' after 'to'
        // has returned
        private class SubTreeItr implements Iterator<Tree<X, Y>> {
            final Tree<X, Y> from, to;

            public SubTreeItr(Tree<X, Y> from, Tree<X, Y> to) {
                this.from = from;
                this.to = to;
            }

            //...
        }

        @Override
        public Tree<X, Y> subTree(X lo, X hi) {
            // Check if lo > this.lo && hi < this.hi
            return new SubTree<>(backing, lo, hi);
        }
    }
}

递归地检索二叉搜索树的子集

Retrieving a subset of a binary search tree recursively

java

tree

recursion

binary-tree

binary-search-tree