binary_tree.cpp

#include <iostream>
#include <utility>
#include <functional>
#include <cstdlib>

template<class Key, class Value>
class seq_binary_tree{
public:
    typedef Key key_type;
    typedef Value value_type;
    struct item{
        item() : key(), value(){
            for(std::size_t i = 0; i < 2; ++i){ link[i] = nullptr; }
            parent = nullptr;
        }

        ~item(){
            for(std::size_t i = 0; i < 2; ++i){ delete link[i]; }
        }

        item *link[2], *parent;
        key_type key;
        value_type value;
    };

    typedef std::function<void(item&)> scanner;

    seq_binary_tree(){
        root = nullptr;
    }
    
    ~seq_binary_tree(){
        delete root;
    }

    template<class Compare>
    void add(const key_type &key, const value_type &value, Compare &cmp){
        auto result = search_impl(key, cmp);
        *result.first = new item;
        (*result.first)->parent = result.second;
        (*result.first)->key = key;
        (*result.first)->value = value;
    }

    template<class Compare>
    item &search(const key_type &key, Compare &cmp){
        auto result = search_impl(key, cmp);
        return *result.second;
    }

    void scan(const scanner &fn){
        if(root == nullptr){ return; }
        scan_impl(fn, root);
    }

private:
    template<class Compare>
    std::pair<item**, item*> search_impl(const key_type &key, Compare &cmp){
        item **ptr = &root, *prev = nullptr;
        while(*ptr){
            prev = *ptr;
            ptr = &((*ptr)->link[cmp(key, (*ptr)->key) ? 0 : 1]);
        }
        return std::make_pair(ptr, prev);
    }
 
    static void scan_impl(const scanner &fn, item *curr){
        for(std::size_t i = 0; i < 2; ++i){
            if(curr->link[i]){ scan_impl(fn, curr->link[i]); }
        }
        fn(*curr);
    }

    item *root;
};

struct cmp{
    cmp() : idx(0){}
    std::size_t idx;
    bool operator()(const std::string &x, const std::string &y){
        for(; ; ){
            if(idx == x.size()){
                if(idx == y.size()){ return false; }
                if(idx < y.size()){ return true; }
            }
            if(idx == y.size()){ return false; }
            unsigned char xc = x[idx], yc = y[idx];
            if(xc == yc){ ++idx; }else{
                if(xc < yc){
                    return true;
                }else{
                    if(idx > 0){ --idx; }
                    return false;
                }
            }
        }
    }
};

int main(){
    typedef seq_binary_tree<std::string, int> map;
    map m;
    m.add("000", 0, cmp());
    m.add("011", 6, cmp());
    m.add("010", 2, cmp());
    m.add("101", 5, cmp());
    m.add("001", 4, cmp());
    m.add("110", 3, cmp());
    m.add("100", 1, cmp());
    m.add("111", 7, cmp());
    m.scan([](map::item &a){ std::cout << a.value << " "; });
    std::cout << "----\n";
    std::cout << m.search("111", cmp()).value << std::endl;
    return 0;
}