快速排序递归算法隐含一棵由关键字生成的二叉树（递归树），输出该隐含二叉树的后序遍历序列

Question

描述：
快速排序递归算法隐含一棵由关键字生成的二叉树（递归树），输出该隐含二叉树的后序遍历序列。（注：划分时以第一关键字为枢轴）
输入说明：
输入数据第一行为1个正整数n，表示关键字个数。第2行为n个整数表示n个关键字。
输出说明：
在一行上输出由关键字隐含的二叉树的后序遍历序列。
输入样例：
9
49 38 65 97 13 27 49 55 4
输出样例：
27 13 38 4 49 55 65 97 49

Answer 1

在快速排序的过程中输出隐含二叉树的后序遍历序列，不用生成二叉树。

```c
#include<stdio.h>
#include<stdlib.h>

int Partition(int L[],int low,int high){
    L[0]=L[low];
    int pivotkey=L[low];
    while(low<high){
        while(low<high&&L[high]>=pivotkey) high--;
        L[low]=L[high];
        while(low<high&&L[low]<=pivotkey) low++;
        L[high]=L[low];
    }
    L[low]=L[0];
    return low;
}
void QSort(int L[],int low,int high){
    if(low<high){
        int pivotloc=Partition(L,low,high);
        QSort(L,low,pivotloc-1);
        QSort(L,pivotloc+1,high);
        printf("%d ",L[pivotloc]);
    }
    else if(low==high){
        printf("%d ",L[low]);
    }
}

int main(void){
    int n;
    scanf("%d",&n);
    int L[100]={0};
    for(int i=1;i<=n;i++) scanf("%d",&L[i]);
    QSort(L,1,n);

    return 0;
}

```