c语言二叉树排序算法动态顺序表实现

首先，我们需要定义二叉树结点的结构体：

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

接下来，我们可以定义一个创建二叉树的函数，该函数可以接收一个动态顺序表作为输入，并返回二叉树的根节点。

Node* createBinaryTree(int* arr, int size) {
    Node* root = NULL;
    for (int i = 0; i < size; i++) {
        root = insertNode(root, arr[i]);
    }
    return root;
}

其中，insertNode函数用于向二叉树中插入一个结点，代码如下：

Node* insertNode(Node* root, int data) {
    if (root == NULL) {
        root = (Node*)malloc(sizeof(Node));
        root->data = data;
        root->left = NULL;
        root->right = NULL;
    } else if (data < root->data) {
        root->left = insertNode(root->left, data);
    } else if (data > root->data) {
        root->right = insertNode(root->right, data);
    }
    return root;
}

接下来，我们可以定义一个中序遍历二叉树的函数，该函数可以将二叉树中的结点按照升序排列，并存储到动态顺序表中。

void inorderTraversal(Node* root, int* arr, int* index) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left, arr, index);
    arr[(*index)++] = root->data;
    inorderTraversal(root->right, arr, index);
}

最后，我们可以编写一个函数，用于对动态顺序表中的元素进行排序。这里我们可以使用快速排序算法。

void quickSort(int* arr, int left, int right) {
    if (left >= right) {
        return;
    }
    int i = left, j = right, pivot = arr[left];
    while (i < j) {
        while (i < j && arr[j] >= pivot) {
            j--;
        }
        arr[i] = arr[j];
        while (i < j && arr[i] <= pivot) {
            i++;
        }
        arr[j] = arr[i];
    }
    arr[i] = pivot;
    quickSort(arr, left, i - 1);
    quickSort(arr, i + 1, right);
}

完整代码如下：

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

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

Node* insertNode(Node* root, int data) {
    if (root == NULL) {
        root = (Node*)malloc(sizeof(Node));
        root->data = data;
        root->left = NULL;
        root->right = NULL;
    } else if (data < root->data) {
        root->left = insertNode(root->left, data);
    } else if (data > root->data) {
        root->right = insertNode(root->right, data);
    }
    return root;
}

Node* createBinaryTree(int* arr, int size) {
    Node* root = NULL;
    for (int i = 0; i < size; i++) {
        root = insertNode(root, arr[i]);
    }
    return root;
}

void inorderTraversal(Node* root, int* arr, int* index) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left, arr, index);
    arr[(*index)++] = root->data;
    inorderTraversal(root->right, arr, index);
}

void quickSort(int* arr, int left, int right) {
    if (left >= right) {
        return;
    }
    int i = left, j = right, pivot = arr[left];
    while (i < j) {
        while (i < j && arr[j] >= pivot) {
            j--;
        }
        arr[i] = arr[j];
        while (i < j && arr[i] <= pivot) {
            i++;
        }
        arr[j] = arr[i];
    }
    arr[i] = pivot;
    quickSort(arr, left, i - 1);
    quickSort(arr, i + 1, right);
}

int main() {
    int arr[] = {5, 3, 7, 1, 4, 6, 8};
    int size = sizeof(arr) / sizeof(arr[0]);
    Node* root = createBinaryTree(arr, size);

    int* sortedArr = (int*)malloc(sizeof(int) * size);
    int index = 0;
    inorderTraversal(root, sortedArr, &index);

    quickSort(sortedArr, 0, size - 1);

    for (int i = 0; i < size; i++) {
        printf("%d ", sortedArr[i]);
    }
    printf("\n");

    free(sortedArr);
    return 0;
}