用c语言写一个将二叉排序树调整为平衡二叉树的算法

将二叉排序树调整为平衡二叉树的算法可以分为以下两个步骤：

1. 将二叉排序树中的节点按照中序遍历的顺序存储到一个数组中，然后重构为平衡二叉树。
2. 对于每个子树，递归执行第一步操作。

下面是具体的实现代码：

// 定义二叉树节点结构体
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

// 计算二叉树的节点个数
int countNodes(struct TreeNode* root) {
    if (!root) return 0;
    return countNodes(root->left) + countNodes(root->right) + 1;
}

// 将二叉排序树中的节点按照中序遍历的顺序存储到一个数组中
void inorderTraversal(struct TreeNode* root, struct TreeNode** nodes, int* index) {
    if (!root) return;
    inorderTraversal(root->left, nodes, index);
    nodes[(*index)++] = root;
    inorderTraversal(root->right, nodes, index);
}

// 重构平衡二叉树
struct TreeNode* buildBalancedBST(struct TreeNode** nodes, int start, int end) {
    if (start > end) return NULL;
    int mid = (start + end) / 2;
    struct TreeNode* root = nodes[mid];
    root->left = buildBalancedBST(nodes, start, mid - 1);
    root->right = buildBalancedBST(nodes, mid + 1, end);
    return root;
}

// 将二叉排序树调整为平衡二叉树
struct TreeNode* balanceBST(struct TreeNode* root) {
    int n = countNodes(root);
    struct TreeNode** nodes = (struct TreeNode**)malloc(n * sizeof(struct TreeNode*));
    int index = 0;
    inorderTraversal(root, nodes, &index);
    return buildBalancedBST(nodes, 0, n - 1);
}

这个算法的时间复杂度为 O(n)，其中 n 是二叉树中节点的个数。