用unique_ptr实现二叉搜索树中的迭代findMin（）

Question

class BinarySearchTree
{
public:
struct Node {
    Node(int k)
    {
        key = k;
        left = nullptr;
        right = nullptr;
    }
    int key;
    // This will auto-destroy all child nodes when this Node is destroyed
    std::unique_ptr<Node> left;
    std::unique_ptr<Node> right;
};

BinarySearchTree():
      m_root(nullptr)
    , m_depth(0)
{}

void deleteKey(int key)
{
    deleteKeyRec(key, m_root);
}

void deleteKeyRec(int key, std::unique_ptr<Node>& node)
{
    if (key == node->key) {
        // This node needs to be deleted and replaced with one of its children
        if (node->left == nullptr && node->right == nullptr) {
            // Node to be deleted has no children
            node = nullptr;
        }
        else if (node->left != nullptr && node->right == nullptr) {
            // Only left child present
            node = std::move(node->left);
        }
        else if (node->left == nullptr && node->right != nullptr) {
            // Only right child present
            node = std::move(node->right);
        }
        else {
            // Both children present, find minimum node in left subtree and replace
            auto minNode = findMin(node->left);
            node->key = minNode->key;
            deleteKeyRec(minNode->key, minNode);                
        }
    }
    else if (key < node->key) {
        deleteKeyRec(key, node->left);
    }
    else if (key > node->key) {
        deleteKeyRec(key, node->right);
    }
}

std::unique_ptr<Node> findMin(std::unique_ptr<Node> & node)
{
    Node *current = node.get();
    while (current->left) {
        current = current->left.get();
    }
    return std::make_unique<Node>(current);
}

private:
    std::unique_ptr<Node> m_root;   // Clean-up all children when this object is destroyed
    int m_depth;

};

void deleteKeyRec(int key, std::unique_ptr<Node>& node)
{
    if (key == node->key) {
        // This node needs to be deleted and replaced with one of its children
        if (node->left == nullptr && node->right == nullptr) {
            // Node to be deleted has no children
            node = nullptr;
        }
        else if (node->left != nullptr && node->right == nullptr) {
            // Only left child present
            node = std::move(node->left);
        }
        else if (node->left == nullptr && node->right != nullptr) {
            // Only right child present
            node = std::move(node->right);
        }
        else {
            // Both children present, find minimum node in right subtree and replace 'node'
            Node *owner = nullptr;         // stays one step behind current after first iteration
            Node *current = node->right.get();
            while (current->left.get()) {
                owner = current;
                current = current->left.get();
            }

            //auto minNode = findMin(node->left.get());
            node->key = current->key;      // transfer the key here, we do not free the memory of this node.
            if (owner == nullptr) {
                // The right node of 'node' is the correct replacement as it has no children
                node->right = nullptr;  // delete the node from which key was copied
            }
            else {
                // A left node was found when traversing the right subtree of 'node', so that node's owner now will have no left child!
                // This left child thats being deleted has already had its key copied to 'node' via 'current'
                owner->left = nullptr;   // delete the node from which key was copied
            }
        }
    }
    else if (key < node->key) {
        deleteKeyRec(key, node->left);
    }
    else if (key > node->key) {
        deleteKeyRec(key, node->right);
    }
}

Answer 1

find函数应该返回一个指向所找到元素的引用/指针/迭代器。它根本不应该返回所属指针。同样，它也不应该将所属指针作为参数。它应该使用指向节点的引用/指针/迭代器。

每个对象/节点必须完全由一个std::unique_ptr所有。因此，如果不打算从树中删除找到的节点，则不应将其作为std::unique_ptr返回。

例如：

Node& findMin(const Node& node)
{
    Node *current = node.get();
    while (current->left) {
        current = current->left.get();
    }
    return *current;
}