//非递归方式建树，并按任一种非递归遍历次序输出二叉树中的所有结点；
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define MaxSize 50
typedef char ElemType;
typedef struct TNode{
     ElemType data;
     struct TNode *lchild,*rchild;
     }BTree;
//------------------------------------------------------------------------------

ElemType str[]="A(B(C(D,E(F,G(,H))),I(J,K(L))),M)";
//------------------------------------------------------------------------------

void CreateBTree(BTree **T,ElemType *Str);  //非递归建树；
void TraverseBTree(BTree *T);     //选择非递归算法的遍历方式;
void PreOrderUnrec(BTree *T);           //先序遍历非递归算法;
void InOrderUnrec(BTree *T);            //中序遍历非递归算法;
void PostOrderUnrec(BTree *T);         //后序遍历非递归算法;
void LevelOrderUnrec(BTree *T);        //层次遍历非递归算法;
//------------------------------------------------------------------------------
int main(void)
{
 BTree *T = NULL; printf("\n二叉树的广义表格式为：\n\t"); puts(str);
 CreateBTree(&T,str);
 TraverseBTree(T);
 system("pause"); return 0;
}
//------------------------------------------------------------------------------
void CreateBTree(BTree **T,ElemType *Str)
{           //按二叉树广义表建立对应的二叉树存储结构;
 BTree *p = NULL,*Stack[MaxSize];//数组为存储树根结点指针的栈,p为指向树结点的指针;
 int top = -1;     //top为Stack栈的栈顶指针;
 char flag;      //flag为处理结点的左子树(L)和右子树(R)的标记;
 *T = NULL;
 while(*Str)
 {
  if    (*Str == '(') {Stack[++top] = p;flag = 'L';}  //入栈;
  else if(*Str == ')') --top;                                //出栈;
  else if(*Str == ',') flag = 'R';
  else
  {
      if(!(p = (BTree *)malloc(sizeof(BTree))))  exit (1);
      p->data = *Str;
      p->lchild = p->rchild = NULL;      //初始化新结点;
      if(*T == NULL) *T = p;              //根结点;
      else
      {
        if(flag == 'L') Stack[top]->lchild = p;
        if(flag == 'R') Stack[top]->rchild = p;
      }
  }
  ++Str;
 }
}
//------------------------------------------------------------------------------
void TraverseBTree(BTree *T)        //选择非递归算法的遍历方式;
{
 int mark;
 printf("\n非递归算法遍历方式：\n\t1 --- 前序遍历\n\t2 --- 中序遍历");
  printf("\n\t3 --- 后序遍历\n\t4 --- 按层遍历\n\tq ---  退 出\n请选择：\n");
 if(T == NULL) printf("该树为空！\n");
 while(T != NULL && scanf("%d",&mark)==1)
 {
     if(mark==1)    {printf("先序遍历:\t");PreOrderUnrec(T);}
     else if(mark==2) {printf("中序遍历:\t");InOrderUnrec(T);}
     else if(mark==3) {printf("后序遍历:\t");PostOrderUnrec(T);}
     e