/*syc*/
#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 /*假定预分配的栈空间最多为*/
typedef BinTree SDataType; /*栈的元素类型设为整型*/
#define Error printf
typedef struct{
SDataType data[StackSize];
int top;
}SeqStack;
void InitStack(SeqStack *S) /*初始栈*/
{ S>top=;
}
int StackEmpty(SeqStack *S) /*判栈空*/
{return S>top==;
}
int StackFull(SeqStack *S) /*判栈满*/
{return S>top==StackSize;
}
void Push(SeqStack *S SDataType x) /*进栈*/
{if(StackFull(S))
Error(栈已满\n); /*上溢退出*/
else S>data[++S>top]=x; /*栈顶指针加后将x进栈*/
}
SDataType Pop(SeqStack *S) /*出栈*/
{if (StackEmpty(S))
Error(Stack underflow); /*下溢退出*/
else return S>data[S>top]; /*栈顶指针返回后将栈顶指针减*/
}
SDataType StackTop(SeqStack *S) /*取栈顶元素*/
{if (StackEmpty(S))
Error(栈已空\n);
return S>data[S>top];
}
main()
{BinTree T;
char chch;
printf(\n欢迎进入二叉树操作测试程序请选择\n);
ch=y;
while(ch==y || ch==Y)
{printf(\nA二叉树建立);
printf(\nB先序遍历(非递归));
printf(\nC退出\n);
scanf(\n%c&ch);
switch(ch)
{case A:
case a:printf(按二叉树带空指针的先序次序输入结点:\n);
CreateBinTree(&T);
printf(二叉树建立成功\n);break;
case B:
case b:printf(遍历的结果为:\n);
PreorderN(T);break;
case C:
case c:ch=n;break;
default:ch=n;
}
}
}
void CreateBinTree(BinTree *T)
{char ch;
scanf(\n%c&ch);
if (ch==) *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(ST); /*根指针进栈*/
while(!StackEmpty(S))
{while(p=StackTop(S))
{ printf(%cp>data); /*访问入栈结点的数据域*/
Push(Sp>lchild); /*向左走到尽头*/
}
p=Pop(S); /*空指针退栈*/
if (!StackEmpty(S)) /*输出结点向右一步*/
{p=Pop(S);
/* printf(%cp>data); */
Push(Sp>rchild);
}
}
}/*PreorderN */
