0 
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指针应该是列表的指针。

我的想法是：由于树是有序树，因此中序遍历会给我一个排序列表。但是在进行中序遍历时，我无法看到将指针移动到何处以及如何移动以形成双向链表。

PS我检查了这个问题的一些变体，但没有一个给我任何线索。

4

6 回答 6

11

听起来您需要一个方法来接受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;
}

如果我正确涵盖了所有链接分配，那么这应该就是您所需要的。

于 2012-03-05T21:25:23.960 回答
2

对列表进行有序遍历，在遇到每个列表项时将其添加到双向链表中。完成后，在第一项和最后一项之间添加显式链接。

2012 年3 月 6 日更新：由于您必须重用已有的 Node 对象，因此在将节点对象放入列表后，您可以遍历列表并重置 Node 对象的左右指针以指向他们的兄弟姐妹。完成后，您可以摆脱列表并简单地返回第一个节点对象。

于 2012-03-05T20:51:25.203 回答
1

让您的递归返回已形成列表的左端和右端。然后将当前节点链接到左侧列表的最后一个和右侧列表的第一个。基本情况它，当没有左或右元素时，它是它自己的节点。全部完成后，您可以链接最终结果的第一个和最后一个。下面是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;
}
于 2015-01-01T00:04:40.350 回答
1

这也应该有效：

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);
}
于 2013-02-28T10:56:06.143 回答
0

将以下方法添加到您的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()具有正确形式的不变量，您可以轻松获取子树上递归调用返回的子列表中的最左边和最右边的节点

于 2012-03-05T21:52:23.473 回答
0 
/*  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;
}
于 2013-10-28T00:20:37.227 回答