Проблема клонирования двоичного дерева Java

Question

У меня есть двоичное дерево Java с приведенной ниже спецификацией, и мне нужно его клонировать.

public class Item {

    private final String value;
    public final Item left;
    public final Item right;

    ...

}

То, что кажется очень простой задачей, сбивает меня с толку в том, что клонированное дерево должно иметь те же ячейкис исходным древовидным объектом, а не копируемым.

Однако, если элемент должен быть добавлен к исходному или клонированному дереву, он не должен распространяться на другое дерево.то есть.Если новый элемент должен быть добавлен к исходному дереву, он не должен появляться в клонированном дереве и наоборот.

Также это должно быть сделано без рекурсии и без какой-либо циклической конструкции.

Так что мне было интересно, может ли кто-нибудь придумать, как это сделать, потому что я понятия не имею, с чего начать?

Answer 1

это можно сделать, если вы настроите копирование при записи в структуре:

/*in Item */
Item add(String value){
   Item item = new Item(this.value);
   if(value.compareTo(this.value)<0){
      item.left = this.left;
      item.right = this.right.add(value);
   }else{
      item.left = this.left.add(value);
      item.right = this.right;
   }
   return item;
}

, тогда клонирование копирует только корень в другое дерево

Answer 2

Node cloneTree(Node root) {
        Node n1 = new Node();
        n1.value = root.value;
        cloneTree(root, n1);
        return n1;
}

void cloneTree(Node root, Node newNode) {
        if (root == null) {
            return;
        }
        if (root.leftNode != null) {
            newNode.leftNode = new Node();
            newNode.leftNode.value = root.leftNode.value;
            cloneTree(root.leftNode, newNode.leftNode);
        }
        if (root.rightNode != null) {
            newNode.rightNode = new Node();
            newNode.rightNode.value = root.rightNode.value;
            cloneTree(root.rightNode, newNode.rightNode);
        }

}

Answer 3

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

открытый класс CloneTree {

public static void main(String[] args)
{

    tNode root=createTree();
    if(root==null)
    {
        return;
    }
    tNode newR=new tNode();
    cloneMyTree(root,newR);
    printTree(newR);



}




private static tNode cloneMyTree(tNode root, tNode newR) {
    if(root==null)
    {
        return null;
    }
    tNode leftSubNode=null;
    tNode rightSubNode=null;

    if(!(root.left==null))
        {
         leftSubNode = new tNode();
          cloneMyTree(root.left, leftSubNode);
        }

    if(!(root.right==null))
    {
     rightSubNode = new tNode();
      cloneMyTree(root.right, rightSubNode);
    }

    newR.left=leftSubNode;
    newR.right=rightSubNode;
    newR.value=root.value;


    return root;




}

public static void printTree(tNode root)
{
    if(root==null)
    {
        System.out.println("NULL");
        return;
    }
    else{
    System.out.println(root.value);
    System.out.println("Left of "+root.value);
    printTree(root.left);

    System.out.println("right of "+root.value);
    printTree(root.right);
    }

}



public static tNode  createTree()
{
bTree myTree=new bTree();
myTree.root = new tNode(1);

myTree.root.left=new tNode(2);
myTree.root.left.left=new tNode(4);
myTree.root.left.right= new tNode(5);

myTree.root.right= new tNode(3);
myTree.root.right.left=new tNode(6);
myTree.root.right.right=new tNode(7);
return myTree.root;

}  

}

Answer 4

Простой и понятный ответ - создать объект Cell и иметь ссылку на него на узле дерева, а не на данные ячейки внутри узла.

Answer 5

final для левого и правого поддерева не имеет особого смысла.Делая их окончательными, дерево по сути является неизменным, и как таковая операция вставки не имеет смысла.В любом случае, этот код, как мы надеемся, должен согреть процесс мышления.

public class Node {
  final String value;
  Node left;
  Node right;

  boolean copyOnWrite; //google it for more information

  public Node(String value,Node left,Node right,boolean copyOnWrite) {
    //blabla
  }

  public Node copy() { //not recursive!
    copyOnWrite = true;
    return new Node(value,left,right,true);
  }

  public Node deepCopy() { //recursive!
    return new Node(value,left.deepCopy(),right.deepCopy(),false);
  }

  public void insert(String value) {
    if (copyOnWrite) {
      copyOnWrite = false;
      left = left.deepCopy();
      right = right.deepCopy();
    }
    //normal tree insert code
  }

Итак, вызов copy() быстр, что делает мелкую копию.deepCopy() выполняется только при попытке его изменить.На самом деле, нет необходимости делать глубокую копию дерева whole , но так как это домашняя работа, я оставляю это (сколько нужно копий? Какие узлы становятся «грязными»?) В качестве упражнения:)

Answer 6

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

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

Код будет выглядеть примерно так

public Item cloneItem() {

    Item cloneLeft = left.cloneItem();
    Item cloneRight = right.cloneItem();
    return new Item(value, cloneLeft, cloneRight);
}

Вы должны проверить, установлены ли левые и / или правые значения, которые я пропустил в примере.