/*sy32.c*/

　　#include

　　#include

　　typedef char DataType;

　　typedef struct node{

　　DataType data;

　　struct node *lchild,*rchild;

　　}BinTNode;

　　typedef BinTNode *BinTree;

　　int count;

　　void CreateBinTree(BinTree *T);

　　void PreorderN(BinTree T);

　　#define StackSize 10 /*假定预分配的栈空间最多为10*/

　　typedef BinTree SDataType; /*栈的元素类型设为整型*/

　　#define Error printf

　　typedef struct{

　　SDataType data[StackSize];

　　int top;

　　}SeqStack;

　　void InitStack(SeqStack *S) /*初始栈*/

　　{ S->top=-1;

　　}

　　int StackEmpty(SeqStack *S) /*判栈空*/

　　{return S->top==-1;

　　}

　　int StackFull(SeqStack *S) /*判栈满*/

　　{return S->top==StackSize-1;

　　}

　　void Push(SeqStack *S, SDataType x) /*进栈*/

　　{if(StackFull(S))

　　Error("栈已满\n"); /*上溢退出*/

　　else S->data[++S->top]=x; /*栈顶指针加1后将x进栈*/

　　}

　　SDataType Pop(SeqStack *S) /*出栈*/

　　{if (StackEmpty(S))

　　Error("Stack underflow"); /*下溢退出*/

　　else return S->data[S->top--]; /*栈顶指针返回后将栈顶指针减1*/

　　}

　　SDataType StackTop(SeqStack *S) /*取栈顶元素*/

　　{if (StackEmpty(S))

　　Error("栈已空\n");

　　return S->data[S->top];

　　}

　　main()

　　{BinTree T;

　　char ch1,ch2;

　　printf("\n欢迎进入二叉树操作测试程序，请选择：\n");

　　ch1='y';

　　while(ch1=='y' || ch1=='Y')

　　{printf("\nA-------------------------二叉树建立");

　　printf("\nB-------------------------先序遍历(非递归)");

　　printf("\nC-------------------------退出\n");

　　scanf("\n%c",&ch2);

　　switch(ch2)

　　{case 'A':

　　case 'a':printf("按二叉树带空指针的先序次序输入结点:\n");

　　CreateBinTree(&T);

　　printf("二叉树建立成功\n");break;

　　case 'B':

　　case 'b':printf("遍历的结果为:\n");

　　PreorderN(T);break;

　　case 'C':

　　case 'c':ch1='n';break;

　　default:ch1='n';

　　}

　　}

　　}

　　void CreateBinTree(BinTree *T)

　　{char ch;

　　scanf("\n%c",&ch);

　　if (ch=='0') *T=NULL;

　　else {*T=(BinTNode*)malloc(sizeof(BinTNode));

　　(*T)->data=ch;

　　CreateBinTree(&(*T)->lchild);

　　CreateBinTree(&(*T)->rchild);

　　}

　　}

　　void PreorderN(BinTree T)

　　{/*先序遍历二叉树T的非递归算法*/

　　SeqStack *S;

　　BinTree p;

　　InitStack(S);Push(S,T); /*根指针进栈*/

　　while(!StackEmpty(S))

　　{while(p=StackTop(S))

　　{ printf("%3c",p->data); /*访问入栈结点的数据域*/

　　Push(S,p->lchild); /*向左走到尽头*/

　　}

　　p=Pop(S); /*空指针退栈*/

　　if (!StackEmpty(S)) /*输出结点，向右一步*/

　　{p=Pop(S);

　　/* printf("%3c",p->data); */

　　Push(S,p->rchild);

　　}

　　}

　　}/*PreorderN */