Алгоритм двоичного дерева поиска, который возвращает массив значений в диапазоне - PullRequest
Новая
       19

Алгоритм двоичного дерева поиска, который возвращает массив значений в диапазоне

0 голосов
/ 01 ноября 2019

Напишите функцию рекурсивного диапазона , в которой задано двоичное дерево поиска, два целых числа k1 и k2, для которых k1 ≤ k2, и вектор v вставляет в v все ключи в порядке возрастания, организованные вдерево такое, что k1 ≤ k ≤ k2. Функция возвращает размер вектора v.

Это мое решение: 

typedef struct node {
  int key;
  struct node * left;
  struct node * right;
  struct node * parent;
} * Node;

void rangeRic(Node u, int k1, int k2, int v[], int * pindex) {
  if (u == NULL) {
    return;
  }

  rangeRic(u->left,k1,k2,v,pindex);

  if (u->key >= k1 && u->key <= k2) {
    v[*pindex] = u->key;
    *pindex += 1;
  }

  rangeRic(u->right,k1,k2,v,pindex);
}

int range(Node u, int k1, int k2, int v[]) {
  int i = 0;
  rangeRic(u,k1,k2,v,&i);
  return i;
}

Моя проблема в том, что в описании упражнения также указано следующее:

Вы не можете использовать какую-либо вспомогательную функцию, и вектор v имеет достаточно места для размещения всех элементов, удовлетворяющих условию.

, и это последнее утверждение делает недействительным мое решение.

Как скомпилировать: gcc -std=gnu89 -pedantic -Wall -o main main.c binarySearchTree.c

Не могли бы вы, ребята, помочь мне с этим?

1 Ответ

1 голос
/ 01 ноября 2019

Вы можете вернуть количество элементов, добавленных с каждого узла, и использовать его в качестве индекса в массиве. 

int range(Node u, int k1, int k2, int v[]) {
  if (u == NULL) {
    return 0;
  }

  // Will return how many items added from the left side
  int count = range(u->left, k1, k2, v);

  if (u->key >= k1 && u->key <= k2) {
    // Add and increment counter
    v[count++] = u->key;
  }

  // Add how many from the right side
  // Note: passing the last part of the array
  // Could also write v+count as &v[count]
  return count + range(u->right, k1, k2, v + count);
}
...