tree.hh icon indicating copy to clipboard operation
tree.hh copied to clipboard

Breadth-first iterators do not work on multiple heads tree.

Open rdebroiz opened this issue 3 years ago • 1 comments

The doc says that for the tree:

root
  |
  +----A
  |    |
  |    +---B
  |    | 
  |    +---C
  |
  +----D
       |
	   +---E
	   |
	   +---F

The resulting order in which nodes are visited using breadth_first_iterator is: root A D B C E F. But it's A B C

    tree<char> t;
    auto r = t.insert(t.begin(), 'A');
    auto it = t.append_child(r, 'B');
    it = t.insert_after(it, 'C');

    it = t.insert_after(r, 'D');
    it = t.append_child(it, 'E');
    it = t.insert_after(it, 'F');

    auto bfit = t.begin_breadth_first();
    cout << "breadthfirst from root: ";
    while(t.is_valid(bfit)) {
        cout << *bfit << " ";
        ++bfit;
    }
    cout << endl;

    tree<char>::sibling_iterator siit = t.begin();
    cout << "siblings from root: ";
    while(t.is_valid(siit)) {
        cout << *siit << " ";
        ++siit;
    }
    cout << endl;

output:

breadthfirst from root: A B C   // Not OK
siblings from root: A D         // OK

rdebroiz avatar Mar 03 '21 06:03 rdebroiz

It does work if the tree as a single head.

rdebroiz avatar Mar 03 '21 07:03 rdebroiz