Binary word trees
All other answers are technical discussions of how to implement an iterator over a tree structure. However, as far as I understand your question, you seem to be having difficulty understanding the mechanics of the tree traversal concept, not just for implementation. In other words, you are not "traversing" the tree traversal. What will probably help the most is getting a good pseudocode algorithm to walk through a binary tree, pencil, sheet of paper and work out an example. Create a simple binary tree and then traverse it mechanically following pseudocode. You should probably use the second sheet of paper to write the stack . That is, the state of each function that is in the middle of a call, because it is waiting for a subfunction to return.
Keep in mind that while you are doing this, the tree is a very elegant structure. It may seem rather complicated, but in every node it is simple. To perform an operation on all elements of a tree, you simply perform that operation on the root of the tree, and then perform the actual operation call on each child of that root, which are themselves the roots of subtrees. Having worked out an example will go a long way in getting your mind to understand and accept recursion. Don't be embarrassed if this is difficult for you. The recursion is strange. It's a tricky concept at first, but you need to understand and work with trees.
Here is an example tree (ASCII art) you can use to launch:
F
/ \
/ \
DH
/ \ / \
BEGI
/ \
AC
And a simple pseudocode algorithm that you can use to spell all letters in the correct workaround.
procedure traverse (node)
if node is not null:
traverse (node.left)
write node.letter
traverse (node.right)
else:
do nothing
You can even start with simpler trees. What if the tree only consisted of nodes D, F, and H? What if it's just F? Zero? Try these simple examples and work with a large tree. By the time you figure out how to do this consistently and correctly, you will not only have a good idea of what is going on in the iterator implementation, you will have a much better estimate of the cardinality of recursion.
a source to share
What do you mean by "Iterator"? If you just need to iterate through the tree, you can do it recursively: http://en.wikipedia.org/wiki/Tree_traversal#Sample_implementations
If you need to provide an IEnumerator interface like in C # or Java, or want to save stack space, use this: http://en.wikipedia.org/wiki/Tree_traversal#Queue-based_level_order_traversal You can use output in C # or easily convert the while loop to the GetNext method required by the iterator.
a source to share
There are two main ways to iterate through the tree. I have posted some examples of Python code on how to do this on Iterating through the tree .
a source to share
In a binary tree, each node will store some value and have 2 children, for example left and right. Now, one way to traverse the tree is to start at the top, traverse the left child, look at that node value, and then traverse the right child.
Where moving the child means (recursively): 1) moving the left child 2) looking at the node value 3) moving the right child
This is the first depth traversal, so for each node you use 'or' see 'the value of that left child, followed by the value of the current node and the last value of the right child.
On the first pass of the width, you start at root, look at the node's value, and then push the children (if any) to the queue on it. Then loop while there is a node in the queue, get the node from the front of the queue and repeat: look at this value if it has children, then push them at the end of the queue.
An example in python:
#!/usr/bin/env python
class Node:
def __init__(self, val = 0):
self.value = val
self.left = None
self.right = None
def __str__(self):
return "%d" % (self.value)
def dfs(node = None):
if node is None: return
dfs(node.left)
print node
dfs(node.right)
def bfs(root = None):
if root is None: return
nodes = []
nodes.append(root)
while len(nodes):
current = nodes[0]
print current
nodes.remove(current)
if current.left is not None:
nodes.append(current.left)
if current.right is not None:
nodes.append(current.right)
def main():
root = Node(0)
root.left = Node(10)
root.right = Node(20)
l = root.left
l.left = Node(100)
l.right = Node(101)
r = root.right
r.left = Node(200)
r.right = Node(201)
dfs(root)
bfs(root)
if __name__ == '__main__':
main()
# example tree constructed:
# 0
# 10 20
# 100 101 200 201
# dfs (depth first) traversal:
# 100
# 10
# 101
# 0
# 200
# 20
# 201
# bfs (breadth first) traversal:
# 0
# 10
# 20
# 100
# 101
# 200
# 201
a source to share
I had the same problem in my Data Structures class.
My solution is pretty simple.
Traverse the tree recursively, but store every node you visit in a different collection and then iterate over that new collection. Thus, there is nothing difficult about writing an iterator at all.
I personally chose to use a stack, but you could do it with a simple array or even a linked list (which you said you already have experience with).
a source to share