n-ary tree

[nandor.sieben]

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:ointer, 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>:ush_back(const

]'

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);
}

 

[Daniel T.]

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

Get rid of the above function.