<![CDATA[
CSE143 Key to Final handout #35
1. Binary Tree Traversals, 6 points.
Preorder traversal 2, 0, 5, 1, 7, 6, 3, 4, 9, 8
Inorder traversal 1, 5, 0, 7, 6, 2, 3, 9, 4, 8
Postorder traversal 1, 5, 6, 7, 0, 9, 8, 4, 3, 2
2. Binary Search Tree, 4 points.
+------------+
| Pride |
+------------+
/ \
/ \
/ \
+------------+ +------------+
| Envy | | Sloth |
+------------+ +------------+
/ \
/ \
/ \
+------------+ +------------+
| Anger | | Greed |
+------------+ +------------+
/ \
/ \
/ \
+------------+ +------------+
| Gluttony | | Lust |
+------------+ +------------+
3. Binary Trees, 10 points. One possible solution appears below.
public void printLevel(int target) {
if (target < 1)
throw new IllegalArgumentException();
printLevel(overallRoot, target, 1);
}
private void printLevel(TreeNode root, int target, int level) {
if (root != null)
if (level == target)
System.out.println(root.data);
else {
printLevel(root.left, target, level + 1);
printLevel(root.right, target, level + 1);
}
}
4. Programming with inheritance, 20 points. Two possible solutions appear
below.
public class TallyPhoneList extends PhoneList {
private int[] fromCount;
private int[] toCount;
private int totalFrom;
private int totalTo;
public TallyPhoneList(ArchiveData archive) {
super(archive);
fromCount = new int[1000];
toCount = new int[1000];
}
public void add(PhoneCall call) {
super.add(call);
int from = call.fromAreaCode();
fromCount[from]++;
if (fromCount[from] == 1)
totalFrom++;
int to = call.toAreaCode();
toCount[to]++;
if (toCount[to] == 1)
totalTo++;
}
public int getFromCount(int area) {
return fromCount[area];
}
public int getToCount(int area) {
return toCount[area];
}
public int getTotalFrom() {
return totalFrom;
}
public int getTotalTo() {
return totalTo;
}
}
public class TallyPhoneList extends PhoneList {
private Map<Integer, Integer> fromCount;
private Map<Integer, Integer> toCount;
public TallyPhoneList(ArchiveData archive) {
super(archive);
fromCount = new HashMap<Integer, Integer>();
toCount = new HashMap<Integer, Integer>();
}
public void add(PhoneCall call) {
super.add(call);
int from = call.fromAreaCode();
if (!fromCount.containsKey(from))
fromCount.put(from, 1);
else
fromCount.put(from, fromCount.get(from) + 1);
int to = call.toAreaCode();
if (!toCount.containsKey(to))
toCount.put(to, 1);
else
toCount.put(to, toCount.get(to) + 1);
}
public int getFromCount(int area) {
if (fromCount.containsKey(area))
return fromCount.get(area);
else
return 0;
}
public int getToCount(int area) {
if (toCount.containsKey(area))
return toCount.get(area);
else
return 0;
}
public int getTotalFrom() {
return fromCount.size();
}
public int getTotalTo() {
return toCount.size();
}
}
5. Comparable class, 20 points. One possible solution appears below.
public class RadioStation implements Comparable<RadioStation> {
private String name;
private String band;
private double station;
private RadioStation link;
public RadioStation(String name, String band, double station) {
this.name = name;
this.band = band;
this.station = station;
}
public int compareTo(RadioStation other) {
if (!band.equals(other.band))
return band.compareTo(other.band);
double difference = station - other.station;
if (difference < 0)
return -1;
else if (difference == 0)
return 0;
else // difference > 0
return 1;
}
public String getName() {
return name;
}
public String getBand() {
return band;
}
public double getStation() {
return station;
}
public void simulcast(RadioStation other) {
link = other;
other.link = this;
}
public String toString() {
String result = name + " " + band + " " + station;
if (link != null)
result += " (simulcast on " + link.band + " " +
link.station + ")";
return result;
}
}
6. Binary Trees, 20 points. One possible solution appears below.
public void completeToLevel(int target) {
if (target < 1)
throw new IllegalArgumentException();
overallRoot = complete(overallRoot, target, 1);
}
private TreeNode complete(TreeNode root, int target, int level) {
if (level <= target) {
if (root == null)
root = new TreeNode(-1);
root.left = complete(root.left, target, level + 1);
root.right = complete(root.right, target, level + 1);
}
return root;
}
7. Linked Lists. One possible solution appears below.
public void doubleList() {
if (front != null) {
ListNode half2 = new ListNode(front.data);
ListNode back = half2;
ListNode current = front;
while (current.next != null) {
current = current.next;
back.next = new ListNode(current.data);
back = back.next;
}
current.next = half2;
}
}
]]>