2

I want to add Bi-Directional Iterator (like Iterator exported by std::set) in my Parametrized BinaryTree class but I'm unable to comeup with any algorithm.

Simply structure of Binary tree node is , it contains three pointers , left , right , parent:

Node Structure

Stephan Dollberg
  • 32,985
  • 16
  • 81
  • 107
Mr.Anubis
  • 5,132
  • 6
  • 29
  • 44

3 Answers3

5

With the given structure you want to proceed like this:

  1. To start the iteration you would find the left-most node.
  2. To go to the next node the operation depends on where you currently are:
    1. If your node has a right child you go to this child and find its left-most successor (if there is no left child the node you are on is the next node).
    2. If you nodes doesn't have a right child you move up the chain of parents until you find a parent for which you used the link to the left node: the next node becomes this node.
  3. To move in the other direction you reverse the roles of left and right.

Effectively, this is implements a stack-less in-order traversal of the tree. If your tree isn't changed while iterating (an unlikely scenario) or you don't have a link to the parent node, you can maintain the stack explicitly in the iterator.

Dietmar Kühl
  • 150,225
  • 13
  • 225
  • 380
  • 2.2 If you nodes doesn't have a right child you move up the chain of parents **until you find a parent for which you used the link to the left node** << can please explain the bold'ed sentence? Thanks – Mr.Anubis Jan 23 '12 at 16:36
  • 2
    @Mr.Anubis: what I mean is this: from the current node you look at the parent. If the current node is the right child of the parent you make the parent the current node and check its patent. If the current node is the parent's left child, the parent node is where you stop. The best way to see this is with a drawing of a binary tree (hanging strangly upside down): from the right most node in a subtree you need to walk all the way up until there is a node which either has another subtree hanging off its right child or no right child. Of course, eventually there is further node. – Dietmar Kühl Jan 23 '12 at 18:24
1

A good approach to this issue may be to first write your recursive pre-order algorithm, without using templates, and then you can from that create a templated version and implement the correct Iterators.

Just a thought.

Tony The Lion
  • 61,704
  • 67
  • 242
  • 415
0

You can't use recursion to implement an iterator in C++ because your iterator needs to return from all processing before it can return the result.

Only languages like C# and Python, that have a concept of yield can use recursion to create iterators.

Your iterator needs to maintain a stack of yet-to-be-visited nodes.

Of the top of my head, I think the algorithm is something like:

  1. Keep going down and to the left
  2. Every time you come across a right branch, add it to the stack
  3. If at any point you can't go left, pop the first branch off the stack and begin visiting that in the same way.
  • Actually, you don't need to maintain a stack in the iterator if you have a link to the parent node. Also, if you do maintain a stack in the iterator you are preventing changes to the tree structure while iterating. – Dietmar Kühl Jan 22 '12 at 14:24
  • Can you please explain the concept of `yield` also? – Mr.Anubis Jan 22 '12 at 15:28
  • There's an explanation of `yield` here: http://stackoverflow.com/questions/231767/the-python-yield-keyword-explained. –  Jan 22 '12 at 20:34