Дерево поиска

@serega006 · Регистрация: 16.10.2011

Студворк — интернет-сервис помощи студентам

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

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <fstream>
#include "Set.h"
 
using namespace std;
 
Set set;
 
int main()
{
    ifstream in("input.txt");
 
    while (!in.eof())
    {
        string s;
        in >> s;
        set.insert(s); //строки one, two и т.д. добавляет вроде как нормально
    }
    cout << set.find("one"); //здесь начинаются ошибки
    cout << set.find("g");
    return 0;
}

Set.h

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#ifndef Set_H
#define Str_H
#include <string>
#include <cstddef>
struct treeNode;
 
class Set
{
public:
    treeNode *root;
    Set(void);
    ~Set(void);
    void insert(std::string k);
    int find(std::string x, treeNode **node = 0);
};
#endif

Set.cpp

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include "Set.h"
 
struct treeNode
{
    treeNode *left;
    treeNode *right;
    treeNode *parent;
    std::string value;
    //bool red; Для КЧ дерева
};
 
 
Set::Set()
{
    root = new treeNode();
    //root->red = 0; 
    root->right = 0;
    root->left = 0;
    root->parent = 0;
}
 
Set::~Set()
{
    delete root;
}
 
void Set::insert(std::string k)
{
    treeNode *node;
    if (find(k, &node) != 0)
    {
        treeNode *tmp = new treeNode();
        tmp->value = k;
        //tmp->red = 1;
        tmp->right = 0;
        tmp->left = 0;
 
        tmp->parent = node;
        if (k < node->value)
            node->left = tmp;
        else
            node->right = tmp;
    }
 
 
}
 
int Set::find(std::string x, treeNode **node)
{
    treeNode *v, *vp;
    v = root;                           
    vp = root;                                          
    int res = -1;                   
    std::string y;                                    
                                                   
    while (v != 0)                                
    {                                            
        y = v->value;
        if (x == y)
        {
            *node = v; //Здесь вылетает System.NullReferenceException
            return 0;
        }
        else if (x < y)
        {
            vp = v;
            v = v->left;
        }
        else
        {
            vp = v;
            v = v->right;
        }
    }
    *node = vp; // в случае невыполнения условия x == y System.NullReferenceException будет тут.              
    return res;
}

@serega006 · 29.11.2015, 01:07 **[ТС]**

С предыдущей проблемой разобрался и почти закончил дерево, но возникла еще одна трабла, я нашел функцию для удаления вершин из дерева, но она выкидывает исключение если пытаешься удалить корень дерева. Причину исключения видно, но вот как её пофиксить я не знаю, может кто подскажет.

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
void delete_node(std::string z)
{
    treeNode *node;
    if(find(z, &node) == 0);
        {
    treeNode *x, *y, *c;  
    c = node;
        if (!c || c == NULL) return;
 
 
        if (!c->left || !c->right) {
            y = c;
        }
        else {
            y = c->right;
            while (y->left) y = y->left;
        }
 
        if (y->left)
            x = y->left;
        else if(x->right)
 
        x->parent = y->parent; // исключение тут, потому что x = 0
        if (y->parent)
            if (y == y->parent->left)
                y->parent->left = x;
            else
                y->parent->right = x;
        else
            root = x;
 
        if (y != c) c->value = y->value;
 
        if (y->red == 0)
            rebalanse_delete(x);
 
        delete y;
                }
}

Новые блоги и статьи Все статьи Все блоги /
AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .	Отображение реквизитов в документе по условию и контроль их заполнения Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .	Фото всей Земли с борта корабля Orion миссии Artemis II kumehtar 04.04.2026 Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .	Вывод диалогового окна перед закрытием, если документ не проведён Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .
Программный контроль заполнения реквизитов табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: 1. Реализовать контроль заполнения реквизита. . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .	Вывод данных в справочнике через динамический список Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .