Creating a tree datastructure - different approach

Question

In the passed I've asked many questions about tree datastructures, but it seems I didn't take it to the correct manner in C++.

In the way I wrote the datastructure I couldn't think of a single manner on how to have an "end" or "begin" iterator. As such I've gone to the approach to include all functionality as member methods. Instead of using the standard approach of iterators & algorithms.

Now the goal with my tree structure is to have: 1) as fast as possible moving a branch from 1 tree to another. 2) each branch should be a tree on it's own. And actions working on the tree should also be capable to be executed on the branch.

What I have done is simply create a class, which contains a vector. - Inside the vector are other objects of this class. Example (I'm only posting a minimal example here, as the biggest problem I face now is that the class is simply too large to handle):

template <typename ValTy>
class Tree {
private:
    std::vector<std::unique_ptr<Tree> > subtrees;
    ValTy value;
};

As you can see with this I can just take something out of subtrees - and use it either as a tree or copy it around. However as the top level tree has no indication about how many sub trees (or how many levels) there are, it's impossible to state an "end iterator"? And as such algorithms like std::find() won't iterate over the whole tree (and all it's subtrees)?

Is it possible to make use of these algorithms possible, while still mainting the structure of easy "branching"?

Answer 1

You can iterate over such a tree by keeping a stack of pairs of iterators of the subtrees vectors. An increment on such a vector means an increment on the top-most subtree iterator, followed by a cleanup if the bottom-most iterator is at its end.

The end() iterator for this vector would simply be the empty stack.

Answer 2

As you can see with this I can just take something out of subtrees - and use it either as a tree or copy it around. However as the top level tree has no indication about how many sub trees (or how many levels) there are, it's impossible to state an "end iterator"? And as such algorithms like std::find() won't iterate over the whole tree (and all it's subtrees)?

Well the problem here is more of a conceptual problem.

I always solve CRUD functionality within tree structures with recursion. Recursion doesn't require knowledge of number of subtrees, and this is one of the things which enables O(log n) insert, find and delete.

Insertion example:

 void insertNode(Node* &treeNode, Node *newNode) {
     if (treeNode) treeNode = newNode;
     else if (newNode->key < treeNode->key) insertNode(treeNode->left, newNode);
     else insertNode(treeNode->right, newNode);
 }

If you need to know how many levels are on the tree just go left child until NULL. You can easily work out O(log n) algorithms for counting number of children in tree using this knowledge.

---

Trees are designed for recursive access. If you want non-recursive access, maybe trees aren't what you're looking for? - What data will this structure hold, at what access frequency?