对二叉树进行先序、中序和后序遍历都是从根结点开始的,且在遍历过程中经过结点的路线是一样的,只是访问的时机不同而已。
先序遍历是在深入时遇到结点就访问,中序遍历是在从左子树返回时遇到结点访问,后序遍历是在从右子树返回时遇到结点访问。
非递归遍历实现的大概模板:
void xxxorder(bintree T)
{
sqstack stack;//定义一个栈,并初始化栈
initstack(stack);
定义一个局部临时变量p存放根节点 p=T;
while(p||!stackempty())//判断条件 是节点非空或者栈非空
{
if(p)//节点非空的话,进入入栈操作后
再转移到左子树判断
{
push();
p=p->lchild;
}
else { //节点为空则进行出栈操作,然后再转移到右子树判断
p=pop();
p=p->rchild;
}
}
}
快速排序的 模板:
void quicksort(elemtype A[],int low,int high)//快速排序的三个接口
{
int i=low,j=high;
elemtype x=A[low];//定义哨兵
if(low<high)
{
while(i<j) //确定x的最终位置
{
while(i<j&&A[j]>x) j--;
if(i<j)
{ A[i]=A[j];i++;}
while(i<j&&A[i]<x) i++;
if(i<j)
{ A[j]=A[i];j--;}
}
A[i]=x;
quicksort(A,low,i-1);//进行递归调用
quicksort(A,i+1,high);
}
}