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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.73
PointsEqual
ниначмуроФ
835 / 519 / 33
Регистрация: 12.10.2009
Сообщений: 1,915
#1

Дерево поиска. добавление элемента - C++

23.03.2011, 11:32. Просмотров 1456. Ответов 5
Метки нет (Все метки)

Привет. Поясните кое что с деревом.
Допустим есть класс
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class bst
{
    public:
        bst(): root(NULL) {}
        virtual ~bst() {}
 
        void insert(binaryNode*& , size_t);
        void inorder(binaryNode*);
        binaryNode* getRoot(){  return root; }
 
    protected:
        node* root;
    private:
};

и операция добавления элемента в дерево
C++
1
2
3
4
5
6
7
8
9
10
void bst::insert(binaryNode*& r , size_t key){
    if ( r == NULL ){
         r = new binaryNode(key);
        return;
    }
    else if (key < r -> key)
        insert(r ->left, key);
    else if (key > r -> key)
        insert(r -> right, key);
}
В функцию передается по ссылке указатель на корень дерева(root), но после, например, 5 операций insert, root ведь будет указывать не на вершину дерева а на последний вставленный элемент.
И тогда getRoot() тоже будет возвращать указатель не на вершину дерева а на последний вставленный элемент.
А мне хотелось бы чтобы root всегда указывал на вершину.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.03.2011, 11:32
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Дерево поиска. добавление элемента (C++):

Бинарное дерево поиска (удаление, добавление элемента) - C++
Задачи В Бинарном дереве поиска 1)введено с клавиатуры значение, если существует узел с таким значением, он удаляется; 2) с...

Добавление нового элемента в бинарное дерево поиска с вспомогательной функцией(без рекурсии) - C++
с реализацией этой функции с рекурсией проблем нету.но без нее уже по-сложнее(.есть функция иbool Add(int) определенная в классе Дерева,и в...

N дерево, добавление элемента - C++
Добрый вечер, не могу нормально написать добавление узла в дереве. Несколько вариантов пробовал, ни один не сработал, это последний. Где...

Добавление элемента в бинарное дерево - C++
Добрый вечер, помогите написать метод добавления в бинарное дерево. Я написал вот такой код: class word_translate { private: char...

Исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру - C++
Помогите, не могу понять!( Нужно исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру. вот...

дерево поиска - C++
Помогите написать прог-му на С++ задача: Написать программу построения частотного словаря слов некоторого текста в виде дерева...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
23.03.2011, 13:07 #2
Мне не видно, чтобы insert изменял root.

Добавлено через 1 минуту
В корректной реализации, вставка элемента реализуется через бинарный поиск.

Добавлено через 21 секунду
*от корня.

Добавлено через 16 секунд
*с последующей перестройкой дерева.)
fasked
Эксперт С++
4935 / 2515 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
23.03.2011, 13:12 #3
Цитата Сообщение от Deviaphan Посмотреть сообщение
В корректной реализации, вставка элемента реализуется через бинарный поиск.
Чем, интересно, рекурсивная реализация некорректна?
Цитата Сообщение от Deviaphan Посмотреть сообщение
с последующей перестройкой дерева
Опять непонятно, зачем перестраивать дерево после вставки элемента для несбалансированных деревьев?

Цитата Сообщение от PointsEqual Посмотреть сообщение
А мне хотелось бы чтобы root всегда указывал на вершину.
Так и есть.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
23.03.2011, 13:19 #4
Цитата Сообщение от fasked Посмотреть сообщение
Чем, интересно, рекурсивная реализация некорректна?
Моей невнимательностью.(
PointsEqual
ниначмуроФ
835 / 519 / 33
Регистрация: 12.10.2009
Сообщений: 1,915
23.03.2011, 14:10  [ТС] #5
fasked,

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    int main()
{
    bst klen;
 
    binaryNode* p_root = klen.getRoot();
    klen.insert(p_root, 8 );
    klen.insert(p_root, 6 );
   // p_root = klen.getRoot();
    klen.insert(p_root, 12 );
 
 
    klen.inorder(p_root);
 
  return 0;
}
если я расскоментирую строку, то inorder выведет только последнее добавленное число(12), следовательно root указывает не на вершину все таки

Добавлено через 7 минут
Цитата Сообщение от Deviaphan Посмотреть сообщение
Мне не видно, чтобы insert изменял root.
insert изменяет не совсем root, а указатель на root
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
23.03.2011, 14:14 #6
А должен изменять левый или правй узел в руте.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.03.2011, 14:14
Привет! Вот еще темы с ответами:

Дерево поиска - C++
Всем добрый полдень:) Помогите пож-та решить вот такую вот задачку: В текстовом файле задан алфавит(на англ(a-z), нужно построить...

Дерево поиска - C++
Здравствуйте, хочу написать set на базе КЧ-дерева, начал с обычного дерева и столкнулся с ошибками, буду очень благодарен за помощь. ...

Бинарное дерево поиска - C++
Решил написать бинарное дерево поиска, но что-то пошло не так, дерево не выводиться не понимаю почему. Вот весь код: #include...

Двоичное дерево поиска - C++
Даны 2 вершины дерева .Для каждой из данных вершины вывести ее уровень или информацию что такой вершины нет Подскажите как...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
23.03.2011, 14:14
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru