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

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

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

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

11.03.2013, 13:42. Просмотров 1002. Ответов 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 корнем делать, такаяже фигня выходит( Подскажите пожалуйста, где я ошибся?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.03.2013, 13:42
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Двоичное дерево (операции вставка, удаление, поиск) (C++):

B-Дерево. Поиск. Вставка. Удаление. - C++
Доброго всем дня,есть задача: Написать программу реализующую следующие действия в B-Дереве: Поиск. Вставка. Удаление. Так же у меня...

Реализовать простейшие операции над списком: вставка, удаление, вывод на экран - C++
Народ спасайте! Помогите реализовать простейшие операции над списком: вставка, удаление, вывод на экран. Я уже столько книг перечитал на...

Слово из строки: вставка, удаление, поиск - C++
Как выдернуть слово из строки? Или посчитать длину, например 4-го слова? Как обратиться к конкретному слову в строке? Как добавить например...

Создание одномерных массивов, поиск, вставка и удаление элементов - C++
нужно написать 1.Сформировать одномерный массив целых чисел, используя датчик случайных чисел и выполнить задание c использованием...

Двоичное дерево - C++
Здравствуйте! Помоги задачу решить! Сразу говорю: это не от лени, нам просто мало объясняют! Хотя бы направление дайте, подсказку...Прогу...

Двоичное дерево - C++
Помогите найти ошибку, в консоль вообще ничего не выводится: #include&lt;iostream&gt; #include&lt;string&gt; #include&lt;fstream&gt; using...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
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);
    }
}
0
skMaster
4 / 4 / 2
Регистрация: 26.02.2013
Сообщений: 39
Завершенные тесты: 1
11.03.2013, 14:27  [ТС] #3
Цитата Сообщение от srg_btl Посмотреть сообщение
Ты работаешь с копией указателя, и каждый раз твоя функция получает дерево которое с прошлого раза не было изменено.
C++
1
void Insert(usel *&t, int k)
Большое спасибо) Заработало) Пробую дальше разбираться)
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.03.2013, 14:27
Привет! Вот еще темы с ответами:

Двоичное дерево - C++
Помогите пожалуйста построить двоичное дерево и найти в нём длину пути(количество ветвей от корня) до минимального элемента

Двоичное дерево Хаффмана - C++
Дана некоторая последовательность данных...(то есть набор каких то значений)...этот набор представляет из себя набор конечных потомков...

указатели. двоичное дерево - C++
Всем добрый день. Объясните мне, пожалуйста, несколько вещей. 1.Вот, например. root-&gt;left что делает он: -&gt; Я вроде читал, но не...

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


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

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

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