1. Preface traversal non-recursive algorithm
#define maxSize 100
Typedef struct
{
Bitree elem [maxsize];
Int top;
} SQSTACK;
Void PreorderunRec (Bitree T)
{
SQSTACK S;
Stackinit (s);
P = T;
While (p! = null ||! stackempty (s))
{
While (p! = null) // Traverse the left subtree
{
Visite (P-> DATA);
Push (S, P);
P = P-> lchild;
} // endwhile
IF (! stackempty (s)) // Realize the right of the right tree through the next cycle.
{
P = POP (s);
P = P-> rChild;
} // Endif
} // endwhile
} // preorderunRec
2. Secondary traversal non-recursive algorithm
#define maxSize 100
Typedef struct
{
Bitree elem [maxsize];
Int top;
} SQSTACK;
Void inorderunRec (Bitree T)
{
SQSTACK S;
Stackinit (s);
P = T;
While (p! = null ||! stackempty (s))
{
While (p! = null) // Traverse the left subtree
{
Push (S, P);
P = P-> lchild;
} // endwhile
IF (! stackempty (s))
{
P = POP (s);
Visite (P-> DATA); // Access root node
P = P-> rchild; // Realize the right tree traversal through the next loop
} // Endif
} // endwhile
} // inorderunrec
3. Back sequence traversal non-recursive algorithm
#define maxSize 100
Typedef enum {l, r} tagtype;
Typedef struct
{
Bitree PTR;
TagType tag;
} stacknode;
Typedef struct
{
StackNode Elem [MaxSize];
Int top;
} SQSTACK;
Void PostOrderunRec (Bitree T)
{
SQSTACK S;
StackNode X;
Stackinit (s);
P = T;
DO
{
While (p! = null) // Traverse the left subtree
{
x.ptr = p;
x.tag = L; / / Mark as left subtree
PUSH (S, X);
P = P-> lchild;
}
While (! stackempty (s) && s.elem [s.top] .tag == r)
{
X = POP (s);
P = x.ptr;
Visite (P-> DATA); // tag is R, indicating that the right child is accessed, so the root node is accessed.
}
IF (! stackempty (s))
{
S.Elem [S.TOP] .tag = r; // Traversed the right tree
P = S.Elem [S.TOP] .ptr-> rchild;
}
} while (! stackempty (s));
} // PostorderUnRec
