java - 按顺序检索二叉搜索树中的元素

Question

我正在尝试创建一个强调递归的二叉搜索树，目前我一直致力于创建一个函数来按顺序返回二叉搜索树元素的数组列表。

我的主要问题是如何将这个算法实现到返回数组列表的函数中。

下面是类(class)的开始:

public class BinarySearchTree<T> {
    private Comparator<T> comparator;
    private T data;
    private BinarySearchTree<T> left;
    private BinarySearchTree<T> right;

这是我当前拥有的功能:

public List<T> getElements() {
        List<T> list = new ArrayList<>();
        if(data != null) {
            left.getElements();
            list.add(data);
            right.getElements();
        }
        return list;
    }

这是我的插入函数，我相信它是正确的，但如果问题根源在这里，它可能有助于调试:

public void insert(T element) {
        if(data == null) {
            data = element;
        }
        if(element != null && data != null) {
            if(comparator.compare(element, data) == -1) {
                if(left == null) {
                    left = new BinarySearchTree<T>(element, comparator);
                }
                else {
                    left.insert(element);
                }
            }
            if(comparator.compare(element, data) == 1) {
                if(right == null) {
                    right = new BinarySearchTree<T>(element, comparator);
                }
                else {
                    right.insert(element);
                }
            }
            if(comparator.compare(element, data) == 0) {
                return;
            }
        }

Answer 1

您需要将递归调用 getElements 的结果添加到 list (顺便说一下，这是一个非常的坏名字)。

此外，您还需要考虑如何处理 left 和/或 right 为 null 的情况。