Преобразование бинарного дерева в двусвязный список

Question

Я пытаюсь написать функцию в Java для преобразования двоичного дерева в DLL. Функция выполняется без ошибок, но DLL не создается. Ниже приводится функция. root - указатель на корень дерева, а head - на начальный узел DLL.

public void dll(Node x)
    {

        if(x==null)
        {
            return;
        }
        else
        {
            if(x==root)
            {
                Node temp=root;
                while(temp.left!=null)
                {
                    temp=temp.left;
                }
                head=temp;
            }

            if(x.left!=null)
            {
                System.out.println(x.data);

                Node lchild=x.left;
                Node rightmost=lchild;
                while(rightmost.right!=null)
                {
                    rightmost=rightmost.right;
                }
                x.left=rightmost;
                rightmost.right=x;
                dll(lchild);

            }
            if(x.right!=null)
            {
                System.out.println(x.data);

                Node rchild=x.right;
                Node leftmost=rchild;

                while(leftmost.left!=null)
                {
                    leftmost=leftmost.left;
                }

                x.right=leftmost;
                leftmost.left=x;
                dll(rchild);
            }




        }

    }
}

Логика такова: найдите самый правый в левом поддереве и сделайте предыдущий узел корня, найдите самый левый в правом поддереве и сделайте его следующим за корнем. Рекурсивно применять для поддеревьев.

Когда я пытаюсь напечатать head.right, это дает мне исключение нулевого указателя.

Exception in thread "main" java.lang.NullPointerException
        at BTtoDll.main(BTtoDll.java:153)

Строка 153 -

 System.out.println(t.head.right.data);

Answer 1

Чистая рекурсивная функция фактически делает то же самое: крайняя правая часть левого поддерева, соединенная с x и x, соединяется с самой левой частью правого поддерева. Я подумал, что вам может быть интересно увидеть соответствие.

public DLL dll(Node x) {
    return dll(null, x, null);
}

public DLL dll(DLL before, Node x, DDL after) {
    if (x == null) {
        return;
    }
    if (x.left != null) {
        before = dll(before, x.left, null);
    }
    if (x.right != null) {
        after = dll(null, x.left, after);
    }
    DLL result = new DLL();
    result.insert(x.value);
    result.insertBefore(before); // null being a no-op.
    result.insertAfter(after); // null being a no-op.
    return result;
}

Как можно видеть, есть несколько возможных вариантов.

Answer 2

Здесь вы назначаете x.left а также x.right в x:

if(x.left!=null)
{
    ...
    rightmost=x;
    x.left=rightmost;
    ...
}
if(x.right!=null)
{
    ...
    leftmost=x;
    x.right=leftmost;
    ...
}

Я не могу сказать, что это значит, чтобы сказать, на что это можно изменить, но это, вероятно, ваша ошибка. Список не будет перепривязан.

Answer 3

Что касается вашего NullPointerException, Я думаю что

          while(leftmost!=null)

должно быть

          while(leftmost.left!=null)