CODEWITHSUNDEEP
c++tree
sdasdadas
sdasdadas

Reputation: 25096

tree.hh - C++ Leaf Traversal

The output from the following code is incorrect. It should only output the leaves in the tree:

tree<Node> gameTree;
tree<Node>::iterator root = gameTree.insert(gameTree.begin(),Node(14));
tree<Node>::iterator first = gameTree.append_child(root,Node(32.0));
tree<Node>::iterator second = gameTree.append_child(root,Node(64.0));
gameTree.append_child(second,Node(21.0));
gameTree.append_child(second,Node(24.0));

tree<Node>::iterator begin = gameTree.begin_leaf();
tree<Node>::iterator end = gameTree.end_leaf();
int x = 0;
while (begin != end) 
{ 
    cout << begin->value << endl; 
    begin++;
}

But it outputs:

32
64
21
24

when the output SHOULD be:

32
21
24

Upvotes: 1

Views: 1324

Answers (3)

Keith Irwin
Keith Irwin

Reputation: 5668

What's happening is that the iterator class is actually just a typedef for the pre_order_traversal class. So when you set the result of gameTree.beginLeaf() (which returns a leaf_iterator) to an iterator, it invokes the copy constructor of pre_order_iterator because there's a constructor defined for pre_order_traversal(const iterator_base&) (iterator_base is the superclass for all other iterators, including the leaf_iterator), so this creates a new pre_order_iterator from the leaf_iterator. Then when you use that iterator, it does a depth-first traversal rather than iterating through the leaves. If you switch to leaf_iterator instead of iterator, the problem will disappear.

This is also why the direct form mentioned in a comment below (where the value is not assigned to an iterator) works properly.

Upvotes: 2

daven11
daven11

Reputation: 3025

From the docs you should be using a leaf_iterator rather than an iterator, the output you're seeing is from an in order traversal, you want to do a leaf traversal I'm guessing.

btw, thanks for posting this I was just starting in a search for a tree container

hth

Upvotes: 2

Sebastian Mach
Sebastian Mach

Reputation: 39089

I don't know what tree<> is, nor do I know the semantics of append_child, but from what I see, 32, 64, 21 and 24 are all below the root of the hierarchy (children and grandchildren of 14); I don't see a problem.

Why exactly should 64 be skipped, but not 24?

Upvotes: 1

Related Questions