1

役立つものが見つからなかったので、ここで質問します。

余分なスペースを使用せずに、BST をインオーダー リンクリストに変換し、「同じ」BST に戻すにはどうすればよいでしょうか。

これまでに試したこと (まだ実行中): Morris Traversal を使用して次の順序の後継者にリンクしようとしましたが、すべてのノードに接続できず、左のサブツリーと右のサブツリーでのみ機能します。ツリーの実際のルートではありません。ツリーをリンクリストに変換して同じツリーに戻す方法を提案してください...

4

4 に答える 4

0

ツリーをリストに格納するには、少なくとも2つのリストが必要です。1つはプレオーダートラバーサル用で、もう1つはインオーダートラバーサル用です。

幸いなことに、ツリーはBSTであるため、順序どおりのトラバーサルはソートされたリストにすぎません。

したがって、プレオーダートラバーサルを保存でき（インプレースで実行してみることができます）、再構築で要素を並べ替えることで、インオーダートラバーサルを取得できます。

この投稿では、ツリーのインオーダートラバーサルとプレオーダートラバーサルからツリーを再構築する方法について説明します。

于 2012-09-24T11:14:09.870 に答える
0

リストするバイナリ検索ツリー:

subTreeToList(node)
    if (node.hasLeft()) then subTreeToList(node.left, list)
    list.add(node.Value)
    if (node.hasRight()) subTreeToList(node.right, list)
    end if
subTreeToList end

treeToList(tree)
    subTreeToList(tree.root)
treeToList end

list <- new List()
treeToList(tree)

上記のアイデアをソリューションに実装する必要があります。オブジェクト指向テクノロジを使用している場合は、リストとツリーをデータ メンバーにする必要があります。それ以外の場合は、参照として関数に渡す必要があります。

ツリーへの挿入が次のようになることを知っていれば、ツリーを元に戻すことができます。

Insert(tree, value)
    if (tree.root is null) then
        tree.createRoot(value)
    else
        node <- tree.root
        while (((node.value < value) and (node.hasRight())) or ((node.value > value) and (node.hasLeft())))
            if ((node.value < value) and (node.hasRight())) then node <- node.right()
            else node <- node.left()
            end if
        while end
        if (node.value > value) then node.createLeft(value)
        else node.createRight(value)
        end if
    end if
insert end

リストを順番にトラバースし、上記の疑似コードに基づいて実装された関数を呼び出すだけです。宿題頑張ってください。

于 2012-09-24T11:32:33.760 に答える
0

これは、BST から LL への再帰的な解決策です。お役に立てば幸いです。

    Node BSTtoLL(BST root) {

        if(null == root) return null;

        Node l = BSTtoLL(root.left);
        Node r = BSTtoLL(root.right);

        Node l1 = null;
        if(null != l) {
            l1 = l;
            while(null != l.left) { l = l.left; }
            l.left = root;
            l.right = null;
        }
        if(null != r) {
            root.left = r;
            root.right = null;
        }

        if(null != l1) return l1;
        return root;
    }
于 2012-12-22T10:02:31.603 に答える
0

私は自分で解決策を見つけたと思います: 以下は完全な Java 実装です ロジック + 擬似コードは以下のとおりです [1] ツリーの左端のノードを見つけ、それが LinkList の先頭になり、クラスに保存します

Node HeadOfList = null;
    findTheHeadOfInorderList (Node root)
    {
        Node curr = root;

        while(curr.left != null)
            curr = curr.left;

        HeadOfList = curr; // Curr will hold the head of the list

    }

[2] ツリーを逆順に走査して、ツリーを右ポインタの LL に変換し、左ポインタが常にノードの親を指していることを確認します。

updateInorderSuccessor(Node root, Node inorderNext, Node parent)
{
    if(root != null) 
                 //Recursively call with the right child
            updateInorderSuccessor(root.right, inorderNext, root);

                // Update the in-order successor in right pointer
        root.right = inorderNext; 
        inorderNext = root;

                //Recursively call with the left child
        updateInorderSuccessor(root.left, inorderNext, root);

                // Update the parent in left pointer
        root.left = parent;
    }
}

[3] 元に戻すには:

リストをトラバースし、左ポインタが null のノードを見つけます。それをルートにし、リンクリスト内のこのルートのリンクを解除し、その子からも解除します...

これでリンク リストは左サブツリー用と右サブツリー用の 2 つの部分に分割されます. これら 2 つのリストのルートを再帰的に見つけて, 左右の子にします. 関数 restoreBST() を参照してください.

Node restoreBST(Node head)
{
    if(head == null || (head.left == null && head.right == null)) return root;

    Node prev, root, right, curr;
            curr = head;

    // Traverse the list and find the node with left as null
    while(curr != null)
    {
        if(curr.left == null)
        {
            // Found the root of this tree
            root = curr;
                            // Save the head of the right list
            right = curr.right;
                            // Detach the children of the root just found, these will be updated later as a part of the recursive solution
            detachChildren(curr, head);
            break;
        }
        prev = curr;
        curr = curr.right;
    }

    // By now the root is found and the children of the root are detached from it.
    // Now disconnect the right pointer based connection in the list for the root node, so that list is broken in to two list, one for left subtree and one for right subtree
    prev.right = null;

    root.right = null;

    // Recursively call for left and right subtree

    root.left = restoreBST(head);
    root.right = restoreBST(right);

    //now root points to its proper children, lets return the root
    return root;
}

子をデタッチするロジックは単純です。リストを繰り返し処理し、左ポインタがルートに等しいノードを探します。

private void detachChildren(AvlNode root, AvlNode head) {
    AvlNode curr = head;

    while(curr != null)
    {
        if(curr.left == root)
        {
            curr.left = null;
        }
        curr = curr.right;
    }
}
于 2012-09-25T02:15:49.493 に答える