非递归前序,中序,后序遍历二叉树(优化算法).txt

非递归前序,中序,后序遍历二叉树(优化算法)

#include <stdio.h>
>  #include <alloc.h>
>  typedef struct mybitree  {
>   char data;
>   struct mybitree *left, *right;
>  } bitree;
>  bitree e = {'e', NULL, NULL};
>  bitree f = {'f', NULL, NULL};
>  bitree d = {'d', &e, &f};
>  bitree c = {'c', NULL, NULL};
>  bitree b = {'b', &c, NULL};
>  bitree root = {'a', &d, &b};
>  typedef struct myelement {
>   char   problem;
>   bitree *data;
>   struct myelement *next;
>  } element;
>  element *stack;
>  void push(bitree *data) {
>   element *elem = (element *)malloc(sizeof(element));
>   elem->data = data;
>   elem->next = stack;
>   stack = elem;
>  }
>  void pop() {
>   element *next = stack;
>   stack = stack->next;
>   free(next);
>  }
>  void printPreOrder(bitree *tree) {
>   bitree *current = tree;
>   if(current == NULL)
>    return;
>   do {
>    printf("%c ", current->data);
>    if(current->left == NULL)
>     if(current->right == NULL)
>      if(stack == NULL)
>       break;
>      else {
>       current= stack->data;
>       pop();
>      }
>     else
>      current = current->right;
>    else {
>     if(current->right != NULL)
>      push(current->right);
>     current = current->left;
>    }
>   } while(1);
>  }
>  void printInOrder(bitree *tree) {
>   if(tree==NULL)
>    return;
>   do {
>    if(tree->right != NULL)   {
>     push(tree->right);
>     stack->problem = 'F';  /*** Full problem **/
>    }
>    push(tree);
>    stack->problem = 'H';   /***** Half problem ****/
>    if(tree->left == NULL) {
>     while(stack != NULL && stack->problem=='H') {
>      printf("%c ", stack->data->data);
>      pop();
>     }
>     if(stack == NULL)
>      break;
>     else {
>      tree = stack->data;
>      pop();
>     }
>    } else
>     tree = tree->left;
>   } while(1);
>  }
>  void printPostOrder(bitree *tree) {
>   if(tree==NULL)
>    return;
>   do {
>    push(tree);
>    stack->problem = 'H';   /***** Half problem ****/
>    if(tree->right != NULL)   {
>     push(tree->right);
>     stack->problem = 'F';  /*** Full problem **/
>    }
>    if(tree->left == NULL) {
>     while(stack != NULL && stack->problem=='H') {
>      printf("%c ", stack->data->data);
>      pop();
>     }
>     if(stack == NULL)
>      break;
>     else {
>      tree = stack->data;
>      pop();
>     }
>    } else
>     tree = tree->left;
>   } while(1);
>  }
>  void main() {
>   printf("

		");
>   printPreOrder(&root);
>   printf("

		");
>   printInOrder(&root);
>   printf("

		");
>   printPostOrder(&root);
>  }