0

Given a binary tree such as this:

#include <iostream>

template <typename InfoType>
struct Node
{
    InfoType info;
    Node<InfoType> *left;
    Node<InfoType> *right;
};

template <typename InfoType>
class BinaryTree
{
public:
    bool search(const InfoType& searchItem) const;
    void insert(const InfoType& insertItem);
    void delete(const InfoType& deleteItem);
    void orderedPrint() const;

protected:
    Node<InfoType> *root;

private:
    void orderedPrint(Node<InfoType>* p) const;
};

template <typename InfoType>
void BinaryTree<InfoType>::orderedPrint() const
{
    orderedPrint(root);
}

template <typename InfoType>
void BinaryTree<InfoType>::orderedPrint(Node<InfoType>* p) const
{
    if (p != nullptr)
    {
        orderedPrint(p->left);
        std::cout << p->info << " ";
        orderedPrint(p->right);
    }
}

how do I edit the class so that I can write something like this:

#include <vector>

int main()
{
    std::vector<int> v;
    BinaryTree<int> tree;
    
    for (auto i: tree)
    {
        v.push_back(i);
    }

    return 0;
}

The idea is to be able to iterate through all the contents of a binary tree, similar to iterating through all the elements in a standard container.

Specifically, how do you write the iteration code (e.g., operator++()) given the recursive nature of traversing the nodes?

hermit.crab
  • 852
  • 1
  • 8
  • 20
  • You'll need to add begin() and end() functions: https://stackoverflow.com/questions/7562356/c11-foreach-syntax-and-custom-iterator – CompuChip Oct 15 '20 at 10:42
  • but how do you write the iteration code (`operator++()`) given the recursive nature of traversal? – hermit.crab Oct 15 '20 at 10:44
  • 2
    Either add a "parent" pointer in the nodes, so that the iterator can climb back up, or keep a stack in the iterator itself. – StoryTeller - Unslander Monica Oct 15 '20 at 10:45
  • 1
    "How to write iterator for binary tree" is a different question than "How to make range-based loop work with binary tree". I suggest asking another question where you will ask exactly about iterators. – Yksisarvinen Oct 15 '20 at 10:55

0 Answers0