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");
}
以上即为二叉树的各种遍历算法。