Поиск по порядку элементов в бинарном дереве поиска

Question

Я пытаюсь создать двоичное дерево поиска с акцентом на рекурсию, и в настоящее время я застрял при создании функции, возвращающей массив элементов двоичного дерева поиска по порядку.

Моя главная проблемаБолее того, как реализовать этот алгоритм в функции, которая возвращает массив.

Вот начало класса:

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 равны нулю.