我正在解决一个问题,该问题要求我递归复制二进制搜索树并返回该树。我在二进制搜索树类中进行编码,因此它将复制它被调用的任何二进制搜索树。要求表明,私有方法必须具有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;
}


这是入门课程,所以您知道我能得到的信息:

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;
    }
}

最佳答案

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;
}


这不会复制任何内容。它将返回当前节点的最左侧(如果没有左侧子节点,则返回最右侧;如果是叶节点,则返回当前节点)。因为您总是返回电流。您需要类似的东西:

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>?树的一部分不是树吗?

10-07 22:36