int Push(SqStack *S,Datatype ch)//进栈(字符栈)
{
? ? Datatype *p;
? ? int select;
? ? if(S->top+1 == S->stacksize)? ? //先判断栈是否已满
? ? {
? ? ? ? printf("栈的容量已满，无法进栈");
? ? ? ? return 0;
? ? }
? ? S->arr[++S->top] = ch;
? ? return 1;
}

int Pop(SqStack *S,Datatype *ch)//出栈（字符栈）
{
? ? if(S->top < 0)
? ? {
? ? ? ? printf("栈为空....\n");
? ? ? ? return 0;
? ? }
? ? *ch = S->arr[S->top];
? ? S->top--;
? ? return 1;
}

int GetTopStack(SqStack S,Datatype *ch) //取字符栈顶
{
? ? if(S.top < 0)
? ? {
? ? ? ? return 0;
? ? }
? ? *ch = S.arr[S.top];
? ? return 1;
}

int EmptyStack(SqStack S) //判断栈空
{
? ? if(S.top < 0)
? ? {
? ? ? ? return 1;
? ? }
? ? return 0;
}

/******************************栈结束*********************************/

void CreateBitree(BiTree *T)? //前序创建二叉树
{
? char ch;
? scanf(" %c",&ch);
? getchar();
? if(ch == '#')
? {
? ? ? *T = NULL;
? }
? else
? {
? ? *T =(BiTree)malloc(sizeof(BiNode));
? ? (*T)->data = ch;
? ? CreateBitree(&((*T)->lchild));
? ? CreateBitree(&((*T)->rchild));
? }
}
? ?

void View(BiTree T)//非递归遍历? 实现不同的遍历顺序修改第一个else语句的结点入栈顺序
{
? ? Datatype temp;
? ? BiTree p;
? ? temp.task = 1;
? ? temp.ptr = T;
? ? SqStack S;
? ? InitStack(&S);
? ? if(T == NULL) return ;
? ? Push(&S,temp);
? ? while(!EmptyStack(S))
? ? {
? ? ? ? Pop(&S,&temp);? ? ? //先把根出栈
? ? ? ? p = temp.ptr;? ? ? ? ? //记录根地址
? ? ? ? if(temp.task == 0)? ? //task为0? 则访问输出
? ? ? ? {
? ? ? ? ? ? printf("%c ",temp.ptr->data);
? ? ? ? }
? ? ? ? else? ? ? ? ? ? ? ? ? ? ? ? //task为1 则将孩子进栈
? ? ? ? {
? ? ? ? ? ? if(p->rchild)? ? ? ? ? ? ? //右孩子进栈
? ? ? ? ? ? {
? ? ? ? ? ? ? ? temp.task = 1;
? ? ? ? ? ? ? ? temp.ptr = p->rchild;
? ? ? ? ? ? ? ? Push(&S,temp);
? ? ? ? ? ? }
? ? ? ? ? ? temp.task = 0;? ? ? ? ? //根的状态由遍历改为访问，然后进栈
? ? ? ? ? ? temp.ptr = p;
? ? ? ? ? ? Push(&S,temp);
? ? ? ? ? ? if(p->lchild)? ? ? ? ? ? ? //左孩子进栈
? ? ? ? ? ? {
? ? ? ? ? ? ? ? temp.ptr = p->lchild;
? ? ? ? ? ? ? ? temp.task = 1;
? ? ? ? ? ? ? ? Push(&S,temp);
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? printf("\n");
}

int main()//二叉树创建：a b d # # e # # c f # # g # #
{
? ? BiTree T;
? ? CreateBitree(&T);
? ? printf("中序遍历为：");
? ? View(T);
? ? return 0;
}

三：层次遍历

　　　　层次遍历需要使用队列

　　　　算法思路比较结单，即对每个结点按左孩子，右孩子的顺序进队列即可，出队列时访问即为层次遍历。

　　　　此处就不赘述算法思路步骤了，直接上代码。

void DispLayer(BiTree T) //层次遍历
{
? ? LinkQueue rear;? ? ? ? ? ? ? ? //装二叉树的结点地址的队列
? ? BiTree view = NULL;
? ? InitQueue(&rear);
? ? if(T == NULL)
? ? {
? ? ? ? return ;
? ? }
? ? EnQueue(&rear,T);? ? ? ? ? ? ? //先将总树根地址装进去
? ? while(!EmptyQueue(rear))? ? //队列为空则遍历完毕
? ? {
? ? ? ? DeQueue(&rear,&view);? ? ? ? ? //小树根出队列
? ? ? ? printf("%c ",view->data);? ? ? ? ? //输出小树根
? ? ? ? if(view->lchild)? ? ? ? ? ? ? ? ? ? ? ? ? //小树根左右孩子存在则入队列
? ? ? ? {
? ? ? ? ? ? EnQueue(&rear,view->lchild);
? ? ? ? }
? ? ? ? if(view->rchild)
? ? ? ? {
? ? ? ? ? ? EnQueue(&rear,view->rchild);
? ? ? ? }
? ? }
? ? printf("\n");
}

以上即为二叉树的各种遍历算法。