algorithm - BST 到 LinkList 并返回到相同的 BST

Question

由于我找不到任何有用的东西，所以我在这里问我的问题：

我们如何在不使用任何额外空间的情况下将 BST 转换为有序链接列表，然后再转换回“相同”的 BST。

到目前为止我尝试过的（尽管仍在做）：我尝试了 Morris Traversal 连接到下一个有序后继节点，但它无法连接所有节点，仅适用于左子树和右子树，不是树的实际根。请建议我如何将 Tree 转换为 Linked List 并返回到 Same 树...

Answer 1

要将树存储在列表中 - 您至少需要两个列表：一个用于前序遍历，另一个用于中序遍历。

幸运的是 - 由于树是 BST，因此中序遍历只是排序列表。

因此，您可以存储前序遍历（您可以尝试就地进行）并通过对重新构建的元素进行排序，您可以获得中序遍历。

这篇文章讨论了如何从它的中序和前序遍历中重建一棵树。

Answer 2

二叉搜索树列表：

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

您只需要按顺序遍历您的列表并调用基于我上面的伪代码实现的函数。祝你的家庭作业好运。

Answer 3

I think I found the solution myself: below is the complete Java implementation The logic + pseudo Code is as below [1] Find the left most node in the tree, that will be the head of the LinkList, store it in the class

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] Do the reverse - inorder traversal of the tree to convert it to a LL on right pointer, and make sure the left pointer is always pointing to the parent of the node.

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] To convert it back :

Traverse the list and find the node with left pointer as null, Make it the root, break the link of this root in the linklist and also from its children...

Now the link list is broken into two parts one for left Subtree and one for right subtree, recursively find the roots in these two list and make them the left and right child, Please refer the function 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;
}

Logic to detach the children is simple : Iterate through the list and look for the nodes with left pointer equal to root.

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

    while(curr != null)
    {
        if(curr.left == root)
        {
            curr.left = null;
        }
        curr = curr.right;
    }
}

Answer 4

Here is a recursive solution for BST to LL, hope you find it useful.

    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;
    }