Arbre qui peut contenir la meme valeur

#include <map>
#include <vector>
#include <iostream>

// Un noeud de l'arbre
class node_t{
    protected:
    unsigned id; // l'id de ce noeud
    std::map<unsigned,struct node_t *> neigh; // les noeuds fils

    public:
    // Le constructeur par défaut
    node_t(){}

    // Le constructeur
    node_t(unsigned id0):id(id0){}

    // Accesseur
    inline unsigned get_id() const{
        return id;
    }

    // Ajouter un noeud fils si besoin
    struct node_t * add_neigh(unsigned id0){
        std::map<unsigned,struct node_t *>::iterator
            fit = neigh.find(id0);
        // Ce noeud fils existe déjà, on retourne son adresse
        if (fit != neigh.end()){
            return fit->second;
        }
        // Ce noeud fils n'existe pas
        node_t *new_node = new node_t(id0);
        neigh[id0] = new_node;
        return new_node;
    }

    protected:
    void show_impl(
        const std::vector<unsigned> & prefix // le morceau d'arbre actuellement parcouru
    ) const{
        if(neigh.empty()){ // on a atteint une feuille
            for(std::size_t i=0;i<prefix.size();++i) std::cout << prefix[i] << ' ';
            std::cout << std::endl;
        }else{ // il y a des noeuds fils
            std::map<unsigned,struct node_t *>::const_iterator
                mit (neigh.begin()),
                mend(neigh.end());
            // pour chaque fils
            for(;mit!=mend;++mit){
                const unsigned & id_next = mit->first;
                const node_t & node_next = *(mit->second);
                // on rajoute au prefixe courant l'id du noeud fils
                std::vector<unsigned> prefix_next = prefix;
                prefix_next.push_back(id_next);
                node_next.show_impl(prefix_next);
            }
        }
    }

    public:
    // Afficher ce noeud et ses noeud fils
    void show() const{
        show_impl(std::vector<unsigned>());
    }
};

// La classe d'arbre
class tree_t{
    protected:
    struct node_t *root; // le noeud racine

    // Fonction appelée récursivement pour insérer le chemin dans l'arbre
    // path = p1,p2,...
    // on est rendu à la position i (node_cur = pi)
    // on est en train d'inserer p(i+1) (node_next) si nécessaire
    void add_path_impl(
        const std::vector<unsigned> & path,
        struct node_t *node_cur,
        std::size_t i
    ){
        if(i==path.size()) return;
        struct node_t *node_next = node_cur->add_neigh(path[i]);
        add_path_impl(path,node_next,i+1);
    }

    public:

    // Le constructeur
    tree_t(){
        root = new node_t();
    }

    // Le destructeur
    ~tree_t(){
        delete root;
    }

    // Ajouter un chemin
    inline void add_path(const std::vector<unsigned> & path){
        add_path_impl(path,root,0);
    }

    // Afficher l'arbre
    inline void show() const{
        root->show();
    }
};

int main(){
    std::vector<unsigned> path1(4),path2(4),path3(3);
    path1[0] = 2; path1[1] = 4; path1[2] = 5; path1[3] = 4;
    path2[0] = 2; path2[1] = 4; path2[2] = 3; path2[3] = 7;
    path3[0] = 1; path3[1] = 2; path3[2] = 3;
    tree_t tree;
    tree.add_path(path1);
    tree.add_path(path2);
    tree.add_path(path3);
    std::cout << "tree built" << std::endl;
    tree.show();
    return 0;
}

(mando@polgara) (~) $ g++ -W -Wall -g plop.cpp
(mando@polgara) (~) $ ./a.out
tree built
1 2 3
2 4 3 7
2 4 5 4

#include <iostream>
#include <set>

template <typename T>
bool cherche(const std::multiset<T> & m,const T & t){
    return (m.find(t) != m.end());
}

int main(){
    std::multiset<int> m;
    m.insert(2);
    m.insert(3);
    m.insert(1);
    m.insert(2);
    m.insert(4);
    m.insert(2);
    m.insert(3);

    {
        std::multiset<int>::const_iterator
            mit (m.begin()),
            mend(m.end());
        for(;mit!=mend;++mit) std::cout << *mit << ' ';
        std::cout << std::endl;
    }

    cherche(m,3) ?
        std::cout << "3 est dans m" << std::endl :
        std::cout << "3 n'est pas dans m" << std::endl;
    cherche(m,7) ?
        std::cout << "7 est dans m" << std::endl :
        std::cout << "7 n'est pas dans m" << std::endl;
    return 0;
}