При использовании qsort () для дерева, состоящего из структур, я не получаю отсортированный массив обратно

Question

Используя qsort на дереве из структур, я не получаю отсортированный массив обратно.

Я пытался манипулировать функцией компаратора и qsort, но не уверен, в чем проблема.

typedef struct nodeBST { // struct
    char *key;
    int count;
    struct nodeBST *left;
    struct nodeBST *right;
} nodeBST;

---

qsort(*words, numTokensActual, sizeof(nodeBST), comparator); //qsort

---

for (i = 0; i < numTokensActual; i++) {
    printf("sorted words[%d]:%s: %d \n", i,
           ((struct nodeBST *)words[i])->key,
           ((struct nodeBST *)words[i])->count); //traverse to print
}

---

struct nodeBST *words[4]; //creation of array and malloc for space

int z;

for (z = 0; z < 4; z++) {
    words[z] = malloc(sizeof(nodeBST));
}

---

int comparator(const void *p, const void *q) { //compare function
    struct nodeBST *a = (struct nodeBST **)p;    
    struct nodeBST *b = (struct nodeBST **)q;

    return a->count - b->count;
} 

---

printf("%d \n"((struct nodeBST*)words[i])->count); //print output

---

int numTokensActual = AddToArray(root, words, 0);

---

int AddToArray(nodeBST *node,  nodeBST **arr, int i) {
    if (node == NULL)
        return i;

    if (node->left != NULL)
        i = AddToArray(node->left, arr, i);

    //printf("Adding To Array[%d]: %s:%d\n",i, node->key, node->count);
    //arr[i] = node;
    arr[i] = newNodeBST2(node->key, node->count);
    //printf("added array[%d]: %s\n", i, arr[i]->key);
    i++;
    if (node->right != NULL)
        i = AddToArray(node->right, arr, i);

    return i;
}

Я ожидаю, что вывод даст мне отсортированный массив, но вывод:

0 
0 
49 
6

Answer 1

У вас нет массива, прочтите документацию:

Функция qsort () сортирует массив с элементами nmemb размера size.

Мы можем использовать qsort для получения отсортированного списка элементов без изменения структуры данных, если вы строите временный массив с count и указателем на такие элементы, как:

struct {
    int count;
    struct nodeBST *node;
} tempSortedNodes[numTokensActual];

Пройдите по вашему дереву и заполните массив sorted, после чего вы сможете выполнить его сортировку.Обратите внимание, что отсортированная версия становится недействительной при обновлении дерева.

Другой подход заключается в использовании другого дерева, использующего вместо ключа count.Это вторичное дерево также будет недействительным при каждом обновлении исходного дерева.Однако мы можем обновить оба дерева, если вам нужно постоянно поддерживать отсортированную по счету версию дерева.

Алгоритм сортировки для дерева, как предлагается в комментариях, вообще не является хорошей идеей,Это было бы эквивалентно созданию нового дерева, используя count в качестве ключа, как я и предлагал.