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

Написать класс, описывающий дерево - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.82
velodro
72 / 1 / 1
Регистрация: 28.11.2009
Сообщений: 78
06.11.2010, 15:19     Написать класс, описывающий дерево #1
Хочется понять, как написать простейший класс, описывающий дерево.
Компилирует данный код, но пишет пишет "ошибка сегментирования"

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
#include <iostream>
 
using namespace std;
 
class Tree
{
    int data;
    Tree *right;
    Tree *left;
public:
    Tree()
    {
        data = 0;
        right = left = NULL;
    }
    void make(Tree **pp, int d);
};
 
void Tree::make(Tree **pp, int d)
{
    if(!(*pp))
    {
        Tree *p = new Tree;
        p->data = d;
        *pp = p;
    }
    else 
    {
        if ((*pp)->data > d)
            make(&((*pp)->right), d);
        else
            make(&((*pp)->right), d);
    }
}
 
int main()
{
    Tree *pp;
    pp->make(&pp,3);
    return 0;
}
Подскажите пожалуйста!

 Комментарий модератора 
Дублирование тем запрещено правилами форума (п. 3.4).
Не плодите одинаковых тем.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.11.2010, 15:19     Написать класс, описывающий дерево
Посмотрите здесь:

Создать класс описывающий множество C++
Класс, описывающий окружность C++
Класс описывающий квадрат, перегрузка C++
Создать класс, описывающий треугольник, и наследник, описывающий прямые треугольной призмы C++
Создать классы, описывающий прямоугольники и класс-наследник, описывающий прямоугольные параллепипеды C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
volovzi
266 / 168 / 8
Регистрация: 14.03.2010
Сообщений: 501
06.11.2010, 16:09     Написать класс, описывающий дерево #2
Ну, во-первых, у тебя неинициализирован указатель на объект "pp", поэтому при попытке вызова метода этого объекта произойдёт ошибка.
А во-вторых, функция "make" — это тихий ужас. Так нельзя работать с объектами.
velodro
72 / 1 / 1
Регистрация: 28.11.2009
Сообщений: 78
06.11.2010, 16:36  [ТС]     Написать класс, описывающий дерево #3
а конструктор видели? или там нет инициализации по умолчанию? а на счёт функции make Ваш комметарий мягко говоря неинформативен хочется конкретики.. как бы Вы решели эту задачу?
volovzi
266 / 168 / 8
Регистрация: 14.03.2010
Сообщений: 501
06.11.2010, 17:29     Написать класс, описывающий дерево #4
До вызова конструктора у тебя дело не доходит. Ты должен выделить память под объект прежде, чем его использовать.
C++
1
Tree *pp = new Tree;
Функция "make" ужасна тем, что работает с объектом "снаружи" являясь при этом его методом.
Вместо неё нужно сделать функцию "insert", которая добавляет в уже существующее дерево новый элемент.
velodro
72 / 1 / 1
Регистрация: 28.11.2009
Сообщений: 78
06.11.2010, 21:34  [ТС]     Написать класс, описывающий дерево #5
действительно, память не выделилась.. спасибо! это мой косяк!
может так?
C++
1
pp = new Tree;
я так понимаю это должно быть внутри make?
а разве make не добавляет новые эл-ты?
как тогда выглядеть функция insert?
volovzi
266 / 168 / 8
Регистрация: 14.03.2010
Сообщений: 501
06.11.2010, 22:14     Написать класс, описывающий дерево #6
velodro, метод класса, принимающий указатель на объект, методом которого он является — это бессмыслица.
Вот пример, как делать можно:
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
#include <iostream>
 
class binary_tree {
private:
    class binary_tree_node {    
    public:
        binary_tree_node (int value) : m_value(value), m_left(0), m_right(0) {}
    
        ~binary_tree_node () {
            delete m_left;
            delete m_right;
        }
        
        void insert (int value) {
            if (value < m_value) insert_left(value);
            else insert_right(value);
        }
        
        void show () const {
            if (m_left != 0) m_left->show();
            std::cout << m_value << ' ';
            if (m_right != 0) m_right->show();
        }
        
    private:
        void insert_left (int value) {
            if (m_left == 0) m_left = new binary_tree_node(value);
            else m_left->insert(value);
        }
        void insert_right (int value) {
            if (m_right == 0) m_right = new binary_tree_node(value);
            else m_right->insert(value);
        }
    
    private:
        int m_value;
        
        binary_tree_node * m_left;
        binary_tree_node * m_right;
    };
    
public:
    binary_tree () : m_root(0) {}
    ~binary_tree () { delete m_root; }
 
    void insert (int value) {
        if (m_root == 0) m_root = new binary_tree_node(value);
        else m_root->insert(value);
    }
    
    void show () const { if (m_root != 0) m_root->show(); }
 
private:
    binary_tree_node * m_root;
};
 
