#!/usr/bin/python2.7
class Node:
"holds left and right values, forming a tree"
def __init__(self, data: int):
"constructor to initiate a node"
# store data
self.data = data
# store reference (next item)
self.left = None
self.right = None
return
def to_string(self) -> str:
"returns the node as a string"
s = ""
s += str(self.data)
if self.left != None or self.right != None:
s += " ["
if self.left != None:
s += self.left.to_string()
else:
s += "null"
s += " "
if self.right != None:
s += self.right.to_string()
else:
s += "null"
s += "]"
return s
# Define an enum
LEFT = 0
MIDDLE = 1
RIGHT = 2
class Iterator:
"the iterator will iterate left, middle, right"
def __init__(self, node: Node):
"constructor to initiate an Iterator"
self.node = node
self.current = None
self.checking = LEFT
self.next_called = False
def next(self) -> bool:
"gets the next item in the iteration"
self.next_called = True
if self.checking == LEFT:
if self.node.left == None:
self.checking = MIDDLE
return True
else:
if self.current == None:
self.current = Iterator(self.node.left)
return True
else:
if self.current.next():
return True
else:
self.current = None
self.checking = MIDDLE
return True
if self.checking == MIDDLE:
self.checking = RIGHT
if self.node.right == None:
return False
self.current = Iterator(self.node.right)
return True
# LEFT and MIDDLE have been checked, we're on the RIGHT now
if self.current == None:
return False
# if we can go next, return true
if self.current.next():
return True
# otherwise, we're done here
self.current = None
return False
def exists(self) -> bool:
"checks if there is a value"
if self.next_called == False:
self.next()
if self.checking == RIGHT or self.checking == LEFT:
if self.current == None:
return False
return True
def get_value(self) -> int:
"gets the value (an integer)"
if self.next_called == False:
self.next()
if self.checking == RIGHT or self.checking == LEFT:
if self.current != None:
return self.current.get_value()
return
return self.node.data
c = Node(4)
c.left = Node(2)
c.left.left = Node(1)
c.left.right = Node(3)
c.right = Node(6)
c.right.left = Node(5)
c.right.right = Node(7)
i = Iterator(c)
while i.exists():
print(i.get_value())
i.next()
print("The value is ", c.to_string())
