468,512 Members | 1,485 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,512 developers. It's quick & easy.

n-ary tree

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_iterato r<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<TNodenodes;
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<Tchildnode = 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<TNodenodes;
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 '06 #1
1 4472
In article <11**********************@m73g2000cwd.googlegroups .com>,
na***********@gmail.com 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.
Oct 22 '06 #2

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

5 posts views Thread by Jeffrey Silverman | last post: by
reply views Thread by Tree menu using XML | last post: by
4 posts views Thread by Tarique Jawed | last post: by
2 posts views Thread by New | last post: by
5 posts views Thread by Mike | last post: by
2 posts views Thread by Kiran | last post: by
reply views Thread by NPC403 | last post: by
1 post views Thread by fmendoza | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.