Gabrielle Evans

I have browsed the other questions and found solutions as to how to do a deep copy of objects that contain references. I am specifically wanting to make a deep copy of a tree. Logically, each tree node contain references to its children nodes. Here is the basics of my node class
public class BSTNode implements Comparable, Serializable { private String token; private int count; private BSTNode leftChild; private BSTNode rightChild;

I know I must only be making a shallow copy because when I make a copy of tree1, called tree2, and edit tree1 the edits also appear on tree2. Here is my copy method within my BSTNode class
public BSTNode copy() { BSTNode obj = null; try{ ByteArrayOutputStream bos = new ByteArrayOutputStream(); ObjectOutputStream out = new ObjectOutputStream(bos); out.writeObject(this); out.flush(); out.close(); ObjectInputStream in= new ObjectInputStream(new ByteArrayInputStream( bos.toByteArray())); obj = (BSTNode) in.readObject(); } catch(Exception e) { e.printStackTrace(); } return obj; }
When I wish to copy the entire tree, I call that above copy method from my BSTree class using the methods below. (I have 2 methods because this is a homework assignment that requires a copy method that calls a preorder traversal method)

public BSTNode copy() { BSTNode copiedTreeRoot = new BSTNode(); return copyTree(copiedTreeRoot,root); } public BSTNode copyTree(BSTNode copiedTreeRoot, BSTNode otherTreeRoot) { if(otherTreeRoot == null) { copiedTreeRoot = null; } else { copiedTreeRoot = otherTreeRoot.copy(); copyTree(copiedTreeRoot.getLeft(), otherTreeRoot.getLeft()); copyTree(copiedTreeRoot.getRight(), otherTreeRoot.getRight()); } return copiedTreeRoot; }
I use these lines to create the new tree and assign the copy to it

BSTree tree2 = new BSTree(); tree2.setRoot(tree1.copy());

And further along when I make changes to tree1, tree 2 also changes. I have no clue what I'm doing wrong. I believe it must be somewhere in how I return the new tree or something. Any help is greatly appreciated!!

First of all, I understand that there are many similar questions to mine posted around the web. I have spent, literally, 2 hours looking through and attempting some of the solutions already given. I am at my wits end. I have a BST that I am told (this is for homework) that I must do a deep copy of into a separate tree. I am told to to this my implementing a preorder traversal method. This is what I have so far

public BSTNode copy() { BSTNode copiedTreeRoot = null; return copyTree(copiedTreeRoot,root); } public BSTNode copyTree(BSTNode copiedTreeRoot, BSTNode otherTreeRoot) { if(otherTreeRoot == null) { copiedTreeRoot = null; } else { copiedTreeRoot = new BSTNode(); copiedTreeRoot.setToken(otherTreeRoot.getToken()); copyTree(copiedTreeRoot.getLeft(), otherTreeRoot.getLeft()); copyTree(copiedTreeRoot.getRight(), otherTreeRoot.getRight()); } return copiedTreeRoot; }

I am doing it in 2 seperate methods because the specifications require a method BSTNode copy() that calls a preorder traversal method.

Here is my BSTNode class for reference

public class BSTNode implements Comparable { private String token; private int count; private BSTNode leftChild; private BSTNode rightChild; public BSTNode(String setToken) { token = setToken; count = 1; leftChild = null; rightChild = null; } public void setToken(String setToken) { token = setToken; } public BSTNode (String setToken, int setCount, BSTNode newLeft, BSTNode newRight) { token = setToken; count = setCount; leftChild = newLeft; rightChild = newRight; } public BSTNode(){count = 1;}; public int compareTo(Object o) { BSTNode anotherNode = (BSTNode) o; if(this.token.compareTo(anotherNode.token) > 0) { return 1; } else if(this.token.compareTo(anotherNode.token) < 0) { return -1; } else { if(this.count > anotherNode.count) { return 1; } else if(this.count < anotherNode.count) { return -1; } else { return 0; } } } public String getToken() { return token; } public void setCount(int newInt) { count = newInt; } public int getCount() { return count; } public void setLeft(BSTNode newLeft) { leftChild = newLeft; } public BSTNode getLeft() { return leftChild; } public void setRight (BSTNode newRight) { rightChild = newRight; } public BSTNode getRight () { return rightChild; } public BSTNode search(String searchValue) { if(searchValue.compareTo(this.token) == 0) { return this; } else if(searchValue.compareTo(this.token) <0) { if(leftChild == null) { return null; } else { return leftChild.search(searchValue); } } else if(searchValue.compareTo(this.token)> 0) { if(rightChild == null) { return null; } else { return rightChild.search(searchValue); } } return null; } public BSTNode remove(BSTNode parent, String value) { if(value.compareTo(token) <0) { if(leftChild != null) { return leftChild.remove(this, value); } else { return null; } } else if(value.compareTo(token)> 0) { if(rightChild != null) { return rightChild.remove(this,value); } else { return null; } } else { if(leftChild != null && rightChild != null) { token = rightChild.findMin(); rightChild.remove(this,token); } else if(parent.getLeft().compareTo(this) == 0) { if(leftChild != null) { parent.setLeft(leftChild); } else { parent.setLeft(rightChild); } } else if(parent.getRight().compareTo(this) == 0) { if(leftChild != null) { parent.setRight(leftChild); } else { parent.setRight(rightChild); } } return null; } } public String findMin() { if(leftChild == null) { return token; } else { return leftChild.findMin(); } } public void swapValues(BSTNode anotherNode) { String temp = token; token = anotherNode.getToken(); anotherNode = new BSTNode(temp,anotherNode.getCount(), anotherNode.getLeft(), anotherNode.getRight()); } }

When I attempt to run the code, I get that only the first element (root) of the tree gets copied. Here is the code I am using to test

public static void main(String[] args) { String[] array1 = {"apple","banana", "tuesday", "pie"}; BSTree tree1 = new BSTree(); for(int i =0; i< array1.length; i++) { tree1.insert(array1[i]); } System.out.print("Original tree: "); testPrint(tree1.getRoot()); System.out.println(""); System.out.print("Copied tree: "); testPrint(tree1.copy()); } public static void testPrint(BSTNode node) { if(node == null) { return; } testPrint(node.getLeft()); System.out.print(node.getToken()+ " "); testPrint(node.getRight()); }

My output is Original tree: APPLE BANANA PIE TUESDAY Copied tree: APPLE

I really am desperate. This is about the 8th time I have completely re-written my copy method(s). Any guidance would be greatly appreciated.

My objective is to execute quick sort ( i was told to convert the pseudocode from the Cormen book) using arrays of increasing sizes and find the average number of comparisons for each of those sizes over 100 iterations. This is a school project and the numbers I am getting are far larger than those of my friends, so I am clearly doing something wrong. I believe it must be in the way that I am collecting and averaging my number of comparisons. I will first give the method in which most of that calculating is done, then I will include the whole program.

public static void tests(int arraySize) { long numComparisons = 0; long averageComparisons = 0; long[] numComparisonsArray = new long[100]; for(int i = 0; i<100; i++) { int[] array= genRandomArray(arraySize); numComparisons=quickSort(array,0,array.length-1); numComparisonsArray[i]=numComparisons; numComparisons = 0; } for(int i =0; i<numComparisonsArray.length;i++) { averageComparisons += numComparisonsArray[i]; } averageComparisons = averageComparisons/100; System.out.println("Average comparisons for "+ arraySize+" "+averageComparisons); totalComparisons[totalComparisonsIndex] = averageComparisons; totalComparisonsIndex++; averageComparisons=0; }

I am incrementing the variable comparisonCount for each comparison done and adding that to an array of all the comparison numbers for that array size. I am then running through that array, averaging it, and placing that average into another array.

import java.util.Random; import java.io.*; public class TestQS { public static Random randomGenerator = new Random(System.currentTimeMillis()); public static int comparisonCount = 0; public static long[] totalComparisons = new long [90]; public static int totalComparisonsIndex = 0; public static void main(String[] args) { for(int i = 1100;i<=10000;i=i+100) { tests(i); } try{ PrintWriter writer = new PrintWriter("results.txt","UTF-8"); int indexNum = 1100; for (int i =0; i<totalComparisons.length;i++) { writer.println(indexNum+", "+totalComparisons[i]); indexNum=indexNum+100; } writer.close(); System.out.println("done"); } catch(IOException ex) { ex.printStackTrace(); } } public static void tests(int arraySize) { long numComparisons = 0; long averageComparisons = 0; long[] numComparisonsArray = new long[100]; for(int i = 0; i<100; i++) { int[] array= genRandomArray(arraySize); numComparisons=quickSort(array,0,array.length-1); numComparisonsArray[i]=numComparisons; numComparisons = 0; } for(int i =0; i<numComparisonsArray.length;i++) { averageComparisons += numComparisonsArray[i]; } averageComparisons = averageComparisons/100; System.out.println("Average comparisons for "+ arraySize+" "+averageComparisons); totalComparisons[totalComparisonsIndex] = averageComparisons; totalComparisonsIndex++; averageComparisons=0; } public static int[] genRandomArray(int arraySize) { int[] array = new int[arraySize]; for(int i = 0;i<array.length;i++) { array[i] = randomGenerator.nextInt(); } return array; } public static int partition(int[] array, int p, int r) { int x = array[r]; int i = p-1; int temp = 0; for(int j =p; j<= r-1;j++) { if( array[j] <= x) { i = i+1; temp = array[i]; array[i]= array[j]; array[j] = temp; comparisonCount++; } else { comparisonCount++; } } temp = array[i+1]; array[i+1]= array[r]; array[r]=temp; return (i+1); } public static int quickSort(int[] array, int p, int r) { int q; if (p < r) { comparisonCount++; q = partition(array,p,r); quickSort(array,p,q-1); quickSort(array,q+1,r); } else { comparisonCount++; } return comparisonCount; } }

Figured it out! I just needed to write the array with write() instead of writeObject()!

In one file, I save a TreeNode object, then an int, and then a byte array to a file named `huffmanTrial.huff`.
In another file I want to read in all three of those things and do work on them. I can read in the TreeNode just fine and the int, but when I get to reading in the byte array I get that it is of size zero. Is that saying that it doesn't exist? I am using `in.available()` after I read in the TreeNode and int so I can see how big I need to make my new byte array and I always get 0. Am I somehow saving the array wrongly or am I reading it in wrongly?

Here is where I save the objects:
FileOutputStream fos = new FileOutputStream(savedFileName); ObjectOutputStream out = new ObjectOutputStream(fos); out.writeObject(root); out.writeInt(numberOfZeroesAdded); out.writeObject(encodedByteArray); out.close();


And here is where I am trying to read all three things in
FileInputStream fis = new FileInputStream("huffmanTrial.huff"); ObjectInputStream in = new ObjectInputStream(fis); root = (HuffmanNode) in.readObject(); System.out.println("root "+ root.getCount()); numberOfZeroesAdded = in.readInt(); System.out.println("zeroes: "+numberOfZeroesAdded); sizeOfArray = in.available(); System.out.println("Size of array: "+sizeOfArray); encodedByteArray = new byte[sizeOfArray]; in.readFully(encodedByteArray);

I get `Size of array: 0`
I know for sure that the array that I am saving is not empty because just two lines before I save it, I print its contents. What am I doing wrong?