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

Question

I have a ordered binary tree:
              4
              |
          |-------|
          2       5
          |
      |-------|
      1       3

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

1<->2<->3<->4<->5

(Очевидно, 5 должно указывать на 1)

Класс узла выглядит следующим образом:

class Node {
    Node left;
    Node right;
    int value;

    public Node(int value)
    {
        this.value = value;
        left = null;
        right = null;
    }
}

Как видите, список двойных ссылок также упорядочен (отсортирован).

Вопрос: Мне нужно создать связанный список из дерева без использования дополнительных указателей.Указатель left дерева должен быть указателем previous списка, а указатель right дерева должен быть указателем next списка.

То, что я думалoff: Поскольку дерево является упорядоченным деревом, обход по порядку выдаст мне отсортированный список.Но пока я делаю обход по порядку, я не могу увидеть, где и как перемещать указатели для формирования двусвязного списка.

PS Я проверил некоторые варианты этого вопроса, но ни один изони дали мне какие-либо подсказки.

Answer 1

Похоже, вам нужен метод, который принимает ссылку Node на корень дерева и возвращает ссылку Node на заголовок кругового списка, где не создаются новые объекты Node.Я хотел бы подойти к этому рекурсивно, начиная с простого дерева:

   2
   |
|-----|
1     3

Вы не говорите, гарантированно ли дерево заполнено, поэтому нам нужно учесть 1 и / или 3быть null.Следующий метод должен работать для этого простого дерева:

Node simpleTreeToList(Node root) {
    if (root == null) {
        return null;
    }
    Node left = root.left;
    Node right = root.right;
    Node head;
    if (left == null) {
        head = root;
    } else {
        head = left;
        left.right = root;
        // root.left is already correct
    }
    if (right == null) {
        head.left = root;
        root.right = head;
    } else {
        head.left = right;
        right.right = head;
        right.left = root;
    }
    return head;
}

Как только станет ясно, как это работает, не так уж сложно обобщить его на рекурсивный метод, который работает для любого дерева.Это очень похожий метод:

Node treeToList(Node root) {
    if (root == null) {
        return null;
    }
    Node leftTree = treeToList(root.left);
    Node rightTree = treeToList(root.right);
    Node head;
    if (leftTree == null) {
        head = root;
    } else {
        head = leftTree;
        leftTree.left.right = root;
        root.left = leftTree.left;
    }
    if (rightTree == null) {
        head.left = root;
        root.right = head;
    } else {
        head.left = rightTree.left;
        rightTree.left.right = head;
        rightTree.left = root;
        root.right = rightTree;
    }
    return head;
}

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

Answer 2

Выполните обход списка по порядку, добавляя каждый элемент списка в дважды связанный список по мере его появления.Когда закончите, добавьте явную ссылку между первым и последним элементами.

Обновление 06.03.2012: Поскольку вы должны повторно использовать уже имеющиеся у вас объекты Node, после того как вы поместите объекты узлав список, вы можете затем перебрать список и сбросить левый и правый указатели объектов Node, чтобы они указывали на их братьев и сестер.Как только это будет сделано, вы можете избавиться от списка и просто вернуть объект первого узла.

Answer 3

Пусть ваша рекурсия вернет левый и правый конец сформированного списка. Затем вы связываете свой текущий узел с последним из левого списка и первым из правого списка. Основной случай, когда нет левого или правого элемента, который является узлом для обоих. После того, как все сделано, вы можете связать первый и последний из конечного результата. Ниже приведен код Java.

static void convertToSortedList(TreeNode T){
    TreeNode[] r = convertToSortedListHelper(T);
    r[1].next = r[0];
    r[0].prev= r[1];

}
static TreeNode[] convertToSortedListHelper(TreeNode T){        
    TreeNode[] ret = new TreeNode[2];
    if (T == null) return ret;
    if (T.left == null && T.right == null){ 
        ret[0] = T;
        ret[1] = T;
        return ret;
    }       
    TreeNode[] left = TreeNode.convertToSortedListHelper(T.left);
    TreeNode[] right = TreeNode.convertToSortedListHelper(T.right);

    if (left[1] != null) left[1].next = T;
    T.prev = left[1];

    T.next = right[0];
    if (right[0] != null) right[0].prev = T;

    ret[0] = left[0]==null? T:left[0];
    ret[1] = right[1]==null? T:right[1];

    return ret;
}

Answer 4

Это также должно работать:

NodeLL first = null;
NodeLL last = null;
private void convertToLL(NodeBST root) {
    if (root == null) {
        return;
    }
    NodeLL newNode = new NodeLL(root.data);
    convertToLL(root.left);   
    final NodeLL l = last;
    last = newNode;
    if (l == null)
        first = newNode;
    else {
        l.next = newNode;
        last.prev = l;
    }
    convertToLL(root.right);
}

Answer 5

/*  input: root of BST. Output: first node of a doubly linked sorted circular list. **Constraints**: do it in-place.     */

public static Node transform(Node root){

        if(root == null){
            return null;
        }

        if(root.isLeaf()){

            root.setRight(root);
            root.setLeft(root);
            return root;

        }

        Node firstLeft = transform(root.getLeft());
        Node firstRight = transform(root.getRight());
        Node lastLeft = firstLeft == null ? null : firstLeft.getLeft();
        Node lastRight=  firstRight == null ? null : firstRight.getLeft();

        if(firstLeft != null){

           lastLeft.setRight(root);
           root.setLeft(lastLeft);

           if(lastRight == null){

               firstLeft.setLeft(root);

           }
           else{

               firstLeft.setLeft(lastRight);
               root.setRight(firstRight);
           }
        }

        if(firstRight != null){

           root.setRight(firstRight);
           firstRight.setLeft(root);       

           if(lastLeft == null){

               root.setLeft(lastRight);
               lastRight.setLeft(root);
               firstLeft = root;

           }
           else{

               root.setLeft(lastLeft);
               lastRight.setRight(firstLeft);
           }
        }

        return firstLeft;
}

Answer 6

Добавьте следующий метод к вашему Node классу

public Node toLinked() {
    Node leftmost = this, rightmost = this;
    if (right != null) {
        right = right.toLinked();
        rightmost = right.left;
        right.left = this;
    }
    if (left != null) {
        leftmost = left.toLinked();
        left = leftmost.left;
        left.right = this;
    }
    leftmost.left = rightmost;
    rightmost.right = leftmost;
    return leftmost;
}

РЕДАКТИРОВАТЬ Поддерживая инвариант, что список, возвращаемый toLinked(), имеет правильную форму, вы можете легко получитькрайний левый и правый узлы в подсписке, возвращаемые рекурсивным вызовом на поддеревьях