Java二叉搜索树递归复制树

Question

我正在解决一个问题，它要求我递归地复制二叉搜索树并返回树。我在二叉搜索树类中编码，因此它将复制调用它的任何二叉搜索树。要求说私有(private)方法的返回类型必须是Entry<E>。和一个 Entry<E> 类型的参数.我遇到的问题是将多个条目添加到树中。

这是我目前拥有的:

public BinarySearchTree<E> rcopy(){
   BinarySearchTree newTree = new BinarySearchTree();
   newTree.add(rcopy(root).element);
   return newTree;
}


private Entry <E> rcopy(Entry <E> current){
   if(current.left!=null) return rcopy(current.left);
   if(current.right!=null) return rcopy(current.right);
   return current;
}

这里是 Entry 类，所以你知道我可以使用什么:

protected static class Entry<E> {
    protected E element;
    protected Entry<E> left = null,
                       right = null,
                       parent;
    protected int  pos;
protected Entry<E> link = null;
public Entry() { }
    public Entry (E element, Entry<E> parent) 
{
       this.element = element;
       this.parent = parent;
    }
}

Answer 1

private Entry <E> rcopy(Entry <E> current){
   if(current.left!=null) return rcopy(current.left);
   if(current.right!=null) return rcopy(current.right);
   return current;
}

这不会复制任何东西。它将返回当前节点的最左边(或最右边，如果没有左 child ；或当前，如果它是叶节点) child 。因为你总是返回电流。你需要这样的东西:

private Entry <E> rcopy(Entry <E> current){
    if (current == null) return null;
    return new Entry <E> (current.element, rcopy(current.left), rcopy(current.right)); //write a constructor for that
 }

并实际复制节点。我还没有测试代码，有点晚了，希望它仍然是正确的。

你区分 BinarySearchTree<E> 有什么原因吗？和 Entry<E> ？树的一部分不也是树吗？