Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > n-ary tree

Reply
Thread Tools

n-ary tree

 
 
nandor.sieben@gmail.com
Guest
Posts: n/a
 
      10-22-2006
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: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
_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);
}

 
Reply With Quote
 
 
 
 
Daniel T.
Guest
Posts: n/a
 
      10-22-2006
In article <(E-Mail Removed) .com>,
http://www.velocityreviews.com/forums/(E-Mail Removed) 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.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
B+ Tree versus Ternary Search Tree Ramkumar Menon Java 2 08-16-2005 08:13 PM
B+ Tree versus Ternary Search Tree Ramkumar Menon Java 1 08-16-2005 09:46 AM
B+ Tree versus Ternary Search Tree Ramkumar Menon Java 0 08-16-2005 09:01 AM
B tree, B+ tree and B* tree Stub C Programming 3 11-12-2003 01:51 PM
Spanning Tree And Per Vlan Spanning Tree Amy L. Cisco 0 07-24-2003 10:01 PM



Advertisments