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