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

@velodro · Регистрация: 28.11.2009

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

Хочется понять, как написать простейший класс, описывающий дерево.
Компилирует данный код, но пишет пишет "ошибка сегментирования"

C++

#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).
Не плодите одинаковых тем.

@volovzi · 06.11.2010, 16:09

Ну, во-первых, у тебя неинициализирован указатель на объект "pp", поэтому при попытке вызова метода этого объекта произойдёт ошибка.
А во-вторых, функция "make" — это тихий ужас. Так нельзя работать с объектами.

@velodro · 06.11.2010, 16:36 **[ТС]**

а конструктор видели? или там нет инициализации по умолчанию? а на счёт функции make Ваш комметарий мягко говоря неинформативен хочется конкретики.. как бы Вы решели эту задачу?

@volovzi · 06.11.2010, 17:29

До вызова конструктора у тебя дело не доходит. Ты должен выделить память под объект прежде, чем его использовать.

C++

1	Tree *pp = new Tree;

Функция "make" ужасна тем, что работает с объектом "снаружи" являясь при этом его методом.
Вместо неё нужно сделать функцию "insert", которая добавляет в уже существующее дерево новый элемент.

@velodro · 06.11.2010, 21:34 **[ТС]**

действительно, память не выделилась.. спасибо! это мой косяк!
может так?

C++

1	pp = new Tree;

я так понимаю это должно быть внутри make?
а разве make не добавляет новые эл-ты?
как тогда выглядеть функция insert?

@volovzi · 06.11.2010, 22:14

velodro, метод класса, принимающий указатель на объект, методом которого он является — это бессмыслица.
Вот пример, как делать можно:

C++

#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 · 06.11.2010, 23:27 **[ТС]**

а вот в 51 строке слово const это к чему?

@volovzi · 06.11.2010, 23:48

velodro, это значит, что метод не модифицирует экземпляр своего класса. Помогает отлавливать большее число ошибок на этапе компиляции.

@velodro · 04.12.2010, 22:28 **[ТС]**

а как в таком дереве организовать удаление? поиск мне удался

.

@volovzi · 05.12.2010, 13:12

Самый простой способ — левая ветвь удаляемого элемента вставляется в правую, а правая поттягивается на его место.

@velodro · 05.12.2010, 18:04 **[ТС]**

а как взять то к чему подтягивать.. создать поле с идентификационными номерами, расположенными по порядку, и искать предыдущий по ним?

@volovzi · 05.12.2010, 18:10

velodro, нет, просто всю процедуру удаления производить из того узла, к которому подтягивать.

@velodro · 05.12.2010, 19:40 **[ТС]**

вот такую штуку написал и ЗАРАБОТАЛО!!! ОГРОМНОЕ СПАСИБО!!!

C++

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++

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 · 05.12.2010, 23:05

velodro, сомнительно. Поиск выдаёт правильный результат только в том случае, когда искомый элемент попадается сразу. А в удалении я вообще не понял, что происходит.

@velodro · 06.12.2010, 01:31 **[ТС]**

да я чё то тоже потестировал - расстроился - написал такое. стало легче, но всё равно глючит...

C++

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 · 06.12.2010, 01:31

У тебя удаление использует неправильный поиск, так что начни с него.

@velodro · 06.12.2010, 01:55 **[ТС]**

для проверки поиска написал дополнительно вот такую функцию в классе binary_tree_node:

C++

int ff(int v)
{
     binary_tree_node* p = new binary_tree_node;
     p = f(v);
     return p->m_value;
}

и вот такую в binary_tree:

C++

void find(int v)
{
    if (m_root != 0) 
    cout<<m_root->ff(v);
}

здесь всё работает правильно...

с чего вы взяли что проблема в поиске тоже есть?

@volovzi · 06.12.2010, 02:40

velodro, проблема в том, что поиск возвращает результат только в том случае, если m_value == v, а в остальных случаях не возвращает ничего.

Должно быть примерно так:

C++

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 · 07.12.2010, 22:58 **[ТС]**

C++

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;
        }
        }
}

осталось сделать обработку крайних.. Спасибо Вам большое! =)

@lemegeton · 08.12.2010, 06:00

Не по теме:

Сообщение от velodro

... написать простейший класс, описывающий дерево.

C++

// класс дерево
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);
}

@volovzi 274 / 175 / 12 Регистрация: 14.03.2010 Сообщений: 501
	06.11.2010, 16:09	2
	Ну, во-первых, у тебя неинициализирован указатель на объект "pp", поэтому при попытке вызова метода этого объекта произойдёт ошибка. А во-вторых, функция "make" — это тихий ужас. Так нельзя работать с объектами. 0

@velodro 72 / 1 / 3 Регистрация: 28.11.2009 Сообщений: 78
	06.11.2010, 16:36 [ТС]	3
	а конструктор видели? или там нет инициализации по умолчанию? а на счёт функции make Ваш комметарий мягко говоря неинформативен хочется конкретики.. как бы Вы решели эту задачу? 0

@velodro 72 / 1 / 3 Регистрация: 28.11.2009 Сообщений: 78
	06.11.2010, 23:27 [ТС]	7
	а вот в 51 строке слово const это к чему? 0

@volovzi 274 / 175 / 12 Регистрация: 14.03.2010 Сообщений: 501
	06.11.2010, 23:48	8
	velodro, это значит, что метод не модифицирует экземпляр своего класса. Помогает отлавливать большее число ошибок на этапе компиляции. 1

@velodro 72 / 1 / 3 Регистрация: 28.11.2009 Сообщений: 78
	04.12.2010, 22:28 [ТС]	9
	а как в таком дереве организовать удаление? поиск мне удался. 0

@volovzi 274 / 175 / 12 Регистрация: 14.03.2010 Сообщений: 501
	05.12.2010, 13:12	10
	Самый простой способ — левая ветвь удаляемого элемента вставляется в правую, а правая поттягивается на его место. 1

@velodro 72 / 1 / 3 Регистрация: 28.11.2009 Сообщений: 78
	05.12.2010, 18:04 [ТС]	11
	а как взять то к чему подтягивать.. создать поле с идентификационными номерами, расположенными по порядку, и искать предыдущий по ним? 0

@volovzi 274 / 175 / 12 Регистрация: 14.03.2010 Сообщений: 501
	05.12.2010, 18:10	12
	velodro, нет, просто всю процедуру удаления производить из того узла, к которому подтягивать. 0

@volovzi 274 / 175 / 12 Регистрация: 14.03.2010 Сообщений: 501
	05.12.2010, 23:05	14
	velodro, сомнительно. Поиск выдаёт правильный результат только в том случае, когда искомый элемент попадается сразу. А в удалении я вообще не понял, что происходит. 0

@volovzi 274 / 175 / 12 Регистрация: 14.03.2010 Сообщений: 501
	06.12.2010, 01:31	16
	У тебя удаление использует неправильный поиск, так что начни с него. 0