n-ary tree

Discussion in 'C++' started by nandor.sieben@gmail.com, Oct 22, 2006.

  1. Guest

    I have an n-ary tree implementation consisting of a header file. I
    include this ntree.hh file and an example code below called ntree.C.
    All this seems to be working.

    I have a problem with the following code called trouble.C. The probem
    is nodes.push_back(node);
    line. The error message I get is below. What is the cause for this? Do
    I need a constructor? I am compiling it on Fedora.

    Nandor

    ==================================== error message

    g++ trouble.C
    /usr/lib/gcc/i386-redhat-linux/4.0.2/../../../../include/c++/4.0.2/bits/stl_construct.h:
    In function 'void std::_Construct(_T1*, const _T2&) [with _T1 =
    Tdata, _T2 = Tnode<Tdata>]':
    /usr/lib/gcc/i386-redhat-linux/4.0.2/../../../../include/c++/4.0.2/bits/stl_uninitialized.h:86:
    instantiated from '_ForwardIterator
    std::__uninitialized_copy_aux(_InputIterator, _InputIterator,
    _ForwardIterator, __false_type) [with _InputIterator =
    __gnu_cxx::__normal_iterator<Tnode<Tdata>*, std::vector<Tnode<Tdata>,
    std::allocator<Tnode<Tdata> > > >, _ForwardIterator =
    __gnu_cxx::__normal_iterator<Tnode<Tdata>*, std::vector<Tnode<Tdata>,
    std::allocator<Tnode<Tdata> > > >]'
    /usr/lib/gcc/i386-redhat-linux/4.0.2/../../../../include/c++/4.0.2/bits/stl_uninitialized.h:113:
    instantiated from '_ForwardIterator
    std::uninitialized_copy(_InputIterator, _InputIterator,
    _ForwardIterator) [with _InputIterator =
    __gnu_cxx::__normal_iterator<Tnode<Tdata>*, std::vector<Tnode<Tdata>,
    std::allocator<Tnode<Tdata> > > >, _ForwardIterator =
    __gnu_cxx::__normal_iterator<Tnode<Tdata>*, std::vector<Tnode<Tdata>,
    std::allocator<Tnode<Tdata> > > >]'
    /usr/lib/gcc/i386-redhat-linux/4.0.2/../../../../include/c++/4.0.2/bits/stl_uninitialized.h:254:
    instantiated from '_ForwardIterator
    std::__uninitialized_copy_a(_InputIterator, _InputIterator,
    _ForwardIterator, std::allocator<_Tp>) [with _InputIterator =
    __gnu_cxx::__normal_iterator<Tnode<Tdata>*, std::vector<Tnode<Tdata>,
    std::allocator<Tnode<Tdata> > > >, _ForwardIterator =
    __gnu_cxx::__normal_iterator<Tnode<Tdata>*, std::vector<Tnode<Tdata>,
    std::allocator<Tnode<Tdata> > > >, _Tp = Tnode<Tdata>]'
    /usr/lib/gcc/i386-redhat-linux/4.0.2/../../../../include/c++/4.0.2/bits/vector.tcc:279:
    instantiated from 'void std::vector<_Tp,
    _Alloc>::_M_insert_aux(__gnu_cxx::__normal_iterator<typename
    _Alloc::pointer, std::vector<_Tp, _Alloc> >, const _Tp&) [with _Tp =
    Tnode<Tdata>, _Alloc = std::allocator<Tnode<Tdata> >]'
    /usr/lib/gcc/i386-redhat-linux/4.0.2/../../../../include/c++/4.0.2/bits/stl_vector.h:610:
    instantiated from 'void std::vector<_Tp, _Alloc>::push_back(const
    _Tp&) [with _Tp = Tnode<Tdata>, _Alloc = std::allocator<Tnode<Tdata>
    >]'

    trouble.C:27: instantiated from here
    /usr/lib/gcc/i386-redhat-linux/4.0.2/../../../../include/c++/4.0.2/bits/stl_construct.h:81:
    error: no matching function for call to 'Tdata::Tdata(const
    Tnode<Tdata>&)'
    trouble.C:14: note: candidates are: Tdata::Tdata()
    trouble.C:14: note: Tdata::Tdata(const Tdata&)


    =============================================== code causing trouble

    // trouble.C

    #include <iostream>
    #include "ntree.hh"
    #include <vector>

    /*
    typedef struct {
    string a;
    string b;
    } Tdata;
    */

    struct Tdata {
    string a;
    string b;
    };


    typedef Tnode < Tdata > TNode;

    main ()
    {
    TNode head, node;
    make_head (head);
    vector<TNode> nodes;
    nodes.push_back(node);
    }

    =============================================== header file

    // ntree.hh

    #include <vector>
    #include <string>

    using namespace std;

    // data and the arrows

    template < class T > struct Tnode_
    {
    T data;
    vector < Tnode_ * >ch;
    Tnode_ *parentp;

    };

    // a Tnode is a pointer to a Tnode_ with member functions

    template < class T > struct Tnode
    {
    Tnode_ < T > *p;

    // is this node the head of the tree?

    bool ishead ()
    {
    return NULL == p->parentp;
    }

    // get the data value of the node

    T get ()
    {
    return p->data;
    }

    // set the data value of the node

    void set (T a)
    {
    p->data = a;
    }

    // the n-th child node

    Tnode child (int n)
    {
    Tnode node2;
    node2.p = p->ch[n];
    return node2;
    }

    // add a child node

    void add_child ()
    {
    Tnode_<T> * chp;
    chp = new Tnode_ < T >;
    chp->parentp = p;
    p->ch.push_back (chp);
    }

    // number of children

    int Nchildren ()
    {
    return p->ch.size ();
    }

    // the first child node

    Tnode begin ()
    {
    Tnode node2;
    node2.p = p->ch.front ();
    return node2;
    }

    // the last child node

    Tnode end ()
    {
    Tnode node2;
    node2.p = p->ch.back ();
    return node2;
    }

    // the parent node

    Tnode parent ()
    {
    Tnode node2;
    node2.p = p->parentp;
    return node2;
    }

    T *operator & ()
    {
    return &p->data;
    }

    };

    // make a tree head and set node to this head

    template < class T > void
    make_head (Tnode < T > &node)
    {
    node.p = new Tnode_ < T >;
    node.p->parentp = NULL;

    }

    // print the tree

    template < class T > void
    travel (Tnode < T > node, int level)
    {
    for (int i = 0; i < level; i++)
    cout << " :";
    cout << ". ";
    cout << node.get () << "\n";
    for (int i = 0; i < node.Nchildren (); i++)
    travel (node.child (i), level + 1);

    }

    // cut a child

    template < class T > void
    cut_child (Tnode < T > node, int n)
    {
    Tnode<T> childnode = node.child (n);
    while (childnode.Nchildren () > 0) {
    cut_child (childnode, 0);
    }
    delete node.p->ch[n];
    node.p->ch.erase (node.p->ch.begin () + n);
    }

    ========================================= working example code

    // ntree.C

    #include <iostream>
    #include "ntree.hh"
    #include <vector>

    typedef struct {
    string a;
    string b;
    } Tdata;

    typedef Tnode < Tdata > TNode;

    main ()
    {
    TNode head, node;
    vector<TNode> nodes;
    nodes.push_back(node);
    make_head (head);
    node = head;
    Tdata data;
    data.a="one";
    node.set (data);

    node.add_child ();
    node.add_child ();

    node = node.end ();
    data.a="three";
    node.set (data);
    node = node.parent ();
    node = node.begin ();
    data.a="two";
    node.set (data);

    node.add_child ();
    node.add_child ();
    node.add_child ();

    node = node.begin ();
    data.a="apple";
    node.set (data);
    node = node.parent ();
    node = node.end ();
    data.a="peach";
    node.set (data);
    node = node.parent ();
    node = node.child (1);
    data.a="banana";
    node.set (data);

    node.add_child ();
    node = node.begin ();
    data.a="cherry";
    node.set (data);

    travel (head, 0);

    cout << "-----------\n";
    data = node.get();
    cout << data.a << "\n";
    (*&node).a = "CHERRY";
    while (! node.ishead()) {
    node=node.parent();
    data = node.get();
    cout << data.a << "\n";
    }

    cout << "-----------\n";
    cut_child(head,0);
    travel(head, 0);
    }
    , Oct 22, 2006
    #1
    1. Advertising

  2. Daniel T. Guest

    In article <>,
    wrote:

    > T *operator & ()
    > {
    > return &p->data;
    > }


    Get rid of the above function.

    --
    There are two things that simply cannot be doubted, logic and perception.
    Doubt those, and you no longer have anyone to discuss your doubts with,
    nor any ability to discuss them.
    Daniel T., Oct 22, 2006
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Wynan James

    Depth of n-ary tree

    Wynan James, Sep 29, 2003, in forum: Java
    Replies:
    10
    Views:
    11,095
    Stefan Poehn
    Sep 30, 2003
  2. Stevey

    N-ary tree code?

    Stevey, Apr 9, 2005, in forum: Java
    Replies:
    1
    Views:
    3,719
    Abhijat Vatsyayan
    Apr 10, 2005
  3. Replies:
    4
    Views:
    908
    Bo Persson
    Apr 14, 2008
  4. Guilfoy9898

    M-ary Tree

    Guilfoy9898, Jul 25, 2008, in forum: C Programming
    Replies:
    0
    Views:
    421
    Guilfoy9898
    Jul 25, 2008
  5. cgirl
    Replies:
    1
    Views:
    332
    red floyd
    Jun 26, 2009
Loading...

Share This Page