遍历PreOrder in BinarySearchTree (Java)

Question

我需要些帮助。我已经通过JUnit运行了我的完整代码，但是仍然会出现错误。我想是因为我的代码。

遍历代码的目的是在in LinkedList中创建PreOrder。

例如: JUnit总是说这样的事情是不对的

assertArrayEquals( new Integer[]{2, 14, 26, 86, 122, 134, 182},
    Arrays.copyOf(tree.traversePreOrder(), tree.getSize(), Integer[].class));

@Override
public Object[] traversePreOrder() {
    BinaryTreeNode<T> x = root;
    LinkedList<Object> y = new LinkedList<Object>();

    if (x == null) {
        return null;
    } else {
        y.add(x.value);
        y.add(travPreOrd(x.getLeft()));
        y.add(travPreOrd(x.getRight()));
    }
    return y.toArray();
}

public LinkedList<Object> travPreOrd(BinaryTreeNode<T> x) {
    BinaryTreeNode<T> tmp = x;
    LinkedList<Object> space = new LinkedList<Object>();

    if (x == null) {
        return null;
    } else {
        space.add(tmp.getValue());
        space.add(travPreOrd(x.getLeft()));
        space.add(travPreOrd(x.getRight()));
    }
    return space;
}

Answer 1

您有一个大问题，因为您总是添加travPreOrd的结果，如果节点不存在，这是另一个List<Object>或null。

对于这些情况，最好的解决方案是将重写的方法保持为非递归和重载方法，该方法使用递归，并在接收容器时使用参数，在容器中必须添加数据：

public List<Object> travPreOrd(BinaryTreeNode<T> x) {
    BinaryTreeNode<T> tmp = x;
    List<T> space = new LinkedList<T>();
    travPreOrd(x, space);
    return space;
}

private void travPreOrd(BinaryTreeNode<T> x, List<T> space) {
    if (x == null) {
        return;
    }
    space.add(tmp.getValue());
    travPreOrd(x.getLeft(), space);
    travPreOrd(x.getRight(), space);
}

Answer 2

要将一个列表的内容添加到另一个列表中，可以使用addAll。

因此，与其：

    y.add(x.value);
    y.add(travPreOrd(x.getLeft()));
    y.add(travPreOrd(x.getRight()));

你想要的

    y.add(x.value);
    y.addAll(travPreOrd(x.getLeft()));
    y.addAll(travPreOrd(x.getRight()));

然后您将从travPreOrd返回null，这只会使您的生活更加困难--然后您必须检查并特别处理它。相反，您可以返回一个空列表。

所以而不是

if (x == null) {
    return null;
}

你可以

if (x == null) {
    return Collections.emptyList();
}

编辑:部分问题在于您使用的是一个List<Object>，它允许您添加任何内容，包括其他列表。如果您使用List<Integer>，或者使用泛型并具有List<T>，那么编译器将能够在您做错误的事情时告诉您。