// 1. Preface traversal non-recursive algorithm #define maxSize 100typedef 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 child {Visite ( P-> DATA); PUSH (S, P); P = P-> LCHILD;} // endwhile if (! stackempty (s)) // Realize the right sub-tree traversal to the inline while in the next cycle = POP (s); p = p-> rchild;} // endif} // endwhile} // preorderunRec
// 2. Sub-sequence traversal non-recursion algorithm #define maxSize 100typedef struct {bitree elem [maxsize]; int top;} SQStack; void inorderunrec (bitree t) {sqstack s; stackinit (s); p = t; while ! = 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 knot P = P-> rchild; // Realize the right of the right tree through the next loop} // Endif} // endwhile } // inorderunrec
// 3. Back sequence traversal non-recursive algorithm #define maxsize 100typedef enum {l, r} tagtype; typef 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 sub-tree {x.ptr = P; x.tag = L; / / Mark is a left sub-tree 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 sub-tree access is completed, so access the root node} if (! Stackempty (s)) {S.Elem [s. Top] .tag = r; // Traverse the right child p = s.elem [s.top] .ptr-> rchild;}} while (! stackempty (s));} // PostorderunRec
