lundi 6 mai 2019

How to use unique_ptr for iteration?

I have a binary search tree implementation where each node of the tree has this structure.

struct node {
        T data;
        std::unique_ptr<node> left, right;
        node(T data): data(data), left(nullptr), right(nullptr) {}
    };

I have implemented a findmin routine that returns the minimum data(left most node's data), given the root of the tree. At present, I have implemented it recursively.

template<typename T>
T Btree<T>::_findmin(std::unique_ptr<node>& curr)
{
    if (curr && curr->left == nullptr)
        return curr->data;
    return _findmin(curr->left);    
}

This works but I would like to implement it iteratively. For a normal pointer, we can assign and then keep traversing the leftmost node curr = curr->left , but such an assignment won't work for unique_ptr.

Is there a way to implement it iteratively?

Aucun commentaire:

Enregistrer un commentaire