int main () {
    binary_tree tree;
    
    for (int i = 0; i < 10; ++i) {
        int x = random() % 10;
        
        std::cout << x << ' ';
        tree.insert(x);
    }
    
    std::cout << std::endl;
    
    tree.show();
    
    return 0;
}
velodro
72 / 1 / 1
Регистрация: 28.11.2009
Сообщений: 78
06.11.2010, 23:27  [ТС]     Написать класс, описывающий дерево #7
а вот в 51 строке слово const это к чему?
volovzi
266 / 168 / 8
Регистрация: 14.03.2010
Сообщений: 501
06.11.2010, 23:48     Написать класс, описывающий дерево #8
velodro, это значит, что метод не модифицирует экземпляр своего класса. Помогает отлавливать большее число ошибок на этапе компиляции.
velodro
72 / 1 / 1
Регистрация: 28.11.2009
Сообщений: 78
04.12.2010, 22:28  [ТС]     Написать класс, описывающий дерево #9
а как в таком дереве организовать удаление? поиск мне удался.
volovzi
266 / 168 / 8
Регистрация: 14.03.2010
Сообщений: 501
05.12.2010, 13:12     Написать класс, описывающий дерево #10
Самый простой способ — левая ветвь удаляемого элемента вставляется в правую, а правая поттягивается на его место.
velodro
72 / 1 / 1
Регистрация: 28.11.2009
Сообщений: 78
05.12.2010, 18:04  [ТС]     Написать класс, описывающий дерево #11
а как взять то к чему подтягивать.. создать поле с идентификационными номерами, расположенными по порядку, и искать предыдущий по ним?
volovzi
266 / 168 / 8
Регистрация: 14.03.2010
Сообщений: 501
05.12.2010, 18:10     Написать класс, описывающий дерево #12
velodro, нет, просто всю процедуру удаления производить из того узла, к которому подтягивать.
velodro
72 / 1 / 1
Регистрация: 28.11.2009
Сообщений: 78
05.12.2010, 19:40  [ТС]     Написать класс, описывающий дерево #13
вот такую штуку написал и ЗАРАБОТАЛО!!! ОГРОМНОЕ СПАСИБО!!!
C++
1
2
3
4
5
6
7
8
9
10
11
12
binary_tree_node* f(int v)                          /////////////////////////поиск                  
{
    if (m_value == v)
    return this;
    else
    {
        if (m_left != 0)
        m_left->f(v);
        if (m_right != 0)
            m_right->f(v);
    }
}
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
void del(int v)
{
        binary_tree_node* p = new binary_tree_node;
        p = f(v);
    if (m_left == p)
    {
        binary_tree_node* p1 = new binary_tree_node;
            p1 = m_left;
        if (m_left)
        {
            p1->m_right = p1->m_left;
                m_left = p1->m_right;
        }
        else 
                {
                p1->m_left = p1->m_right;
            m_left = p1->m_left;
        }
         }
         else 
    {
        binary_tree_node* p1 = new binary_tree_node;
            p1 = m_right;
        if (m_left)
        {
            p1->m_right = p1->m_left;
            m_right = p1->m_right;
        }
        else
                {
                p1->m_left = p1->m_right;
            m_right = p1->m_left;
                }
    }
}
volovzi
266 / 168 / 8
Регистрация: 14.03.2010
Сообщений: 501
05.12.2010, 23:05     Написать класс, описывающий дерево #14
velodro, сомнительно. Поиск выдаёт правильный результат только в том случае, когда искомый элемент попадается сразу. А в удалении я вообще не понял, что происходит.
velodro
72 / 1 / 1
Регистрация: 28.11.2009
Сообщений: 78
06.12.2010, 01:31  [ТС]     Написать класс, описывающий дерево #15
да я чё то тоже потестировал - расстроился - написал такое. стало легче, но всё равно глючит...
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
void del(int v)
{
        binary_tree_node* p = new binary_tree_node;
        p = f(v);
        if (m_left == p)
        {
                
                binary_tree_node* p1 = new binary_tree_node;
                p1 = m_left;
                if (m_left)
                {
                        p1->m_left = p1->m_right;
                        m_left = p1->m_left;
                }
                else 
                {                                                
                        p1->m_right = p1->m_left;
                        m_left = p1->m_right;
                }
        }
    else
        if (m_right == p)
        {
                      binary_tree_node* p1 = new binary_tree_node;
                      p1 = m_right;
                      if (m_left)
                      {
                             p1->m_left = p1->m_right;
                     m_right = p1->m_left;
                      }
                      else
                      {
                    p1->m_right = p1->m_left;
                            m_right = p1->m_right;
                      }
                 }
         else
         {
            if (m_left != NULL)
                    m_left->del(v);
            else
                    m_right->del(v);
         }
}
Добавлено через 10 минут
volovzi, как проводить всю процедуру удаления производить из того узла, к которому подтягивать?
volovzi
266 / 168 / 8
Регистрация: 14.03.2010
Сообщений: 501
06.12.2010, 01:31     Написать класс, описывающий дерево #16
У тебя удаление использует неправильный поиск, так что начни с него.
velodro
72 / 1 / 1
Регистрация: 28.11.2009
Сообщений: 78
06.12.2010, 01:55  [ТС]     Написать класс, описывающий дерево #17
для проверки поиска написал дополнительно вот такую функцию в классе binary_tree_node:
C++
1
2
3
4
5
6
int ff(int v)
{
     binary_tree_node* p = new binary_tree_node;
     p = f(v);
     return p->m_value;
}
и вот такую в binary_tree:
C++
1
2
3
4
5
void find(int v)
{
    if (m_root != 0) 
    cout<<m_root->ff(v);
}
здесь всё работает правильно...

