Using level number or with a bool flag that toggles on level change.
(node):
if node == null:
throw
q = new
currlevel = 1
q.push(tuple(node, currlevel))
while !q.isempty():
n, level = q.pop()
if level > currlevel:
printline()
currlevel = level
print(n + ", ")
if n.left != null:
q.push(tuple(n.left, level +1))
if n.right != null:
q.push(tuple(n.right, level +1))
(node):
if node == null:
throw
q = new
isodd = true // level 1
q.push(tuple(node, islevelodd: isodd))
while !q.isempty():
n, islevelodd = q.pop()
if islevelodd != isodd:
printline()
isodd = islevelodd
print(n + ", ")
if n.left != null:
q.push(tuple(n.left, !islevelodd))
if n.right != null:
q.push(tuple(n.right, !islevelodd))
Handling each level at a time.
(node):
if node == null:
throw
q = new
level = 1
q.enqueue({node, level})
while !q.isempty():
while !q.isempty() && q.peek().level == level:
n, level = q.dequeue()
print(n + ", ")
if n.left != null:
q.push({n.left, level+1})
if n.right != null:
q.push({n.right, level+1})
print(newline)
level++
Using dummy node to mark end of level.
(node):
if node == null:
throw
// node marks end of level
marker = new node()
q = new
q.push(node)
q.push(marker)
while true:
n = q.pop()
if n == marker:
if q.isEmpty():
break
printline()
q.push(marker)
continue
print(n + ", ")
if n.left != null:
q.push(n.left)
if n.right != null:
q.push(n.right)
No comments:
Post a Comment