Treat a null reference as the empty binary tree and perform the visit before descending:By structural induction, the empty binary tree produces the empty output. A nonempty binary tree prints its root label, then the complete preorder traversal of the left subtree, then that of the right subtree. These are exactly the required output positions. The recursion terminates on a finite binary tree because each recursive call has strictly fewer vertices. For the three-node example, the output order is . The time complexity is linear in the number of vertices, with call stack depth bounded by the height of a binary tree plus a constant.
def preorderRecursive(t: Tree): Unit = {
if (t != null) {
println(t.datum)
preorderRecursive(t.left)
preorderRecursive(t.right)
}
}Store the bottom of the stack at index zero and the top at the last occupied index:The representation invariant is that
class Stack {
private val MAX = 1000
private val data = new Array[Tree](MAX)
private var used = 0
// Pre: used < MAX.
def push(t: Tree): Unit = {
require(used < MAX, "Stack full")
data(used) = t
used += 1
}
// Pre: used > 0.
def pop: Tree = {
require(used > 0, "Stack empty")
used -= 1
val result = data(used)
data(used) = null
result
}
// Pre: true.
def isEmpty: Boolean = used == 0
}data.length==MAX, , and unused slots from used onwards contain null references. Occupied slots contain the stored Tree references; the stack itself need not forbid null values. The abstraction function, written with the first sequence element at the top, isInitially this is the empty sequence. push prepends its argument, pop removes and returns the first abstract element, and isEmpty reports whether the abstract sequence is empty. These postconditions follow directly from the index changes. Clearing a popped slot avoids retaining an otherwise unused tree reference. All three operations take time. No loops are needed.Push the right child before the left child so that the LIFO stack exposes the left child first:Let be the sequence of labels in the preorder traversal of . If the abstract pending stack, top first, is , the loop invariant is that the output already printed, followed by , is the required full output. Each pending root is non-null, and its subtree is still unvisited. This is the pending-work form of explicit-stack depth-first tree traversal.
def preorderIterative(t: Tree): Unit = {
val pending = new Stack
if (t != null) pending.push(t)
while (!pending.isEmpty) {
val u = pending.pop
println(u.datum)
if (u.right != null) pending.push(u.right)
if (u.left != null) pending.push(u.left)
}
}One iteration discharges the first root's own label and replaces its remaining obligation by the left subtree followed by the right subtree. The push order makes that precisely the new top-first pending order. Thus the loop invariant is preserved. The loop variant is the sum of the numbers of vertices in all pending subtrees; it decreases by exactly one per iteration, even if the number of stack entries increases. When the stack is empty there is no remaining output obligation, proving correctness and termination. This assumes a finite genuine binary tree and, as permitted, sufficient stack capacity. Each vertex is pushed and popped once, giving time and pending references for binary tree height .
Articles by others on the same topic
There are currently no matching articles.