с чего вы взяли что проблема в поиске тоже есть?
volovzi
266 / 168 / 8
Регистрация: 14.03.2010
Сообщений: 501
06.12.2010, 02:40     Написать класс, описывающий дерево #18
velodro, проблема в том, что поиск возвращает результат только в том случае, если m_value == v, а в остальных случаях не возвращает ничего.

Должно быть примерно так:
C++
1
2
3
4
5
6
binary_tree_node * f (int v) {
        if (v == m_value) return this;
        else if (v < m_value && m_left != 0) return m_left->f(v);
        else if (v > m_value && m_right != 0) return m_right->f(v);
        else return 0;
}
Замечание, не относящееся к деревьям: ты неправильно используешь оператор "new". Он используется только тогда, когда тебе нужно выделить память под новый объект. И потом ты обязан удалить выделенную память оператором "delete". Если же ты используешь указатель как псевдоним другого объекта (как в функции "ff"), то выделять память не нужно. Пиши просто
C++
1
 binary_tree_node * p = f(v);
Добавлено через 5 минут
Я сейчас подумал, и понял, что если ты собираешься удалять узел с помощью найденного указателя на него, то тебе нужно в узле создать дополнительную переменную, в которой будет храниться указатель на родительский узел. Иначе просто не получится.

Добавлено через 15 минут
Подумал ещё раз.
Нет, всё-таки удалять узел надо из более высокого уровня, т.к. если узел не имеет родительского, то удалить сам себя не сможет.
velodro
72 / 1 / 1
Регистрация: 28.11.2009
Сообщений: 78
07.12.2010, 22:58  [ТС]     Написать класс, описывающий дерево #19
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
binary_tree_node * f (int v)
{
    if (v == m_value) return this;
    else if (v < m_value && m_left != 0) return m_left->f(v);
    else if (v > m_value && m_right != 0) return m_right->f(v);
    else return 0;
}
binary_tree_node* fdel(binary_tree_node* p2,binary_tree_node* p)
{
    if ((p2->m_left == p) || (p2->m_right == p))
                return p2;
    if ((p2->m_left != p) && (p2->m_right != p))
    {
        if (p2->m_left != NULL)
            return fdel(p2->m_left,p);
        else
            return fdel(p2->m_right,p);
    }
}               
void del(int v)
{
    binary_tree_node* p;
        p = f(v);
        binary_tree_node* p2;
        p2 = fdel(this,p);
 
    if (p2->m_left == p)
        {
        binary_tree_node* p1;
        p1 = p2->m_left;
 
                if (p1->m_left != NULL)
                {
                p1->m_right = p1->m_left;
                p2->m_left = p1->m_right;
            }   
            else
            {
                    p1->m_left = p1->m_right;
                p2->m_left = p1->m_right;
        }
        }
    if (p2->m_right == p)
        {
        binary_tree_node* p1;
                p1 = p2->m_right;
                
                if (p1->m_left != NULL)
                {
            p1->m_right = p1->m_left;
            p2->m_right = p1->m_right;
        }
        else
        {
            p1->m_left = p1->m_right;
            p2->m_right = p1->m_right;
        }
        }
}
осталось сделать обработку крайних.. Спасибо Вам большое! =)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.12.2010, 06:00     Написать класс, описывающий дерево
Еще ссылки по теме:

C++ Написать класс, описывающий эллипс
Создать класс,описывающий треугольник C++
C++ Класс, описывающий вектор в пространстве

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

Или воспользуйтесь поиском по форуму:
lemegeton
08.12.2010, 06:00     Написать класс, описывающий дерево
  #20

Не по теме:

Цитата Сообщение от velodro Посмотреть сообщение
... написать простейший класс, описывающий дерево.
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
// класс дерево
class Tree
{
public:
    bool is_peed;
    Tree() { is_peed = false; };
};
 
// класс, описывающий дерево
class Dog
{
public:
    void pee_on(Tree& a_tree)
    {
        a_tree.is_peed = true;
    }
};
 
void main()
{
    Dog dog;
    Tree oak;
 
    dog.pee_on(oak);
}

Yandex
Объявления
08.12.2010, 06:00     Написать класс, описывающий дерево
Ответ Создать тему
Опции темы

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