二叉樹的遍歷中
- 有兩種實現(xiàn)
- 遞歸
- 非遞歸（迭代）
事實上，在解決一些問題的時候，經(jīng)常使用到遞歸函數(shù)饱亿。
萬一哪天為了追求效率，非要寫迭代呢闰靴。
迭代就是：
考慮彪笼，遞歸其實是讓系統(tǒng)來做棧的操作。
所以迭代蚂且，其實配猫，就是我們來做系統(tǒng)本來要做的事情。
系統(tǒng)對于一個函數(shù)入棧會存儲哪些東西杏死？
- 正在操作的數(shù)據(jù)
- PC
- 返回指針
我們需要的是：正在 ** 操作的數(shù)據(jù)泵肄，PC**，記錄當前程序運行到哪個位置淑翼，以確定下一步做什么腐巢。
但是往往，PC 不需要被記錄玄括。
例子
#前序遍歷冯丙，中序遍歷，后續(xù)遍歷
后面會聊下后續(xù)吧
static void swap(int[] array,int i,int mark){
if(i!=mark) {
int tmp = array[i];
array[i] = array[mark];
array[mark] = tmp;
}
}
#快速排序
//常見的快速排序實現(xiàn)
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;
}
}//可以注意到遭京，存儲的就是傳入的操作數(shù)胃惜。
//其他的數(shù)泞莉，在每一輪里面都是由這兩個數(shù)來決定的，所以這里只存儲兩個數(shù)
#不知道還有沒有別的情況船殉，但是至少遍歷和這個都是存儲的鲫趁，遞歸中的
#輸入?yún)?shù)
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呢利虫？
而后序要挨厚。
看了前序，中序糠惫，后序的遞歸函數(shù)疫剃，沒有看出什么差別。
差別就在于stack.pop()之后的操作有幾種寞钥。
前序和中序慌申，pop()之后都是直接打印出來，后面操作只有一種理郑。
{
1.打印出來
}
但是后序蹄溉，pop()的時候，有兩種情況
{
1.node=node.right
2.node打印出來
}
