Бинарное дерево поиска, C Опции

[-Ник-]

Здравствуйте.
Помогите выполнить задние на С.
Построить бинарное дерево поиска содержащее все целые числа из интервала [l,r)
ну типо портотип функции Node *mktree(int l, int r); ну это желвателньо чтобы функция слдевала прототипу, но вообщще можно ему и не следовать.

[Алена]

Нужен чистый С? Тогда так:

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

/*
  Функция, создающая узел дерева
  на входе - число для хранения в узле
  результат - указатель на вновь созданный узел...
*/
struct Node *create_node(int n) {

  struct Node *ptr;
  /* Запрашиваем у системы память под узел */
  ptr = (struct Node *)malloc(sizeof(ptr));

  /* Значение поля данных установить в N */
  ptr -> val = n;
  /* Указатели на левое/правое поддерево в новом узле, естественно, обнуляем*/
  ptr -> left = ptr -> right = 0;
  /* И возвращаем результат */
  return ptr;

}

/*
  Функция, добавляющая к дереву навый элемент
  На входе - T: указатель на корень дерева, n - добавляемое значение
  На выходе - новый корень дерева
*/
struct Node *add_node(struct Node *T, int n) {

  struct Node *res; /* Переменная для временного хранения результата */

  /*
    Если переданное функции дерево - непустое (T != NULL),
    то начинаем работу с корня дерева
  */
  if(T) {

    /*
      если добавляемый элемент больше текущего узла,
      значит рекурсивно добавить его в ПРАВОЕ поддерево.

      Что при этом происходит? Мы вызываем эту же фунуцию,
      но передаем в нее не сам корень (его-то мы уже получали, и с ним работаем),
      а указатель на правое поддерево, который будет считаться корнем как только
      add_node рекурсивно запустится... (Я не буду читать тебе лекции по рекурсии,
      сам разберись, что делается при подобных вызовах...)
    */
    if((T -> val) < n) T -> right = add_node(T -> right, n);
    /* 
        Если же добавляемое число меньше текущего корня - оно должно быть
        добавлено в ЛЕВОЕ поддерево. Аналогично тому, что написано выше...
    */
    else if((T -> val) > n) T -> left = add_node(T -> left, n);

    /* Сохраняем промежуточный результат: указатель на корень дерева */
    res = T;
  }
  /*
    Если изначально дерево было пустым, или мы рекурсивно добрались до листа
    (узла БЕЗ поддеревьев), то нужно создать новый узел (что и делается, используя
    предназначенную для этого функцию)
  */
  else
    res = create_node(n);

  /* Ну, и наконец, возвращаем результат - новый корень текущего дерева */
  return res;

}


/* 
    Это - сама процедура генерации дерева. Все, что она делает - 
    определяет указатель на "корень", и последовательно вызывает
    add_node с теми значениями, которые нужно добавить в дерево...

    Всё, ее больше ничего не интересует. add_node сама заботится о том,
    чтобы добавить узел на правильное место...
*/
struct Node *mktree(int l, int r) {

  struct Node *root = 0;
  int i;

  for(i = l; i < r; i++)
    root = add_node(root, i);

  /* Возвращаем "корень" в основную программу */
  return root;

}

/* 
    Рекурсивная процедура печати дерева, только для контроля результатов,
    просто печатает содержимое поля данных всех узлов дерева...
*/
void print_tree(struct Node *root) {

  if(!root) return;

  printf("%d ", root -> val);

  print_tree(root -> left);
  print_tree(root -> right);

}

/* 
    Ну, и основная функция - main(), вызывает функцию создания дерева,
    и распечатывает его... Вот, собственно, и все...
*/
int main() {

  struct Node *root = mktree(1, 6);
  print_tree(root);
  return 0;

}

Сообщение отредактировано: Алена - 14.11.2006 2:16