在学校作业中,我应该完成一个方法,该方法应该返回一个数组
节点元素按升序排列。这些节点被组装在一个二叉搜索树中,因此为了对它们进行正确排序,我获得了创建递归方法来完成工作的提示。
问题在于,这甚至无法根据测试输出生成集合中的所有元素(java.lang.AssertionError:toArray()不会返回集合中的所有元素。)
我无法提出任何其他方法来处理数组,而且我不确定递归是否有效。任何帮助深表感谢。
下面是我的代码:
public class BinarySearchTree<E extends Comparable<E>> implements
IfiCollection<E> {
Node root;
Node current;
int size = 0;
int i = 0;
public class Node {
E obj;
Node left, right;
public Node(E e) {
obj = e;
}
} // END class Node
[...]
public E[] toArray(E[] a) {
Node n = root;
a = sort(n, a);
return a;
}
public E[] sort(Node n, E[] a) { //, int idx, E[] a) {
if (n.left != null) {
current = n.left;
sort(current, a);
}
a[i] = current.obj;
i++;
if (n.right != null) {
current = n.right;
sort(current, a);
}
return a;
} // END public Node sort
[...]
} // END class BinarySearchTree
测试输出:
java.lang.AssertionError:toArray()不会返回集合中的所有元素。:TestPerson(“ Bender”)。compareTo(TestPerson(“ Fry”))== 0预期:真,但是:假
在inf1010.assignment.IfiCollectionTest.assertCompareToEquals(IfiCollectionTest.java:74)
在inf1010.assignment.IfiCollectionTest.assertCompareToEquals(IfiCollectionTest.java:83)
在inf1010.assignment.IfiCollectionTest.assertCompareToEqualsNoOrder(IfiCollectionTest.java:100)
在inf1010.assignment.IfiCollectionTest.toArray(IfiCollectionTest.java:202)
protected void assertCompareToEquals(TestPerson actual,
TestPerson expected, String msg) {
assertTrue(actual.compareTo(expected) == 0, String.format( // l:74
"%s: %s.compareTo(%s) == 0", msg, actual, expected));
}
[...]
protected void assertCompareToEquals(TestPerson[] actual,
TestPerson[] expected, String msg) {
for (int i = 0; i < actual.length; i++) {
TestPerson a = actual[i];
TestPerson e = expected[i];
assertCompareToEquals(a, e, msg); // l:83
}
}
[...]
protected void assertCompareToEqualsNoOrder(TestPerson[] actual,
TestPerson[] expected, String msg) {
assertEquals(actual.length, expected.length, msg);
TestPerson[] actualElements = new TestPerson[actual.length];
System.arraycopy(actual, 0, actualElements, 0, actual.length);
TestPerson[] expectedElements = new TestPerson[expected.length];
System.arraycopy(expected, 0, expectedElements, 0, expected.length);
Arrays.sort(expectedElements);
Arrays.sort(actualElements);
assertCompareToEquals(actualElements, expectedElements, msg); // l:100
}
[...]
@Test(dependsOnGroups = { "collection-core" },
description="Tests if method toArray yields all the elements inserted in the collection in sorted order with smallest item first.")
public void toArray() {
TestPerson[] actualElements = c.toArray(new TestPerson[c.size()]);
for (int i = 0; i < actualElements.length; i++) {
assertNotNull(actualElements[i],
"toArray() - array element at index " + i + " is null");
}
TestPerson[] expectedElements = allElementsAsArray();
assertCompareToEqualsNoOrder(actualElements, expectedElements, // l:202
"toArray() does not return all the elements in the collection.");
Arrays.sort(expectedElements);
assertCompareToEquals(actualElements, expectedElements,
"toArray() does not return the elements in sorted order with "
+ "the smallest elements first.");
TestPerson[] inArr = new TestPerson[NAMES.length + 1];
inArr[NAMES.length] = new TestPerson("TEMP");
actualElements = c.toArray(inArr);
assertNull(actualElements[NAMES.length],
"The the element in the array immediately following the "
+ "end of the list is not set to null");
}
我不知道是否应该发布更多的测试代码,因为它相当广泛,对于一篇文章来说可能太多了吗?
最佳答案
好的,我认为问题是您使用了“全局”变量current
。设置方式没有多大意义。无论如何,您都不需要,因为“ current” Node
是参数中提供的。
另外,您应该考虑重命名功能。您无需在此处进行任何排序,仅收集树的内容,因此更适合使用collect
之类的名称。
public E[] toArray(E[] a) {
Node n = root;
a = collect(n, a);
return a;
}
public E[] collect(Node n, E[] a) {
if (n.left != null) {
// If there is a left (smaller) value, we go there first
collect(n.left, a);
}
// Once we've got all left (smaller) values we can
// collect the value of out current Node.
a[i] = n.obj;
i++;
if (n.right != null) {
// And if there is a right (larger) value we get it next
collect(n.right, a);
}
return a;
}
(免责声明:我尚未对此进行测试)
没有全局索引的替代实现:
public E[] toArray(E[] a) {
Node n = root;
collect(n, a, 0);
return a;
}
public int collect(Node n, E[] a, int i) {
if (n.left != null) {
// If there is a left (smaller) value, we go there first
i = collect(n.left, a, i);
}
// Once we've got all left (smaller) values we can
// collect the value of out current Node.
a[i] = n.obj;
i++;
if (n.right != null) {
// And if there is a right (larger) value we get it next
i = collect(n.right, a, i);
}
return i;
}