Linked list/Tree using iterators?

[Amit Bhatia]

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< Node> treeofnodes;
};

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.

 

[Victor Bazarov]

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< Node> treeofnodes;

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