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

葉はnullを指します。次のような二重リンクリストを作成する必要があります

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返すメソッドが必要なようです。単純なツリーから始めて、これに再帰的にアプローチします。NodeNode

   2
   |
|-----|
1     3

ツリーがいっぱいになることが保証されているかどうかはわかりません。そのため、を許可する必要があり1ます。この単純なツリーでは、次の方法が機能するはずです。3null

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日更新：既存のノードオブジェクトを再利用する必要があるため、ノードオブジェクトをリストに追加した後、リストを繰り返し処理し、ノードオブジェクトの左右のポインターをリセットしてポイントすることができます。彼らの兄弟。それが完了すると、リストを削除して、最初のノードオブジェクトを返すことができます。

于 2012-03-05T20:51:25.203 に答える
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 に答える
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 に答える
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 に答える