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

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

Восстановить пароль Регистрация
 
skMaster
3 / 3 / 2
Регистрация: 26.02.2013
Сообщений: 38
11.03.2013, 13:42     Двоичное дерево (операции вставка, удаление, поиск) #1
Вообщем пытаюсь научиться работать с двоичными деревьями.
Информацию беру с википедии: 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++
C++ B-Дерево. Поиск. Вставка. Удаление.
C++ Двоичное дерево
двоичное дерево C++
Создание одномерных массивов, поиск, вставка и удаление элементов C++
Слово из строки: вставка, удаление, поиск C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
srg_btl
33 / 33 / 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     Двоичное дерево (операции вставка, удаление, поиск)
Ответ Создать тему
Опции темы

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