/* ----------------------------------------------------------- */
#include <stdio.h>
typedef struct node {
char value;
struct node *left_child;
struct node *right_child;
} Node;
void prt_tree_prefix_order(Node *tree);
void prt_tree_infix_order(Node *tree);
void prt_tree_postfix_order(Node *tree);
void push(Node *value);
Node *pop(void);
/* ----------------------------------------------------------- */
main()
{
static Node tree[] = {
{'*', &tree[1], &tree[2]}, /* [0] */
{'+', &tree[3], &tree[4]}, /* [1] */
{'-', &tree[5], &tree[6]}, /* [2] */
{'A', NULL, NULL}, /* [3] */
{'B', NULL, NULL}, /* [4] */
{'C', NULL, NULL}, /* [5] */
{'/', &tree[7], &tree[8]}, /* [6] */
{'D', NULL, NULL}, /* [7] */
{'E', NULL, NULL} /* [8] */
};
prt_tree_prefix_order(tree);
prt_tree_infix_order(tree);
prt_tree_postfix_order(tree);
return 0;
}
/* --------------------------------------------------------------
PRT_TREE_PREFIX_ORDER: The steps to traverse a binary tree in
prefix order and to display the value of each node are:
A. Initialize a pointer to the root of the tree.
B. Push a null sentinel on the stack.
C. Process the whole tree (until you run into the null sentinel
placed on the stack in Step B. Do this by going down
the left branch as far as possible, then down the right
branch until you come to another left branch.
D. Display node's value.
E. If the current node has a right branch push the pointer to
that branch on the stack.
F. If the current node has a left branch follow that branch.
G. If the current node is a leaf (terminal) node or has no
left branch, pop a saved (right branch) value back off the
stack and start traversing the subtree to the right.
-------------------------------------------------------------- */
void prt_tree_prefix_order(Node *tree)
{
/*A*/ const Node *ptr = tree;
/*B*/ push(NULL);
/*C*/ while (ptr != NULL) {
/*D*/ printf("%c", ptr->value);
/*E*/ if (ptr->right_child != NULL) {
push(ptr->right_child);
}
/*F*/ if (ptr->left_child != NULL) {
ptr = ptr->left_child;
}
/*G*/ else {
ptr = pop();
}
}
putchar('\n');
}
/* --------------------------------------------------------------
PRT_TREE_INFIX_ORDER: The steps to traverse a binary tree in
infix order and to display the value of each node are:
A. Initialize a pointer to the root of the tree.
B. Push a null sentinel on the stack.
C. Push the whole left subtree on the stack.
D. Start backtracking by popping off last node pushed.
E. Backtrack until you run into the sentinel placed on the stack
in Step B.
F. Display node's value.
G. If the current node has a right branch follow that branch
and go to Step C.
H. Pop the next node off stack.
-------------------------------------------------------------- */
void prt_tree_infix_order(Node *tree)
{
/*A*/ Node *ptr = tree;
/*B*/ push(NULL);
/*C*/
loop: while (ptr != NULL) {
push(ptr);
ptr = ptr->left_child;
}
/*D*/ ptr = pop();
/*E*/ while (ptr != NULL) {
/*F*/ printf("%c", ptr->value);
/*G*/ if (ptr->right_child != NULL) {
ptr = ptr->right_child;
goto loop;
}
/*H*/ ptr = pop();
}
putchar('\n');
}
/* --------------------------------------------------------------
PRT_TREE_POSTFIX_ORDER: The steps to traverse a binary tree in
postfix order and to display the value of each node are:
A. Initialize a pointer to the root of the tree.
B. Push a null sentinel on the stack.
C. Push the whole left subtree on the stack.
D. Push current node pointer on stack.
E. If the current node has a right branch push the pointer to
that branch on the stack and also push a special marker.
This is achieved by allocating a dummy variable 'marker' so
we can use its address as a unique special pointer.
F. Follow the left branch.
G. Pop a pointer off stack.
H. Display node's value and keep popping off the stack until
you either run into the null sentinel (end of stack) or
the special marker.
I. If you found a special marker, pop the associated pointer
and go to Step C. Otherwise, you must have reached the
null sentinel so you are done.
-------------------------------------------------------------- */
void prt_tree_postfix_order(Node *tree)
{
/*A*/ Node *ptr = tree;
Node marker;
/*B*/ push(NULL);
/*C*/
loop: while (ptr != NULL) {
/*D*/ push(ptr);
/*E*/ if (ptr->right_child != NULL) {
push(ptr->right_child);
push(&marker);
}
/*F*/ ptr = ptr->left_child;
}
/*G*/ ptr = pop();
/*H*/ while (ptr != NULL && ptr != &marker) {
printf("%c", ptr->value);
ptr = pop();
}
/*I*/ if (ptr == &marker) {
ptr = pop();
goto loop;
}
putchar('\n');
}
/* ----------------------------------------------------------- */
#define STACK_SIZE 30
static Node *stack[STACK_SIZE];
static size_t stack_ptr = 0;
void push(Node *value)
{
if (stack_ptr == STACK_SIZE)
printf("Stack is full\n");
else
stack[stack_ptr++] = value;
}
Node *pop(void)
{
if (stack_ptr == 0) {
printf("Stack is empty\n");
return 0;
}
return stack[--stack_ptr];
}
/* ------------------------------------------------------------*/
/* End of File */