二进制搜索树删除- iop用while循环代替递归实现。

Question

在此视频(https://youtu.be/WgdzNyhj6BU)中显示字典ADT的实现，递归用于查找无序的前驱者。在47分钟的时间内，演讲者说也可以使用while循环。我的问题是，with循环可以使用与递归调用相同的函数签名吗？获取iop的方法是rightMostChild：

TreeNode*& rightMostChild(TreeNode*& root)

class Dictionary {
    struct TreeNode {
        TreeNode(const int& key, const std::string& value)
            : key (key), value (value), left (nullptr), right (nullptr) {}
        int key;
        std::string value;        
        TreeNode* left;
        TreeNode* right;        
    }; 
    TreeNode* _root;              
public:
    Dictionary() : _root (nullptr) {}        
    std::string find(const int& key)
    {
        TreeNode* item = _find(_root, key);
        if (item == nullptr)
            return "key not in dictionary";
        else
            return item->value;        
    }        
    void insert(const int& key, const std::string& value)
    {        
        _find(_root, key) = new TreeNode(key, value);
    }    
    void del_item(const int& key)
    {
        remove(_root, key);
    }
    void remove(TreeNode*& root, const int& key)
    {
        if (root != nullptr)
        {
            if (root->key == key)
                doRemoval(root);                
            else if (root->key > key)
                remove(root->left, key);
            else
                remove(root->right, key);               
        }
    }    
    void doRemoval(TreeNode*& root)
    {
        if (root->left && root->right)
            twoChildRemove(root);
        else if (root->left == nullptr && root->right == nullptr)
            noChildRemove(root);
        else
            oneChildRemove(root);
    }    
    void noChildRemove(TreeNode*& root)
    {
        TreeNode* temp = root;
        root = nullptr;
        delete temp;
    }    
    void oneChildRemove(TreeNode*& root)
    {
        TreeNode* temp = root;
        if (root->left) root = root->left;
        else root = root->right;
        delete temp;
    }    
    void twoChildRemove(TreeNode*& root)
    {        
        TreeNode*& iop = rightMostChild(root->left);
        root->key = iop->key;
        root->value = iop->value;
        doRemoval(iop);
    }    
     TreeNode*& rightMostChild(TreeNode*& root)
    {
        if (root->right == nullptr) return root;
        else return rightMostChild(root->right);
    }  
private:       
    TreeNode*& _find(TreeNode*& root, const int& key)
    {
        if (root == nullptr)
            return root;
        if (root->key == key)
            return root;
        else if (root->key > key)
            return _find(root->left, key);
        else
            return _find(root->right, key);
    }            
};

我最初尝试过：

TreeNode*& rightMostChild(TreeNode*& root)
    {
        while (root->right != nullptr)
            root = root->right;
        return root;
    }

但这只是将根重新分配到iop上。由于引用不能重新分配，我不知道如何沿着树向下走到正确的指针，然后返回该指针作为引用。是否有可能用此结构编写with循环以返回对指针的引用？这不是作业，我只是好奇。谢谢!

Answer 1

有几种解决办法。

一种是使用双指针。

TreeNode *& rightMostChild(TreeNode*& root) {
    TreeNode **n = &root;
    while ((*n)->right != nullptr)
        n = &(*n)->right;
    return (*n)->right;
}

如果不喜欢双指针，可以使用单个指针：

TreeNode *& rightMostChild(TreeNode*& root) {
    if (root->right == nullptr)
        return root;
    TreeNode *n = root;
    while (n->right->right != nullptr)
        n = n->right;
    return n->right;
}

第三种可能是编译器识别原始版本的尾递归并将其转换为循环。