二叉树的遍历中
- 有两种实现
- 递归
- 非递归（迭代）
事实上，在解决一些问题的时候，经常使用到递归函数。
万一哪天为了追求效率，非要写迭代呢。
迭代就是：
考虑，递归其实是让系统来做栈的操作。
所以迭代，其实，就是我们来做系统本来要做的事情。
系统对于一个函数入栈会存储哪些东西？
- 正在操作的数据
- PC
- 返回指针
我们需要的是：正在 ** 操作的数据，PC**，记录当前程序运行到哪个位置，以确定下一步做什么。
但是往往，PC 不需要被记录。
例子
#前序遍历，中序遍历，后续遍历
后面会聊下后续吧
static void swap(int[] array,int i,int mark){
if(i!=mark) {
int tmp = array[i];
array[i] = array[mark];
array[mark] = tmp;
}
}
#快速排序
//常见的快速排序实现
static void quick_sort(int array[],int start,int end){
if(end<=start){return;}
int middle = array[start];
int mark =start;
for(int i=start+1;i< end+1;i++){
if(array[i] < middle){
swap(array,i,mark+1);
mark++;
}
}
swap(array,start,mark);
quick_sort(array,start,mark-1);
quick_sort(array,mark+1,end);
}
#一个非递归的快速排序
static class QS{
int start,end;
int pc;
QS(int start,int end){
this.start=start;
this.end = end;
}
}//可以注意到，存储的就是传入的操作数。
//其他的数，在每一轮里面都是由这两个数来决定的，所以这里只存储两个数
#不知道还有没有别的情况，但是至少遍历和这个都是存储的，递归中的
#输入参数
static void qs2(int array[]){
Stack<QS> stack =new Stack<QS>();
QS node = new QS(0,array.length-1);
while(!stack.isEmpty()|| node!=null){
while(node.end<=node.start){
if(!stack.isEmpty())
node=stack.pop();
else{
return;
}
}
int middle = array[node.start];
int mark = node.start;
for(int i=node.start + 1;i< node.end + 1;i++){
if(array[i] < middle){
swap(array,i,mark + 1);
mark ++;
}
}
swap(array,node.start,mark);
stack.push(new QS(mark+1,node.end));
node = new QS(node.start,mark-1);
}
}
#关于非递归的后序遍历
伪代码：
void post(Node node){
post(node.left);
post(node.right);
node.print();
}
void postTravel(Node node){
while(node!=null){
Stack.push(node);
node =node.left;
}
node.pop();
if(pc==1){//压入的位置
node.Sprint
}else{
node.push(node);
node=node.right;
}
}
什么时候要用PC
为什么前序和中序遍历，不需要用PC呢？
而后序要。
看了前序，中序，后序的递归函数，没有看出什么差别。
差别就在于stack.pop()之后的操作有几种。
前序和中序，pop()之后都是直接打印出来，后面操作只有一种。
{
1.打印出来
}
但是后序，pop()的时候，有两种情况
{
1.node=node.right
2.node打印出来
}
