CSci 2101 Data Structures: Lab 9

Problem 1

This problem will be done in groups of two Below is the (somewhat corrected) code for delete method that was written yesterday in class: 

    public void delete(int x) {
	IntNode n1 = search(x);
	if (n1 == null) {
	    System.out.println(x + " is not in the tree");
	}
	//n1 has two children:
	else if (n1.getLeft() != null && n1.getRight() != null) {
	    IntNode n2 = n1.getLeft();
	    IntNode n3 = n1;
	    while (n2.getRight() != null) {
		n3 = n2;
		n2 = n2.getRight();
	    }
	    n1.setData(n2.getData());
	    if (n3.getRight() == n2) {
		n3.setRight(n2.getLeft());
	    } else {
		n3.setLeft(n2.getLeft());
	    }
	}
	// n1 is the root:
	else if (n1 == root) {
	    if (n1.getRight() != null) {
		root = n1.getRight();
	    } else {
		root = n1.getLeft();
	    }
	} else {
	    // need to find n1's parent
	    IntNode parent = root;
	    while (parent.getLeft() != n1 && parent.getRight() != n1) {
		if (x > parent.getData()) {
		    parent = parent.getLeft();
		} else {
		    parent = parent.getRight();
		}
	    }
	    if (n1.getLeft() != null) {
		if (parent.getLeft() == n1) {
		    parent.setLeft(n1.getLeft());
		} else {
		    parent.setRight(n1.getLeft());
		}
	    } else {
		if (parent.getLeft() == n1) {
		    parent.setLeft(n1.getRight());
		} else {
		    parent.setRight(n1.getRight());
		}
	    }
	}
    }
Part 1. Comment the code so that it's clear what happens in each segment.
Part 2. Think of good test cases for this method. Make sure to test it thoroughly. Write ALL of your test cases and their results in comments at the end of the program. If you tested this code carefully, you will find at least one case when it doesn't work. Part 3. Correct the problem you have discovered in part 2 and test the program again. Submit the final file.

Problem 3

Draw two memory pictures for the following program: the first one right before the method m1 finishes, the other one right before m2 finishes. The pictures should show a and b in the method and arr1 and arr2 in main.

What will be printed by this program? Write it on your memory picture. Run the program to check your answer, modify your picture if needed. 


public class Lab9Prob2 {
    public static void main(String [] args) {
	int [] arr1 = {1, 2, 3};
	int [] arr2 = {6, 7, 8};
	m1(arr1, arr2);
	System.out.println("after m1:");
	print(arr1);
	print(arr2);
	m2(arr1, arr2);
	System.out.println("after m2:");
	print(arr1);
	print(arr2);
    }

    public static void m1(int [] a, int [] b) {
	for (int i = 0; i < a.length; ++i) {
	    int temp = a[i];
	    a[i] = b[i];
	    b[i] = temp;
	}
	System.out.println("in m1:");
	print(a);
	print(b);
	// Memory picture 1
    }

    public static void m2(int [] a, int [] b) {
	int [] temp = a;
	a = b;
	b = temp;
	System.out.println("in m2:");
	print(a);
	print(b);
	// Memory picture 2
    }

    public static void print(int [] items) {
	// print array elements all on one line
	for (int i = 0; i < items.length; ++i) {
	    System.out.print(items[i] + " ");
	}
	System.out.println();
    }

}

Problem 3: writing array methods

Write a static method that takes an array of integers and replaces each element by its square.

Problem 4: writing array methods

Write a static method that takes two arrays of strings as parameters. The method has a loop that goes through the arrays until the end of the shorter one. If the string in the first array is alphabetically before the string at the same index in the second array, then the two strings get switched, otherwise they don't. Print out the two arrays in main after the call to the method.
This is a lab from CSci 2101 course.