Java二进制搜索树递归副本树 [英] Java Binary Search Tree Recursive Copy Tree
问题描述
我正在解决一个问题,该问题要求我递归复制二进制搜索树并返回该树.我在二进制搜索树类中进行编码,因此它将复制它被调用的任何二进制搜索树.要求说私有方法必须具有返回类型Entry<E>
和参数类型Entry<E>
.我遇到的问题是将多个条目添加到树中.
I'm working on a problem which requires me to copy a binary search tree recursively and to return the tree. I am coding in the binary search tree class, so it will copy whatever binary search tree it is called on. The requirements say that the private method must have a return type of Entry<E>
and a parameter of type Entry<E>
. The problem I'm running into is getting multiple entries added to the tree.
这是我目前拥有的:
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类,所以您知道我可以得到的东西:
And here is Entry class so you know what I have available to me:
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;
}
这不会复制任何内容.它将返回当前节点的最左侧(如果没有左侧子节点,则为最右侧;如果是叶节点,则为当前节点).因为您总是返回电流.您需要类似的东西:
This will not copy anything. It will return the left-most ( or right-most, if no left child; or current, if it is a leaf node ) child of the current node. Because you always return current. You need somelthing like:
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
}
并实际上复制节点.我尚未测试代码,但为时已晚,希望它仍然正确.
and actually copy the nodes. I haven't tested the code and it is bit late, hope it is still correct.
您是否有理由区分BinarySearchTree<E>
和Entry<E>
?树的一部分不是树吗?
Is there a reason you distinguish between BinarySearchTree<E>
and Entry<E>
? Isn't a part of the tree also a tree?
这篇关于Java二进制搜索树递归副本树的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!