Форум программистов, компьютерный форум CyberForum.ru

Дерево - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Перенос битов http://www.cyberforum.ru/cpp-beginners/thread288608.html
Ввести число, перенести все еденичные биты в середину разрядной сетки.
C++ typedef struct .... Здравствуейте. Обьясните пожалуйсто новичку что означает этот код. typedef struct { long num_servers; long data_size; char* data; }SSQ_BATCH_REPLY,*PSSQ_BATCH_REPLY; http://www.cyberforum.ru/cpp-beginners/thread288590.html
C++ Программка С++ Proc
Описать функцию Power2(A, N) вещественного типа, находящую вели- чину AN(N-это степень A) (A — вещественный, N — целый параметр) по следующим форму- лам: A0(0-степень A) = 1; AN(N-степень A) = A•A•…•A (N сомножителей), если N > 0; AN(N-степень A)= 1/(A•A•…•A) (|N| сомножителей), если N < 0. С помощью этой функции найти AK, AL, AM(K,L,M-степени A), если...
Работа со словами в строке. C++
Здравствуйте. Помогите, пожалуйста, с решением. 1) Вводим предложение. Нужно вывести каждое слово с новой строки. Разделителями между словами могут быть: пробел, ‘ , /, , . и т.д. Цифры выводить не нужно. Программу вроде написал. #include <iostream.h> #include <string.h> void main () { char s; cout<<"vvedite text"<<endl; cin.getline(s,149);
C++ Задание про слова http://www.cyberforum.ru/cpp-beginners/thread288554.html
Здравствуйте,я в си новичок.Не поможете мне решить задачу(написать код)? "Дано ошибочно написанное слово "рпроцессо". Путем перемещения его букв получить слово "процессор"
C++ прога, которая по нажатой клавише выводит ascii - код символа это клавиши или scan - код самой клавиши. написать программу, которая по нажатой клавише выводит ascii - код символа этой клавиши или scan - код самой клавиши. осуществите вывод в 8-й, 10-й и 16-й системах счисления. код с++. заранее спасибо!!! подробнее

Показать сообщение отдельно
fasked
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
20.05.2011, 14:12     Дерево
Цитата Сообщение от pito211 Посмотреть сообщение
да собственно почти все функции дерева пригодятся и в бинарном дереве.
Начнем с того, что в Вашем классе методов всего пять! Сейчас я объясню, почему же не подойдут оставшиеся четыре. Это не так уж и много. А заодно разберемся чем же так плох Ваш класс, Вы уж простите меня, но написан он через одно место, и Вы, кстати, сами в этом признались.

Метод add не подходит по, я надеюсь, всем понятным причинам. В бинарном дереве совершенно отличный, то есть другой, алгоритм вставки. Это объяснять, я думаю, не стоит.
Что принимает в качестве аргумента метод add? Я не верю своим глазам, но это индекс. Да-да, индекс. В комментарии написано, что метод должен добавить "сына" к "предку" с указанным индексом. Возникает вопрос: какого именно сына? Видимо никакого. Можно сказать, что этот метод резервирует место для последующей операции добавления или вставки, но никак не делает то, что следует из названия.

Идем дальше...
Метод size. Тут все просто, метод должен возвратить текущее количество элементов в дереве. Во всем дереве. Интересно, работает ли. Я не проверял, конечно, но закрадываются сомнения. Особенно с учетом того, что в самом TreeItem также лежит вектор. Я верю, что тут может быть хитрая схема индексации, но не доверяю.

Метод empty. Признаюсь, я был поражен. Кроме того, что Ваше дерево никогда не будет пустым, следовательно этот метод бесполезен, его реализация это тоже нечто. Да, работать будет. Но Вы в курсе зачем вообще существуют методы по имени empty? Совсем не только ради удобства, можно было бы всегда писать xxx.size() == 0, но нет, дело в другом. В структурах данных, основанных на списках (коим является и дерево) метод empty отрабатывает за O(1) операций, это элементарная операция. Метод size отрабатывает, как минимум, за линейное время O(n). Дело именно в скорости. У метода empty - фиксированное время работы, у метода size - нет.

Метод clear. Тоже странноватый. Судя по комментарию, опять же, должен удалить все кроме корня. М-м-м... И я опять в замешательстве. Реализация вроде как соответствует описанию. Правда есть утечка памяти.

Еще два интересных момента: конструктор и деструктор. В конструкторе создается (зачем?) корень. Я уже говорил, что дерево никогда не будет пустым, потому как корень у него создан изначально. В деструкторе вызывается метод clear - корень не удаляется. Опять потекла...

Operator[]... Имеет право на жизнь в бинарном дереве, но не в таком виде. Все дело в том, что к элементу дерева (даже иерархического, а тем более бинарного) нельзя обращаться по индексу. Ну вот нарисуйте дерево на бумажке... И какой индекс будет у каждого элемента? В бинарном дереве ясное дело к элементу обращаются по ключу. В n-арном дереве, наверное тоже по ключу, по ключу предка. Это же иерархия, верно? Значит элементы дерева должны быть упорядочены по определенному признаку.

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

В класс TreeItem лезть уже не будем. Там еще можно какими-то костылями привернуть его к бинарному дереве. Но и так уже понятно, что Ваш класс дерева не имеет права на жизнь., его надо переписывать.
Можно было бы поспорить с Вами, если бы он был написан хорошо, ну или хотя бы просто правильно. Если бы все его методы работали ожидаемо, не было бы утечек памяти и т.д.

Да и вообще использовать вектор в качестве структуры для хранения решение не однозначное.
Вы знаете почему списки пишут на основе узлов, то есть это так называемые node-based структуры. Почему их не пишут на основе массивов и векторов? Малейшее изменение может привести к "катастрофе", например, вставка в середину - не очень благодарное занятие для векторов. Это же надо сдвинуть очень много элементов в право, а в node-based структуре это просто переопределение адресной части двух элементов.

А так, проще написать новый класс с нуля, чем использовать Ваш.

Добавлено через 12 минут
Цитата Сообщение от pito211 Посмотреть сообщение
алгоритмов поиска для бинарного дерева много - прямой обратный внутренний нафиг их в классе писать все, если пользователю будет нужен один из них. Пусть сам и напишет в теле программы какой ему надо.
После этой Вашей фразы можно заканчивать разговор
Читайте книги, алгоритм поиска в бинарном дереве один! Реализовать его правда можно рекурсивно или не рекурсивно. Вот и вся разница... мдэ... а я то распинался...
 
Текущее время: 17:23. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru