Блог

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

 public class Item {

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

    ...

}
  

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

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

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

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

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

}
  

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

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

тогда клонирование заключается только в копировании корня в другое дерево

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

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

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

 public Item cloneItem() {

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

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

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() Выполняется только при попытке его изменения. На самом деле, нет необходимости делать глубокую копию всего дерева, но поскольку это домашнее задание, я оставляю это (сколько копий необходимо? Какие узлы становятся «грязными»?) в качестве упражнения 🙂

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

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

открытый класс 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;

}  
  

}