IPB
ЛогинПароль:

> Внимание!

1. Пользуйтесь тегами кода. - [code] ... [/code]
2. Точно указывайте язык, название и версию компилятора (интерпретатора).
3. Название темы должно быть информативным. В описании темы указываем язык!!!

 
 Ответить  Открыть новую тему 
> Бинарное дерево поиска, C
-Ник-
сообщение 12.11.2006 21:35
Сообщение #1


Гость






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


Гость






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

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
 К началу страницы 
+ Ответить 
Гость
сообщение 12.11.2006 22:52
Сообщение #3


Гость






Огромное спасибо.
Буду просто очень благодарен, если ты (или кто нибудь кто разбирается) объяснит как это функционирует, желателньо максимально больше подробностей про то как что и куда движется.... или по ихсожднку краткие комнетарие, тогда прошу дать сылку где максималньо доступно это можно понять.....
Заранее благодарю
 К началу страницы 
+ Ответить 
-Ник-
сообщение 13.11.2006 14:57
Сообщение #4


Гость






Объчсните пожалуйста программу хоть кто - нибудь. Желательно с теоретическимим подробностями, а то понять не могу....
 К началу страницы 
+ Ответить 
volvo
сообщение 13.11.2006 15:03
Сообщение #5


Гость






Тебе же дали в разделе "Теоретические вопросы" ссылку на теорию... Программа взята оттуда и переведена на С...
 К началу страницы 
+ Ответить 
-Ник-
сообщение 13.11.2006 15:56
Сообщение #6


Гость






Понятно, постараюь по анлогии.
Ещё такой вопрос, вот вообще нам говорили что реализацию делать луучше так что часть идёт влево, а часть в право и колво ветвей с одной стороны не более чем на еденицу превосходит кол -во с другой. здесь так реализованно?
 К началу страницы 
+ Ответить 
Алена
сообщение 13.11.2006 16:01
Сообщение #7


Гость






Цитата
здесь так реализованно?
Нет... То, что ты написал чуть выше - это сбалансированное дерево. У меня реализовано обычное... Есть сбалансированные (AVL-деревья) тоже, только не на чистом С, а на С++. Если надо - говори...
 К началу страницы 
+ Ответить 
Гость
сообщение 13.11.2006 16:26
Сообщение #8


Гость






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

И ещё одно я знаю что Вольво уже дал ссылку, но мне легче понят по Си не могл бы ты (исключительно если есть время) пояснить работу проги и вообще работу с формированием дерева....?
 К началу страницы 
+ Ответить 
Алена
сообщение 14.11.2006 2:18
Сообщение #9


Гость






Комментарии добавлены...
 К началу страницы 
+ Ответить 
Алена
сообщение 14.11.2006 12:04
Сообщение #10


Гость






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


Гость






Столько лет прошло! Спасибо Вам Алёна! теперь я понял give_rose.gif
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 



- Текстовая версия 19.03.2024 10:18
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"