2024.10.27 直接插入排序 非递归后序遍历(复杂版)
直接插入排序
思路:用temp变量存放需要插入前面有序序列的变量,然后用里面的那个for循环寻找到需要插入的位置。
额外注意的点:arr[j+1]=temp;这个是因为内置循环每次出来之后所指向的位置是我们要插入的位置的前一个(-1或者插入的位置-1)
#include <stdio.h>
int main(){
int arr[10] = {9,8,7,6,5,4,3,2,1,0};
int i,j,temp;
for(i=0;i+1<10;i++){
if(arr[i]>arr[i+1]){
temp = arr[i+1];
for(j=i;j>=0&&arr[j]>temp;j--){
arr[j+1] = arr[j];
}
arr[j+1]=temp; //这里需要额外注意
}
}
for(int i=0;i<10;i++)
printf("%d",arr[i]);
return 0;
}
非递归后序遍历
算法思想:和先序遍历和中序遍历的区别是:需要额外设置一个遍历指针的r(指向遍历节点指针p之前指向的节点)
需要注意的点:
我们需要注意的点就是访问右边节点的时候,需要区分是从根节点到右节点还是从右节点到根节点,如果是从根节点到右节点那么我们需要进行的操作是入栈右节点,如果是从右节点到根节点的话,那么我们需要进行的操作是对根节点进行出栈,打印并更新指针r指向指针p,并将p置空。