Java Binary Search Tree - метод рекурсивного недействительного копирования

Question

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

Я действительно не знаю, как начать с чего-то подобного, все, что у меня есть, довольно пустая оболочка метода и его оболочка. Я не уверен, являются ли параметры в частном методе правильными, но это было мое лучшее предположение как начало.

public void copy(BinarySearchTree<E> bst2){ 
     copy(bst2, root, bst2.root); 
    } 

private void copy(BinarySearchTree<E> bst2, Node node1, Node node2){ 
    } 

Буду признателен за любую помощь.

Спасибо!

Answer 1

Немедленное мысль (грубый псевдокод вперед):

class Tree { 
    //stuff in the tree with a root node, etc... 

    copyTree(Node parentTreeNode, Node copyTreeNode) { 
      if(copyTreeNode == null) 
       return; 
      parentTreeNode = clone(copyTreeNode) //clone just copies the node's values into the node. 
      if(copyTreeNode.leftChild != null) { 
       parentTreeNode.leftChild = new Node(); 
       copyTree(parentTreeNode.leftChild, copyTreeNode.leftChild); 
      } 
      if(copyTreeNode.rightChild != null) { 
       parentTreeNode.rightChild = new Node(); 
       copyTree(parentTreeNode.rightChild, copyTreeNode.rightChild); 
      } 
    } 
} 

И вы бы просто назвать это с двух корневых узлов и пусть рекурсию и строит дерево для вас.

Итак, если базовый случай активирован (текущий узел равен нулю), вы пропустите этот узел, вернувшись и перейдя в процессе рекурсии (базовый регистр важен в рекурсивных методах, иначе вы получите бесконечную рекурсию). Итак, мы начинаем с корневого узла, копируем его (если это не пусто), а затем переходим к левому поддереву, считая его также не равным нулю. Мы останавливаемся в этом методе, вызываем метод в поддереве, который «останавливается» там и вызывает слева. Когда он возвращается назад, все места, которые он «приостановил», возобновляет, переходя к правильному ребенку на каждом из этих узлов с той же процедурой. Как только левое поддерево повторяется само по себе, мы возобновляем в верхнем узле и переходим в правое поддерево, чтобы делать то же самое (как и во всех дочерних узлах, рекурсивно). Когда все будет сделано, оно просто возвращается нормально.

Рекурсия не особенно сложна, но сначала нужно понять, что нужно понимать.

Это грубая идея и не была проверена, но это примерно то, как я это сделал. Вероятно, стоит отметить, что этот стиль обработки не гарантирует, что деревья одинаковы, если в главном дереве уже есть данные, или вы передали узел, отличный от корневого узла. Но это будет то же самое ниже этого узла.