468,140 Members | 1,428 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

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

Linked list/Tree using iterators?

User-Agent: OSXnews 2.081
Xref: number1.nntp.dca.giganews.com comp.lang.c++:817435
Hi,
I searched online to see if this is valid or not (since my classes are
still very incomplete, I am unable to check it using compilation) but
did not find anything that answers my question.
I am trying to implement a tree as a doubly linked list.

So, I have a class Node,

class Node
{
// some stuff ctors, dtors, etc, BUT NO Default ctor;

Node &parent_node; // I want to avoid copying. ??
vector< list<Node>::iterator child_nodes; // ??
};

class Tree
{
//again ctors, dtors, and some other stuff;
list< Nodetreeofnodes;
};

So are the above declarations correct? I don't have a default ctor for
the Node class so am not sure if above would work.
One more question(if above WORKS):

can is do something like this:

list<Node &treeofnodes; //??

The advantage that I see in this is that I won't have to waste time
copying an instance of class Node when I insert it into the list..
If none of this is supposed to work, then I guess I have no other
option but to resort to pointers and use
class Node
{
// some stuff ctors, dtors, etc, BUT NO Default ctor;

Node *parent_node; //
vector< Node * child_nodes; //
};

class Tree
{
//again ctors, dtors, and some other stuff;
list< Node*treeofnodes;
};

thanks,
--a.
Aug 20 '06 #1
1 2906
Amit Bhatia wrote:
I searched online to see if this is valid or not (since my classes are
still very incomplete, I am unable to check it using compilation) but
did not find anything that answers my question.
I am trying to implement a tree as a doubly linked list.

So, I have a class Node,

class Node
{
// some stuff ctors, dtors, etc, BUT NO Default ctor;

Node &parent_node; // I want to avoid copying. ??
vector< list<Node>::iterator child_nodes; // ??
};

class Tree
{
//again ctors, dtors, and some other stuff;
list< Nodetreeofnodes;
I think it would be easier if you just make a simple assumption: a Tree
is represented by its root Node (and every node of a Tree is just another
Tree, only smaller), so in that sense you ought to make your 'Node'
a special (extended) form of Tree, the one that has a parent. At least
I probably would make it that way (if you have to use a reference for
the parent). Otherwise, you could just make 'parent_node' a pointer to
a node and keep it null for the root node of a Tree.

Another note: with your current scheme a subtree cannot be pruned/grafted
on another tree.
};

So are the above declarations correct? I don't have a default ctor for
the Node class so am not sure if above would work.
It doesn't need a default c-tor. Besides, it probably can't have it,
since your 'Node' objects cannot move, once attached to a tree.
One more question(if above WORKS):

can is do something like this:

list<Node &treeofnodes; //??
No, you cannot have a list of references. References are not objects.
The advantage that I see in this is that I won't have to waste time
copying an instance of class Node when I insert it into the list..
If none of this is supposed to work, then I guess I have no other
option but to resort to pointers and use
class Node
{
// some stuff ctors, dtors, etc, BUT NO Default ctor;

Node *parent_node; //
vector< Node * child_nodes; //
};

class Tree
{
//again ctors, dtors, and some other stuff;
list< Node*treeofnodes;
};
In that case you just need to do

class Tree : public Node {
public:
Tree() : Node(NULL) {} // no parent
};

(assuming you have a c-tor that attaches a Node to another one).

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
Aug 21 '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
9 posts views Thread by Jess Austin | last post: by
3 posts views Thread by Pushkar Pradhan | last post: by
14 posts views Thread by Dave | last post: by
5 posts views Thread by Shane | last post: by
12 posts views Thread by joshd | last post: by
23 posts views Thread by Just Another Victim of the Ambient Morality | last post: by
4 posts views Thread by arnuld | last post: by
1 post views Thread by gcdp | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.