c＋＋二叉树的快速排序代码

在 C++ 中，快速排序是一种常见的排序算法，但它通常用于数组而不是二叉树。然而，如果你想对二叉搜索树（BST）进行排序，你可以先将它转换为有序的序列，然后再进行排序。这里是一个简单的示例，展示如何通过递归实现对整个二叉树的中序遍历来达到排序的效果：

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* left;
    Node* right;
};

// 交换两个节点值
void swap(Node*& a, Node*& b) {
    int temp = a->val;
    a->val = b->val;
    b->val = temp;
}

// 通用的递归快速排序函数
void quickSort(Node* root, Node** smaller, Node** greater) {
    if (root == nullptr)
        return;

    // 如果左子树为空，当前节点就是中间元素
    if (root->left == nullptr) {
        *smaller = nullptr;
        *greater = root;
        return;
    }

    // 找到左子树的最大元素作为右边界
    Node* rightMostNode = findMax(root->left);
    swap(rightMostNode, root);

    // 对右子树进行排序
    quickSort(root->right, smaller, greater);
    
    // 将找到的右边界插入到已排序区间的适当位置
    quickSort(rightMostNode, smaller, greater);

    *smaller = root;
}

// 辅助函数，寻找最小值
Node* findMin(Node* node) {
    while (node->left != nullptr)
        node = node->left;
    return node;
}

// 辅助函数，寻找最大值
Node* findMax(Node* node) {
    while (node->right != nullptr)
        node = node->right;
    return node;
}

// 示例：假设有一个二叉搜索树
Node* tree = buildYourBST(); // 自行构建二叉搜索树

// 使用中序遍历快速排序
void sortBST(Node* root) {
    Node* smaller = nullptr;
    Node* greater = nullptr;
    quickSort(root, &smaller, &greater);
    // 更改原树结构使其排序后仍然保持BST特性
    swap(smaller, root);
}

// 主函数
int main() {
    // ... 其他代码 ...

    sortBST(tree); // 调用排序函数
    // 输出排序后的结果
    printInOrder(tree);

    return 0;
}