/ *
* CopyRight (C) 2004
* All Rights Reserved.
*
* File Name: PostORDER.C
* File Identification: Sequenis non-recursion traversal binary tree
* Summary: Use the stack simulation to traverse the binary tree
*
* Current version: 1.0
* Author: yu
* Completion date: August 8, 2004
*
* Replacement version: 1.0
* Original author: yu
* Completion date: August 8, 2004
* /
#include
#include
#define stack_init_size 100 / / The number of spatial numbers initially assigned
#define stackincream 10 / / The number of spaces in the stack space increase
Typedef char datatype; // binary tree node information type
Typedef struct bitnode // binary nodes type
{
Struct Bitnode * LCHILD, * RCHILD;
DataType Data;
} Bitnode;
TYPEDEF ENUM {L, R} tagType; // tag is L indicates the left subtree of the node, and the tag is R indicating the right tree of the node.
Typedef struct stacknode // stack node type
{
BitNode * ptr; // Mark the pointer to record the pointing node
tagType tag; // Used to mark the LR value of each node
} stacknode;
Typedef struct stack // stack type
{
StackNode * base;
StackNode * TOP;
Int stacksize;
} SQSTACK;
SQSTACK * INITSTACK () //
{
Sqstack * S;
IF (! (s = (SQSTACK *) Malloc (Sizeof (Sqstack)))) EXIT (-1);
S-> base = (stacknode *) malloc (stack_init_size * sizeof (stacknode)); // Initialized to assign STACK_INIT_SIZE ELEMTYPE Type Space
IF (! S-> Base) // Assign space failed
{
EXIT (-2);
Printf ("Stack Space Allocation Failed! / N");
}
IF (S-> Base) // Assignment Space
Printf ("Successful Stack Space Allocation! / N");
S-> TOP = S-> Base; // Initialization stack head pointer
S-> stacksize = stack_init_size;
Return S;
}
Void Push (SQSTACK * S, StackNode E) // Press
{
IF (S-> TOP-S-> Base> = S-> stacksize) // Stack full
{
S-> Base = (stacknode *) Realloc (S-> Base, (S-> stacksize stackincream) * sizeof (stacknode)); // Stack over time increases space
IF (! S-> Base) // increase allocation space failure
EXIT (-2);
S-> stacksize = stackincream;
}
* (S-> TOP) = E;
S-> TOP ;
}
StackNode POP1 (SQSTACK * S) // Out of the stack 1, the returned E is a stack top element is an address
{
StackNode E;
IF (S-> TOP == S-> Base) exit (-1); / / Stack Empty Return
S-> TOP -;
E = * (S-> TOP); RETURN E;
}
INT stackempty (sqstack * s) // Judging the stack empty, the stack returns 1, otherwise returns 0
{
IF (S-> Base == S-> TOP) Return 1;
Else Return 0;
}
StackNode getop (Sqstack * S) // gets the top elements of the stack
{
IF (S-> TOP == S-> Base) exit (-1);
Return * (S-> TOP-1);
}
BitNode * createbitree () // Preface to recreate the tree
{
Char x;
BitNode * T;
Scanf ("% C", & x);
IF (x == ') t = NULL;
Else
{
IF (! (t = (bitnode *) malloc (sizeof (bitnode)))))))
T-> Data = X; // Establish a node
T-> LCHILD = Createbitree (); // built a left subtree
T-> rchild = cretebitree (); // Building a right child
}
Return T;
}
Void PostRerder (BitNode * T)
{
Sqstack * S;
BitNode * P;
StackNode X;
P = T;
s = initstack ();
While (p ||! stackempty (s))
{
While (p) // Traverse the left subtree
{
x.ptr = p;
X.TAG = L;
PUSH (S, X);
P = P-> lchild;
}
While (! stackempty (s) && (* (S-> TOP-1)). tag == r) // Determine if the tag is R. Because if r, it means that it is returned from the right tree.
{
X = POP1 (s);
P = x.ptr;
Printf ("% c", p-> data); // tag is R, indicating that the right child is accessed, so the root node is accessed.
}
IF (! stackempty (s))
{
(* (S-> TOP-1)). Tag = r; // Return from the left subtree, traverse the right tree
p = (getop (s) .ptr) -> rchild;
}
}
}
void main ()
{
BitNode * T;
T = CreateBitree ();
PostORDER (T);
}
