Java Binary Tree Cloning Problem

I have a Java Binary Tree with the below specification and I need to clone it.

public class Item {

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

    ...

}

What seems to be a very simpl开发者_开发知识库e task has me baffled in that the cloned tree must share the same cells with the original tree object rather than being copied.

However if an item were to be added to either the original or cloned tree, it must not propagate to the other tree. ie. If a new item were to be added to the original tree, it must not appear in the cloned tree and vice vera.

Also this needs to be done without recursion and without any looping construct.

So I was wondering if anyone can think of anyway to do this because I have no idea where to start?

---

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

}

---

this can be done if you set up copy on write in the structure:

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

then the cloning is only copying the root to the other tree

---

You could write a clone method for a specific node. This method creates a new node with the value of the current node. Result of the method would be the cloned node.

In the method you could call the clone method for the right and left node recursively. The result of the calls will be set as right and left node of the cloned node. This should do the trick.

The code would look something like this

public Item cloneItem() {

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

You have to check if left and/or right are set which I have left out in the example.

---

The final for the left and right sub tree's don't make much sense. Making them final, the tree is essentially immutable, and as such an insert operation does not make sense. Anyway, this code should hopefully warm up the thinking process.

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
  }

So, calling copy() is fast it makes a shallow copy. A deepCopy() is only performed when an attempt is made to modify it. Actually, there is no need to make a deep copy of the entire tree , but since this is homework, I leave that(how many copies are needed? What nodes become 'dirty'?) as an exercise :)

---

The simple straightforward answer is to make a Cell object and have the tree node reference it rather than the data of the cell within the node.

---

This is a solution with recursion. might still need to consider some edge cases but the logic is right.

public class 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;

}  

}