mardi 2 février 2021

The proper way to increment my binary tree

Here is the class I've created

#include <memory>

template <typename T> 
class binary_tree {

private:
    T t_data;
    std::unique_ptr<binary_tree<T>> t_left, t_right;
    
    class binary_tree_iterator {                  // -----------------------
    private:
        T data;
    public:                                       
        binary_tree_iterator(T d) : data(d) {}    //     Iterator class
        T& operator*() {return data;}
        binary_tree_iterator& operator++() {} // <--------- ??????
    };                                            
                                                  // ------------------------
public:
    binary_tree(T d) : t_data(d), t_left(nullptr), t_right(nullptr)
    {}
    
    void insert(T data) {
        if(data <= t_data) {
            if(t_left == nullptr) {
                t_left = std::unique_ptr<binary_tree<T>>(new binary_tree<T>(data));
            } else {
                t_left->insert(data);
            }          
        } else {
            if(t_right == nullptr)
                t_right = std::unique_ptr<binary_tree<T>>(new binary_tree<T>(data));
            else
                t_right->insert(data);
        }
    }
    
    const T data() const {
        return t_data;
    }
    
    const std::unique_ptr<binary_tree<T>>& left() const {
        return t_left;
    }
    
    const std::unique_ptr<binary_tree<T>>& right() const {
        return t_right;
    }
    
    binary_tree_iterator begin() {      
        if(t_left == nullptr) {
            return binary_tree_iterator(t_data);
        } else {
            return t_left->begin();
        }
    }
    
    binary_tree_iterator end() {
        if(t_right == nullptr) {
            return binary_tree_iterator(t_data);
        } else {
            return t_right->end();
        }
    }
};

I've declared my iterator class inside of my container class. This may have been a mistake but either way I'm not sure how to define my overloaded increment function. Once I've found begin() I've lost my way back. It seems like unique_ptr() is designed for one way pointing. Assuming I have to use unique_ptr in this fashion, is there some work around here? I've thought about giving each instance of binary_tree a head member that points back from whence it came, but each node should only be accessible from the node above it. I make some sort of index but that seems to completely defeat the purpose of this container type. I'm solving exercise so I'm restricted to using the unique_ptr.

Aucun commentaire:

Enregistrer un commentaire