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

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

Войти
Регистрация
Восстановить пароль
 
skMaster
3 / 3 / 2
Регистрация: 26.02.2013
Сообщений: 38
#1

Двоичное дерево (операции вставка, удаление, поиск) - C++

11.03.2013, 13:42. Просмотров 923. Ответов 2
Метки нет (Все метки)

Вообщем пытаюсь научиться работать с двоичными деревьями.
Информацию беру с википедии: ru.wikipedia.org.
Пока пытаюсь реализовать функцию вставки нового узла в дерево по алгаритму:
Дано: дерево Т и ключ K.
Задача: добавить ключ K в дерево Т.
Алгоритм:
Если дерево пусто, заменить его на дерево с одним корневым узлом (K, null, null) и остановиться.
Иначе сравнить K с ключом корневого узла X.
Если K<X, рекурсивно добавить K в левое поддерево Т.
Если K>=X, рекурсивно добавить K в правое поддерево Т.

Начал делать вот так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <conio.h>
#include <windows.h>
#include <time.h>
 
using namespace std;
 
struct usel{
    int x;
    usel *left;
    usel *right;
};
 
usel *newUsel(int k){
    usel *t = new usel;
    t->left=NULL;
    t->right=NULL;
    t->x=k;
    return t;
};
 
void Insert(usel *t, int k)
{
    if(t==NULL)
    {
        cout<<"Записываем"<<endl;
        t=newUsel(k);
    }
    else if(k<t->x)
    {
        cout<<"Идем влево ";
        Insert(t->left,k);
    }
    else
    {
        cout<<"Идем вправо ";
        Insert(t->right,k);
    }
}
 
int main(){
    setlocale(LC_ALL, "Russian");
    usel *t = newUsel(50);
    srand(time(0));
    for(int i=1; i<99; i++)
    {
        int k = 1 + rand()%98;
        cout<<"Вставляем "<<k<<": ";
        Insert(t, k);
    }
    _getch();
    return 0;
}
Тоесть создаю корневой узел t с ключем 50 (среднее из моих значений, чтобы болеменее наглядно было), далее добавляю 99 узлов рандомно из промежутка [1,99]. Но такая фигня получается, программа тупо сравнивает их все с корнем и записывает в левую либо в правую ветку, не углубляясь при этом. Тоесть когда функцию Insert рекурсивно вызываю, она почемуто считает что дочерние ветки=NULL. В си++ я чайник такчто прошу сильно не пинать)
Пробовал и дерево с NULL корнем делать, такаяже фигня выходит( Подскажите пожалуйста, где я ошибся?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.03.2013, 13:42     Двоичное дерево (операции вставка, удаление, поиск)
Посмотрите здесь:

C++ Двоичное дерево
C++ B-Дерево. Поиск. Вставка. Удаление.
C++ Двоичное дерево
C++ Реализовать простейшие операции над списком: вставка, удаление, вывод на экран
указатели. двоичное дерево C++
C++ C++. Числовое двоичное дерево
Создание одномерных массивов, поиск, вставка и удаление элементов C++
Двоичное дерево C++
Слово из строки: вставка, удаление, поиск C++
Двоичное дерево поиска C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
srg_btl
34 / 34 / 2
Регистрация: 21.02.2013
Сообщений: 90
11.03.2013, 14:23     Двоичное дерево (операции вставка, удаление, поиск) #2
Ты работаешь с копией указателя, и каждый раз твоя функция получает дерево которое с прошлого раза не было изменено.

void Insert(usel*& t, int k)

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void Insert(usel *&t, int k)
{
    if(t==NULL)
    {
        cout<<"Записываем"<<endl;
        t=newUsel(k);
    }
    else if(k<t->x)
    {
        cout<<"Идем влево ";
        Insert(t->left,k);
    }
    else
    {
        cout<<"Идем вправо ";
        Insert(t->right,k);
    }
}
skMaster
3 / 3 / 2
Регистрация: 26.02.2013
Сообщений: 38
11.03.2013, 14:27  [ТС]     Двоичное дерево (операции вставка, удаление, поиск) #3
Цитата Сообщение от srg_btl Посмотреть сообщение
Ты работаешь с копией указателя, и каждый раз твоя функция получает дерево которое с прошлого раза не было изменено.
C++
1
void Insert(usel *&t, int k)
Большое спасибо) Заработало) Пробую дальше разбираться)
Yandex
Объявления
11.03.2013, 14:27     Двоичное дерево (операции вставка, удаление, поиск)
Ответ Создать тему
Опции темы

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