[This page is auto-generated; please prefer to read the article’s PDF Form.]
All of the three iterative methods which we will write have some common basic structure. In this section, we use method name f() to refer to the recursive method of any of the three traversals. It takes a single argument (node ∗x), which is the root of the tree to traverse.
As said earlier, we will maintain a stack in the iterative methods. Each element of this stack will represent one particular invocation of the recursive method f() with its argument node-pointer x. Since the invocation of f() starts or resumes at the resume-points, we will associate a resume-point to each of these elements. It indicates the point where the invocation will start/resume when it becomes active. So, each element can be represented as (f(x): r), where x is the argument node, and r is the resume-point number, which will be 0 for fresh calls (not resuming). Note that both x and r can vary across the elements of the stack. For convenience, a short notation (x: r) will be used, since the method name is understood as per context. Thus, the stack consists of elements representing invocations of f() at its different execution stages identified by resume-points.
Before we start the iterations in our iterative methods, this stack will be initialized with a single element representing the initial call, i.e. (root : 0), where root is the pointer to root of the tree. In each iteration, we will read the topmost element of the stack, which will be called the “current” element of that iteration. The iteration will perform its execution based on its current element, and this can involve pushing of new elements for the recursive calls, and popping the current element if it is no longer needed (for example, if its execution is complete and has to return). The loop will terminate when there are no more elements on the stack to execute.
Copyright © 2020 Nitin Verma. All rights reserved.