通用 BinarySearchTree 中的 PostOrder 输出 (Java)

Question

我在做一些编码作业时遇到了一些麻烦。我应该编写一个通用二进制搜索树实用程序，包括用于返回树的后顺序遍历的 ArrayList 的方法。我的代码可以编译，但它会为除空树以外的所有树抛出 NullPointerException。我的错误在哪里？

public ArrayList<T> postOrder(BinarySearchTree<T> tree) {
    if (tree == null) {
        return null;
    } else {
        ArrayList<T> post = new ArrayList<T>();
        post.addAll(postOrder(tree.left));
        post.addAll(postOrder(tree.right));
        post.add(tree.thing);
        return post;
    }
}

class BinarySearchTree 是：

public class BinarySearchTree<T> {
/**
 * The key by which the thing is refered to. Must be unique.
 */
public int key;

/**
 * The thing itself.
 */
public T thing;

/**
 * The left sub-tree
 */
public BinarySearchTree<T> left;

/**
 * The right sub-tree
 */
public BinarySearchTree<T> right;
Biny
/**
 * Create a new binary search tree without children.
 * @param key the key by which the thing is refered to
 * @param thing the new thing
 */
public BinarySearchTree(int key, T thing)
{
    this.key = key;
    this.thing = thing;
    this.left = null;
    this.right = null;
}

/**
 * Create a new binary search tree
 * @param key the key by which the thing is refered to
 * @param thing the thing which is managed by the new binary search tree
 * @param left the left sub-tree of the new binary search tree
 * @param right the right sub-tree of the new binary search tree
 */
public BinarySearchTree(int key, T thing, BinarySearchTree<T> left, BinarySearchTree<T> right)
{
    this.key = key;
    this.thing = thing;
    this.left = left;
    this.right = right;
}

感谢您的帮助

编辑：我正在用字符串测试我的代码，但由于使用了通用类型，希望这不重要。

Answer 1

试试这个：

public ArrayList<T> postOrder(BinarySearchTree<T> tree) {
    if (tree == null) {
        return null;
    } else {
        ArrayList<T> post = new ArrayList<T>();
        ArrayList<T> l = postOrder(tree.left);
        if (l != null) post.addAll(l);
        ArrayList<T> r = postOrder(tree.right);
        if (r != null) post.addAll(r);
        post.add(tree.thing);
        return post;
    }
}

通用 BinarySearchTree 中的 PostOrder 输出 (Java)

PostOrder output in a generic BinarySearchTree (Java)

java

generics

binary-search-tree

postorder