二叉搜索树移除——iop用while循环而不是递归实现

Question

在此视频 (https://youtu.be/WgdzNyhj6BU) 中展示了字典 ADT 的实现，递归用于查找中序前驱。在 47 分钟左右，演讲者说也可以使用 while 循环。我的问题是 while 循环是否可以与用于递归调用的相同函数签名一起使用？获取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。由于无法重新分配引用，我不确定如何沿着树向下走到正确的指针，然后 return 该指针作为引用。是否可以使用此结构编写一个 while 循环来 return 对指针的引用？这不是家庭作业；我只是好奇而已。谢谢！

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

第三种可能是编译器识别了原版的尾递归，转为循环

二叉搜索树移除——iop用while循环而不是递归实现

Binary search tree removal -- iop implemented with while loop instead of recursion

c++

binary-search-tree