如何删除具有 O(1) 额外内存的二叉树？

Question

我想知道是否可以在不使用递归或堆栈的情况下删除具有 O(1) 额外内存的二叉树。

我已经设法编写了朴素的递归后序遍历解决方案（使用堆栈内存）：

void deleteTreeRec(Node *root)
{
   if (root == NULL) return;
   deleteTreeRec(root->left);
   deleteTreeRec(root->right);
   cout << "Deleting node " << root->data << endl;
   delete root;
}

我听说这可以使用 (inorder) Morris 遍历来实现，这似乎是错误的，或者至少违反直觉，因为据我所知，树删除需要以后序方式遍历 (首先删除两个子树，然后才删除根）。但是，我还没有找到任何详细的 description/pseudocode 解决方案，因此我在这里试试运气。

如果有人能阐明这个问题，我们将不胜感激。谢谢！

Answer 1

在删除过程中，二叉树的现有节点可以用作单linked列表：始终使用left“link”的节点被视为linked 列表。

要删除所有节点，只需重复以下步骤：

找到“linked 列表的尾部”
如果 right 不为空，将其移至“列表”的末尾
临时存储“列表”中下一个元素的指针
如果“列表”不为空，则用临时替换旧的头部并重复

在前一个尾部开始搜索新尾部导致算法运行 in O(n) 其中 n 是二叉树中的节点数。

void deleteTree(Node* root)
{
    Node* tail = root;
    while (root != nullptr)
    {
        // update tail
        while (tail->left != nullptr)
        {
            tail = tail->left;
        }

        // move right to the end of the "list"
        // needs to happen before retrieving next, since the node may only have a right subtree
        tail->left = root->right;

        // need to retrieve the data about the next
        Node* next = root->left;

        delete root;

        root = next;
    }
}

如何删除具有 O(1) 额外内存的二叉树？

How can I delete a binary tree with O(1) additional memory?

c++

algorithm

tree

binary-tree