Дерево двоичного поиска Java Рекурсивное дерево копирования - PullRequest
Новая
       9

Дерево двоичного поиска Java Рекурсивное дерево копирования

1 голос
/ 21 марта 2011

Я работаю над проблемой, которая требует от меня рекурсивного копирования бинарного дерева поиска и возврата дерева. Я кодирую в классе бинарного дерева поиска, поэтому он будет копировать любое дерево бинарного поиска, к которому оно обращено. В требованиях говорится, что закрытый метод должен иметь тип возвращаемого значения 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;
    }
}

Ответы [ 2 ]

3 голосов
/ 21 марта 2011 
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>? Разве часть дерева не является деревом?

0 голосов
/ 23 марта 2011

Просто подумал, что поделюсь решением, которое я получил.Моя основная проблема не заключалась в том, чтобы сделать глубокую копию объекта, поэтому он будет ссылаться на объект, а не на создание нового. 

public BinarySearchTree<E> rcopy(){
   BinarySearchTree<E> newTree = new BinarySearchTree<E>();
   newTree.root = rcopy(root);
   newTree.size=newTree.nodes();
   return newTree;
}
private Entry <E> rcopy(Entry <E> current){
   Entry <E> b=new Entry<E>();
   if(current!=null){
      if(current.left!=null)b.left=rcopy(current.left);
      if(current.right!=null)b.right=rcopy(current.right);
      b.element = current.element;
      b.parent = successor(current);
   }
   return b;
}

(наследник - это метод, который возвращает запись объекта, предшествующего ему) Спасибо всем за помощь в решении проблемы!

...