1

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

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;
    }

1 ответ 1

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;
}
6
  • Огромное спасибо !!!!! 10 июн 2019 в 12:06
  • @EvgeniyRadion Пожалуйста! На будущее: старайтесь расписывать подробнее что делает код. Если сами пытались написать метод, то прикладывайте неудачную попытку. Так будет легче Вам помочь. 10 июн 2019 в 12:08
  • 1
    ок, понял, и еще раз спасибо 10 июн 2019 в 12:15
  • @EvgeniyRadion заметил, что у Вас в коде уже есть подходящий метод для поиска наиболее левого элемента. Обновил ответ. 10 июн 2019 в 12:20
  • а подскажи плз насчет метода удаления мне нужно очистить коллекцию я сделал так : ' public void clear() { if (root != null) { root =null; }' 10 июн 2019 в 13:06

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.