数据结构与算法c++实现有序表的查找。用二叉链表作为存储结构，输入键值序列建立一棵二叉排序树，然后中序遍历这棵二叉树。分别用堆排序及快速排序算法，对待排序记录进行排序并输出排序结果代码

以下是使用二叉排序树进行查找的C++代码：

#include<iostream>
using namespace std;

struct BSTNode{
    int data;
    BSTNode* left;
    BSTNode* right;
};

BSTNode* createBST(int arr[], int n){
    BSTNode* root = NULL;
    for(int i = 0; i < n; i++){
        BSTNode* newNode = new BSTNode;
        newNode->data = arr[i];
        newNode->left = NULL;
        newNode->right = NULL;
        if(root == NULL){
            root = newNode;
            continue;
        }
        BSTNode* curNode = root;
        while(true){
            if(newNode->data < curNode->data){
                if(curNode->left == NULL){
                    curNode->left = newNode;
                    break;
                }
                curNode = curNode->left;
            }
            else{
                if(curNode->right == NULL){
                    curNode->right = newNode;
                    break;
                }
                curNode = curNode->right;
            }
        }
    }
    return root;
}

void inOrderTraversal(BSTNode* root){
    if(root == NULL)
        return;
    inOrderTraversal(root->left);
    cout<<root->data<<" ";
    inOrderTraversal(root->right);
}

int main(){
    int arr[] = {12, 6, 18, 2, 9, 15, 21};
    int n = sizeof(arr)/sizeof(arr[0]);
    BSTNode* root = createBST(arr, n);
    inOrderTraversal(root);
    return 0;
}

以下是使用堆排序进行排序的C++代码：

#include<iostream>
using namespace std;

void heapify(int arr[], int n, int i){
    int largest = i;
    int left = 2*i + 1;
    int right = 2*i + 2;
    if(left < n && arr[left] > arr[largest])
        largest = left;
    if(right < n && arr[right] > arr[largest])
        largest = right;
    if(largest != i){
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n){
    for(int i = n/2 - 1; i >= 0; i--)
        heapify(arr, n, i);
    for(int i = n - 1; i >= 0; i--){
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

int main(){
    int arr[] = {12, 6, 18, 2, 9, 15, 21};
    int n = sizeof(arr)/sizeof(arr[0]);
    heapSort(arr, n);
    for(int i = 0; i < n; i++)
        cout<<arr[i]<<" ";
    return 0;
}

以下是使用快速排序进行排序的C++代码：

#include<iostream>
using namespace std;

int partition(int arr[], int low, int high){
    int pivot = arr[high];
    int i = low - 1;
    for(int j = low; j <= high - 1; j++){
        if(arr[j] < pivot){
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i+1], arr[high]);
    return i+1;
}

void quickSort(int arr[], int low, int high){
    if(low < high){
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi-1);
        quickSort(arr, pi+1, high);
    }
}

int main(){
    int arr[] = {12, 6, 18, 2, 9, 15, 21};
    int n = sizeof(arr)/sizeof(arr[0]);
    quickSort(arr, 0, n-1);
    for(int i = 0; i < n; i++)
        cout<<arr[i]<<" ";
    return 0;
}