Как вернуть итератор для обхода по порядку в двоичном дереве?

Я пытаюсь сохранить свои результаты обхода Inorder в LinkedList и получить их с помощью итератора, но получаю исключение нулевого указателя при печати моих результатов. Я получаю правильный вывод, когда пытаюсь сделать это с помощью рекурсии и печатать значение в своей функции. Когда я рекурсивно пытаюсь вызвать inorderItr(root.left), он принимает root как нуль. Я думаю, что мой оператор возврата неверен. Не уверен, ниже мой код и комментарии, где мой код не работает. Любая помощь и концепции приветствуются. Я видел это, но не помогает, так как я пытаюсь вернуть Iterator. Опять же, я новичок в концепции Java и Iterator. ТИА.

Изменить: я нашел решение, см. Ответ ниже

  class TreeNode {

            int data;
            TreeNode left;
            TreeNode right;

            public TreeNode(int d) {
                data = d;
            }

        }

        public class TreeTraversal {
             TreeNode root;

            public TreeTraversal() {
                root = null;
            }

       static List<TreeNode> l = new LinkedList<TreeNode>();
            public static Iterator<TreeNode> inorderItr(TreeNode root) {

                List<TreeNode> l = new LinkedList<TreeNode>();

      //I think I am missing something here
                if (root == null)
                    return

      //This is where my root is null
                inorderItr(root.left);
                l.add(root);
                inorderItr(root.right);

                Iterator<TreeNode> itr = l.iterator();

                return itr;

            }

    //This code works fine
            public static void inorderWorksFine(TreeNode root) {

                if (root == null)
                    return;

                inorder(root.left);
                System.out.print(root.data + " ");
                inorder(root.right);
            }



            public static void main(String args[]) {

                TreeTraversal t = new TreeTraversal();
                t.root = new TreeNode(10);
                t.root.left = new TreeNode(5);
                t.root.left.left = new TreeNode(1);
                t.root.left.right = new TreeNode(7);
                t.root.right = new TreeNode(40);
                t.root.right.right = new TreeNode(50);

                // inorderWorksFine(t.root);
                Iterator<TreeNode> itr = inorderItr(t.root);

                while (itr.hasNext()) {
                    System.out.println(itr.next().data + " ");
                }

            }

        }

person Yogesh    schedule 21.12.2017    source источник
comment
Возможный дубликат Итератора по порядку для двоичного дерева   -  person vinS    schedule 21.12.2017
comment
@vinS: я пытаюсь вернуть Iterator, я видел это решение. Можете ли вы помочь внести изменения в приведенный выше код и сказать мне, что с этим не так?   -  person Yogesh    schedule 21.12.2017
comment
Я рекомендую вам создать класс, который реализует интерфейс итератора, как было рекомендовано. Вам будет очень трудно создать рекурсивный метод, который возвращает итератор данных, не прибегая к ужасной производительности, перебирая итератор на каждом шаге рекурсии, чтобы создать новый. Кроме того, преобразование в другую структуру (LinkedList) для создания итератора несколько противоречит цели наличия дерева, если у вас большие первоначальные затраты.   -  person Zachary    schedule 21.12.2017
comment
Чтобы было ясно, ваша функция inorderItr не будет работать. По сути, вы конвертируете каждый отдельный узел в списке в уникальный LinkedList и рекурсивно возвращаете его итератор, но ничего не делаете с рекурсивно возвращаемым итератором. Что будет возвращено, так это итератор, принадлежащий LinkedList с одним элементом (корнем). При этом, если не считать итерации по каждому итератору на каждом рекурсивном этапе, вы мало что можете сделать.   -  person Zachary    schedule 21.12.2017
comment
@ZacharyThompson: Спасибо, что указали на это, я создал глобальный LinkedList сейчас, но все же, если я хочу вернуть Iterator, как мне поступить?   -  person Yogesh    schedule 21.12.2017
comment
Потенциальным решением было бы рекурсивное создание LinkedList, а затем использование вспомогательного метода для получения итератора. Опять же, я не вижу смысла создавать отдельную структуру данных для итератора.   -  person Zachary    schedule 21.12.2017
comment
Пожалуйста, укажите причину отрицательного ответа, я новичок в этом, и я не хочу, чтобы меня заблокировали за логические вопросы.   -  person Yogesh    schedule 21.12.2017


Ответы (1)


Я создал вспомогательный метод для неупорядоченного обхода и Global LinkedList и добавил все свои элементы Inorder в этот список в отдельном рекурсивном вспомогательном методе. Таким образом, мы можем вернуть итератор

static List<TreeNode> l = new LinkedList<TreeNode>();

    public static Iterator<TreeNode> inorderItr(TreeNode root) {
    recursionInorder(root);
    Iterator<TreeNode> itr = l.iterator();

     return itr;

    }

    public static void recursionInorder(TreeNode node){
        if(node==null)
              return;

        recursionInorder(node.left);
        l.add(node);
        recursionInorder(node.right);
    }
person Yogesh    schedule 21.12.2017