TreeSet метод first() java

97
03 февраля 2021, 07:20

Подскажите как можно реализовать метод который должен возвращать самый малый элемент

public class TreeLinkedSet<T extends Comparable<T>> implements Iterable<T> {
    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            private Container cursor;
            {
                if (root != null) {
                    cursor = passLeft(root);
                }
            }
            @Override
            public boolean hasNext() {
                return cursor != null;
            }
            @Override
            public T next() {
                T res = cursor.val;
                if (cursor.right != null) {
                    cursor = passLeft(cursor.right);
                } else if (cursor.right == null) {
                    cursor = passBack(cursor);
                }
                return res;
            }
        };
    }
    private class Container implements Comparable<Container> {
        private Container left;
        private Container right;
        private Container prior;
        private T val;
        public Container(T val) {
            this.val = val;
        }
        @Override
        public int compareTo(Container o) {
            return val.compareTo(o.val);
        }
    }
    private Container root;
    private int size;
    public int Size() {
        return size;
    }
    public void add(T t) {
        Container c = new Container(t);
        if (root == null) {
            root = c;
            size++;
        } else {
            choose(root, c);
        }
    }
    private void choose(Container base, Container c) {
        if (c.compareTo(base) < 0) {
            if (base.left == null) {
                base.left = c;
                c.prior = base;
                size++;
            } else {
                choose(base.left, c);
            }
        }
        if (c.compareTo(base) > 0) {
            if (base.right == null) {
                base.right = c;
                c.prior = base;
                size++;
            } else {
                choose(base.right, c);
            }
        }
    }
    private Container passLeft(Container c) {
        return c.left == null ? c : passLeft(c.left);
    }
    private Container passBack(Container c) {
        if (c.prior != null) {
            return c.prior.compareTo(c) > 0 ? c.prior : passBack(c.prior);
        }
        return null;
    }
    public T[] toArray(T[] type) {
        T[] res = (T[]) Array.newInstance(type.getClass().getComponentType(), size);
        int i = 0;
        for (T t : this) {
            res[i++] = t;
        }
        return res;
    }
Answer 1

Самый малый элемент в таком дереве — самый левый, т.ч. метод будет выглядеть примерно так:

public T first() {
    if(root==null) {
        //нужно понять что делать если коллекция пуста
        return null;
    }
    //в противном случае идем от корня налево до конца
    Container leftMost = root;
    while(leftMost.left!=null) {
         leftMost = leftMost.left;
    }
    return leftMost.val;
}

Обновление: Кстати, у Вас уже есть итератор, который умеет определять первый элемент. И даже есть метод для этого — passLeft, можно использовать его:

public T first() {
    if(root==null) {
        //нужно понять что делать если коллекция пуста
        return null;
    }
    //в противном случае идем от корня налево до конца
    return passLeft(root).val;
}

и, если для пустой коллекции метод действительно должен вернуть null, то можно сократить код:

public T first() {
    return root==null ? null : passLeft(root).val;
}
READ ALSO
Как по странице в браузере найти определенную форму в коде?

Как по странице в браузере найти определенную форму в коде?

Есть очень большой веб проект, как мне найти, например, эту форму в коде? Пользуюсь intellij ideaНа форму нужно добавить одно поле, но искать ее вручную...

94
Обработка одновременного нажатия нескольких кнопок в javafx

Обработка одновременного нажатия нескольких кнопок в javafx

У меня есть панель, на которой рисуются графики функцийС помощью этого метода на неё повешен слушатель

129
Java Json десериализация только нужных данных

Java Json десериализация только нужных данных

Java Json десериализация только нужных данных Как содержимое которое находится в «Campaigns» положить как объект в массив? Желательно при помощи...

116
Юникс время в js

Юникс время в js

Хочу написать простую программу для вывода погоды и тд, но возникли трудности с выводом времени(а именно с разницей времени в часовых поясах)

120