Бинарное дерево поиска, 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

[Гость]

Огромное спасибо.
Буду просто очень благодарен, если ты (или кто нибудь кто разбирается) объяснит как это функционирует, желателньо максимально больше подробностей про то как что и куда движется.... или по ихсожднку краткие комнетарие, тогда прошу дать сылку где максималньо доступно это можно понять.....
Заранее благодарю

[-Ник-]

Объчсните пожалуйста программу хоть кто - нибудь. Желательно с теоретическимим подробностями, а то понять не могу....

[volvo]

Тебе же дали в разделе "Теоретические вопросы" ссылку на теорию... Программа взята оттуда и переведена на С...

[-Ник-]

Понятно, постараюь по анлогии.
Ещё такой вопрос, вот вообще нам говорили что реализацию делать луучше так что часть идёт влево, а часть в право и колво ветвей с одной стороны не более чем на еденицу превосходит кол -во с другой. здесь так реализованно?

[Алена]

здесь так реализованно?

Нет... То, что ты написал чуть выше - это сбалансированное дерево. У меня реализовано обычное... Есть сбалансированные (AVL-деревья) тоже, только не на чистом С, а на С++. Если надо - говори...

[Гость]

Понятно, да наверное збалансированное дерево, вот только как раз вэ том заминка нельзя ли на Си никак? Просто препод задаёт на Си, даже не знаю, ну если это абсурдно то выполни пожалуйста на Си++ буду благодарен....

И ещё одно я знаю что Вольво уже дал ссылку, но мне легче понят по Си не могл бы ты (исключительно если есть время) пояснить работу проги и вообще работу с формированием дерева....?

[Алена]

Комментарии добавлены...

[Алена]

Кстати, вот тут есть то, что тебе нужно, причем с объяснениями:
Идеально сбалансированные бинарные деревья
Посмотри также следующий шаг: сбалансированные по высоте деревья.
(к сожалению, везде используется С++, на чистом С не нашла...)

[-Ваня-]

Столько лет прошло! Спасибо Вам Алёна! теперь я понял