元素e为Q的新的队尾元素 {
if(((*Q).rear+1)%MAXQSIZE==(*Q).front) return ERROR;
(*Q).base[(*Q).rear]=e;
(*Q).rear=((*Q).rear+1)%MAXQSIZE; return OK; }
int DeQueue(SqQueue *Q,QElemType *e)//删除Q的队头元素,用e返回其值 {
if((*Q).front==(*Q).rear) return ERROR; *e=(*Q).base[(*Q).front];
(*Q).front=((*Q).front+1)%MAXQSIZE; return OK; }
int CreateBiTree(BiTree &T)//按先序次序输入二叉中树结点的值，#表示空树构造 {
char ch;
scanf(\ if(ch=='#')T=NULL; else {
if(!(T=(BiTree)malloc(sizeof(BiTNode))))exit(OVERFLOW); T->data=ch;
CreateBiTree(T->lChild); CreateBiTree(T->rChild); }
return OK; }
void PreOrderTraverse(BiTree T)//先序遍历二叉树的递归算法 { if(T) {
printf(\
PreOrderTraverse(T->lChild); PreOrderTraverse(T->rChild);
} }
void InOrderTraverse(BiTree T)//中序遍历二叉树的递归算法 { if(T) {
InOrderTraverse(T->lChild); printf(\ InOrderTraverse(T->rChild); } }
void PostOrderTraverse(BiTree T)//后序遍历二叉树的递归算法 { if(T) {
PostOrderTraverse(T->lChild); PostOrderTraverse(T->rChild); printf(\
} }
void inorder(BiTree T)//中序非递归遍历二叉树 { SqStack S; InitStack(&S); BiTree p=T;
while(p||!StackEmpty(&S)) { if(p) {
Push(&S,*p); p=p->lChild; } else {
p=(BiTNode *)malloc(sizeof(BiTNode)); *p=Pop(&S);
printf(\ p=p->rChild; } }
}
int main()//主函数分别实现建立并输出先、中、后序遍历二叉树 {
BiTree T;
printf(\按先序输入二叉树中结点的值，#表示空结点:\\n\ CreateBiTree(T);
printf(\先序递归遍历二叉树:\ PreOrderTraverse(T);
printf(\中序递归遍历二叉树:\ InOrderTraverse(T);
printf(\后序递归遍历二叉树:\ PostOrderTraverse(T);
printf(\中序非递归遍历二叉树：\\n\ inorder(T); printf(\ system(\ return 0; }
数据结构-二叉树的遍历(北华大学吕磊)
