VPF::Удаление узлов из бинарного дерева до даты, введен

Creder

Дата 9.5.2015, 15:05 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 16
Регистрация: 9.5.2015

Репутация: нет
Всего: нет

Здравствуйте. Такой вопрос.

Используя классы, создать упорядоченное бинарное дерево, которое описывает справочник файлов в файловой системе. Каждому узлу соответствует некоторый файл , в узле содержится имя файла и дата последнего обращения к нему. Узлов в дереве не менее 15. Реализовать функцию, которая удаляет из дерева все файлы(узлы), обращение к которому было произведено до даты, введённой с клавиатуры. Исходное и результирующее дерево вывести на экран.

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

Код


include <iostream>
 
using namespace std;
 
class Tree
{
    struct Node
    {
        Node* left;
        Node* right;
        char name;
        int day;
        int month;
        int year;
    };
    Node* root;
    void print1(Node*);
 public:
     Tree()
     {
         root=0;
     }
     bool isEmptry() const { return root==0; }
     void add_node(char name, int d, int m, int y);
     void print();
     void del_node(char name, int d, int m, int y);
 
 
 
 
};
 
void Tree::add_node(char name, int day, int month, int year)
{
    Node* t=new Node;
    Node* parent;
    t->name=name;
    t->day=day;
    t->month=month;
    t->year=year;
    t->left=0;
    t->right=0;
    parent=0;
 
    if (isEmptry()) root=t;
    else
    {
        Node* curr;
        curr=root;
 
        while(curr)
        {
            parent=curr;
            if(t->name > curr->name) curr=curr->right;
            else curr=curr->left;
        }
 
        if(t->name < parent->name)
            parent->left=t;
        else
            parent->right=t;
    }
}
 
void Tree::print()
{
    print1(root);
}
 
void Tree::print1(Node* p)
{
    if(p != 0)
    {
        cout<<" "<<p->name<<" "<< p->day << "." << p->month << "." << p->year << endl;
        if(p->left) print1(p->left);
        if(p->right) print1(p->right);
    }
    else return;
}

int main()
{
    Tree c;
    setlocale(0, "");
    char name;
    int i,n, d, m, y;

    cout << "Введите кол-во файлов" << endl;
    cin >> n;
    for(i=0; i<n; i++)
        {
        cout << "Имя файла: " << endl;
        cin >> name;
        cout << "День: " << endl;
        cin >> d;
        cout << "Месяц: " << endl;
        cin >> m;
        cout << "Год: " << endl;
        cin >> y;
        c.add_node(name, d, m, y);
        }


    c.print();
    cout << endl;


    return 0;
}

feodorv

Дата 9.5.2015, 16:59 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45

Цитата(Creder @ 9.5.2015, 15:05

)

Проблема заключается в создании функции удаления тех самых узлов

Помимо этой проблемы в приведённой программе есть ещё. Например:

Цитата(Creder @ 9.5.2015, 15:05

)

    struct Node
    {
        Node* left;
        Node* right;
        char name;
        int day;
        int month;
        int year;
    };

char name - это один единственный символ, никак не имя файла (которое есть набор символов). Чтобы не возиться с выделением/высвобождением памяти, можно жёстко задать максимальный размер имени файла:

Код

char name[256];

но тогда нужно следить, чтобы не переполнить этот буфер. Либо все же:

Код

char *name;

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

Соответственно, тогда простые сравнения уже не годятся:

Цитата(Creder @ 9.5.2015, 15:05

)

if(t->name > curr->name) curr=curr->right;

Цитата(Creder @ 9.5.2015, 15:05

)

if(t->name < parent->name)

А нужно будет сравнение именно строк. В идеале, конечно, хотелось бы увидеть применение класса std::string.

Далее. В add_node Вы в цикле поиска узла сравниваете так:

Цитата(Creder @ 9.5.2015, 15:05

)

if(t->name > curr->name) curr=curr->right;

а по окончании цикла уже так:

Цитата(Creder @ 9.5.2015, 15:05

)

if(t->name < parent->name)

Здесь проблема возникает, если t->name совпадает с parent->name, тогда Вы делаете присваивание не в ту ветку дерева (а она уже могла быть кем-то занята). Если же равенство имен файлов не допускается, то тогда Вам нужно мягко обойти эту ситуацию.

Цитата(Creder @ 9.5.2015, 15:05

)

Не знаю, что делать.

Распишите себе, что Вы будете делать в таких ситуациях:

у удаляемого узла дерева отсутствуют правый и левый узлы;
у удаляемого узла дерева отсутствуют правый или левый узел;
у удаляемого узла дерева есть и правый, и левый узлы.

И это всё с учётом того, что Вы совершаете удаление узла в момент обхода дерева. Особо нужно предусмотреть случай, когда Вы удаляете узел root.

Лучше всего удаление одного узла оформить в виде отдельной функции, в которую кроме указателя на удаляемый узел передавать и предка этого узла (для root это будет 0, так как у него нет предка).

А ещё можно поинтересоваться сбалансированными бинарными деревьями, например, Red-Black-Tree)

--------------------

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

Creder

Дата 11.5.2015, 20:35 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 16
Регистрация: 9.5.2015

Репутация: нет
Всего: нет

Я особо не силен в этом. Кое-что нашел в интернете. Подойдет ли это? И если да, то как модифицировать это под мое задание?

Код


        void BinarySearchTree<T>::remove(T d)
{
    bool found = false;
    if(isEmpty())
    {
        cout<<" This Tree is empty! "<<endl;
        return;
    }
    tree_node* curr;
    tree_node* parent;
    curr = root;
    parent = (tree_node*)NULL;
    while(curr != NULL)
    {
        if(curr->data == d)
        {
            found = true;
            break;
        }
        else
        {
            parent = curr;
            if(d>curr->data) curr = curr->right;
            else curr = curr->left;
        }
    }
    if(!found)
    {
        cout<<" Data not found! "<<endl;
        return;
    }

    // Node with single child
    if((curr->left == NULL && curr->right != NULL)|| (curr->left != NULL
        && curr->right == NULL))
    {
        if(curr->left == NULL && curr->right != NULL)
        {            
            if(parent->left == curr)
            {
                parent->left = curr->right;
                delete curr;
            }
            else
            {
                parent->right = curr->right;
                delete curr;
            }
        }
        else // left child present, no right child
        {
            if(parent->left == curr)
            {
                parent->left = curr->left;
                delete curr;
            }
            else
            {
                parent->right = curr->left;
                delete curr;
            }
        }
        return;
    }

    //We're looking at a leaf node
    if( curr->left == NULL && curr->right == NULL)
    {
        if (parent == NULL)
        {
            delete curr;

        } else
            if(parent->left == curr) parent->left = NULL;
            else parent->right = NULL;
            delete curr;
            return;
    }


    //Node with 2 children
    // replace node with smallest value in right subtree
    if (curr->left != NULL && curr->right != NULL)
    {
        tree_node* chkr;
        chkr = curr->right;
        if((chkr->left == NULL) && (chkr->right == NULL))
        {
            curr = chkr;
            delete chkr;
            curr->right = NULL;
        }
        else // right child has children
        {
            //if the node's right child has a left child
            // Move all the way down left to locate smallest element

            if((curr->right)->left != NULL)
            {
                tree_node* lcurr;
                tree_node* lcurrp;
                lcurrp = curr->right;
                lcurr = (curr->right)->left;
                while(lcurr->left != NULL)
                {
                    lcurrp = lcurr;
                    lcurr = lcurr->left;
                }
                curr->data = lcurr->data;
                delete lcurr;
                lcurrp->left = NULL;
            }
            else
            {
                tree_node* tmp;
                tmp = curr->right;
                curr->data = tmp->data;
                curr->right = tmp->right;
                delete tmp;
            }

        }
        return;
    }

}

Здесь, вроде, соблюдаются все 3 условия удаления узла из дерева.

Это сообщение отредактировал(а) Creder - 11.5.2015, 20:43

feodorv

Дата 11.5.2015, 21:07 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45

Цитата(Creder @ 11.5.2015, 20:35

)

Подойдет ли это?

За основу - да. Но очень много ошибок в найденном коде...

Вы в Вашем коде избегаете употребления NULL. Для C++ это правильный подход, в найденный же код изобилует NULL'ами.
В найденном коде совершенно забыт случай, когда удаляется узел root. В этом случае основанием дерева должен стать какой-то другой узел (то есть нужно присвоение root = ...), этого не делается.
Вам нет нужды искать узел в дереве, содержащий искомые данные. На момент принятия решения об удалении какого-либо узла из дерева Вы будете уже обладать указателями на сам удаляемый узел и его предка.

Тщательно следите за пропущенными скобками:

Цитата(Creder @ 11.5.2015, 20:35

)

    if( curr->left == NULL && curr->right == NULL)
    {
        if (parent == NULL)
        {
            root = 0;
            delete curr;
        } else
        {
            if(parent->left == curr) parent->left = NULL;
            else parent->right = NULL;
            delete curr;
        }
            return;
    }

В случае
Цитата(Creder @ 11.5.2015, 20:35 )
if (curr->left != NULL && curr->right != NULL)

с недопустимой легкостью удаляются какие-то другие узлы вместо текущего, это не правильно. Более того, я не уверен и в правильности алгоритма для этой ветви. Я бы все перепроверил...

--------------------

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

Creder

Дата 14.5.2015, 10:06 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 16
Регистрация: 9.5.2015

Репутация: нет
Всего: нет

А если попробовать как-то так?

Код


void Tree::deleteNode(Node* n)
{
    if( (n->left == n->right) && (n->left == 0) )
    {
        delete n;
        return ;
    }
    else
    //    левое поддерево пусто
    if( n->left == 0 )
    {
        //    сохраняем указатель на правое поддерево
        Node* r = n->right;
        //    копируем состояние узла находящегося справа
        *n = *r;
        //    удаляем узел
        r->left = 0;
        r->right = 0;
        delete r;
    }
    else
    //    левое поддерево не пусто
    {
        //    ищем узел являющийся самым правым в левом поддереве
        //    самый правый узел
        Node *c = n->left;
        //    родитель самого правого узла
        Node *p = n->left;

        //    двигаемся по правой ветви левого поддерева
        while( c->right )
        {
            p = c;
            c = c->right;
        }

        //    левое поддерево самого правого узла становиться правым поддеревом родителя
        p->right = c->left;
        //    рвем отношение
        c->left = NULL;
        //    переносим ключ
        n->name = c->name;
        n->day = c->day;
        n->month = c->month;
        n->year = c->year;
        //    удаляем самый правый узел
        delete c;
    }
    return n;
}

void Tree:: removeNode(Node *n, int day, int month, int year)
{
    //    если достигли листа, то узла с данным ключем не существует
    if( n == 0 )
        return 0;
    //    если ключ текущего узла меньше искомого
    if( n->year <= year )
    {
        if(n->day <= day || n->month <= month)
        {
            deleteNode(n);
            n->right = removeNode(n->right, day, month, year);
            return n;
        }
        else
        {
           n->right = removeNode(n->left, day, mont, year);
        }
            n->right = removeNode(n->right, day, mont, year);
            return n;
    }
    else
    //    если ключ текущего узла больше искомого
    if( year < n->year )
    {
        //    идем по левой ветке
        n->left = removeNode(n->left, day, month, year);
        return n;
    }
}

Это сообщение отредактировал(а) Creder - 15.5.2015, 15:58

Creder

Дата 15.5.2015, 16:18 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 16
Регистрация: 9.5.2015

Репутация: нет
Всего: нет

Код


#include <iostream>
#include <cstdlib>
using namespace std;

struct Node
    {
        Node* left;
        Node* right;
        char name;
        int day;
        int month;
        int year;
    };


class Tree
{

    Node* root;
    void print1(Node*);
 public:
     Tree()
     {
         root=0;
     }
     bool isEmpty() const { return root==0; }
     bool searchNode(char);
     void add_node(char , int, int, int);
     void deleteNode(Node*);
     void removeNode(Node* , int, int, int);
     void print();




};

void Tree::add_node(char name, int day, int month, int year)
{
    Node* t=new Node;
    t->name=name;
    t->day=day;
    t->month=month;
    t->year=year;
    t->left=0;
    t->right=0;

    if (isEmpty()) root=t;
    else
    {
        Node* curr;
        curr=root;

        while(curr)
        {
            if(t->name > curr->name) curr=curr->right;
            else curr=curr->left;
        }

        if(t->name < curr->name)
            curr->left=t;
        else
            curr->right=t;
    }
}

void Tree::deleteNode(Node* n)
{
    if( (n->left == n->right) && (n->left == 0) )
    {
        delete n;
        return ;
    }
    else
    //    левое поддерево пусто
    if( n->left == 0 )
    {
        //    сохраняем указатель на правое поддерево
        Node* r = n->right;
        //    копируем состояние узла находящегося справа
        *n = *r;
        //    удаляем узел
        r->left = 0;
        r->right = 0;
        delete r;
    }
    else
    //    левое поддерево не пусто
    {
        //    ищем узел являющийся самым правым в левом поддереве
        //    самый правый узел
        Node *c = n->left;
        //    родитель самого правого узла
        Node *p = n->left;

        //    двигаемся по правой ветви левого поддерева
        while( c->right )
        {
            p = c;
            c = c->right;
        }

        //    левое поддерево самого правого узла становиться правым поддеревом родителя
        p->right = c->left;
        //    рвем отношение
        c->left = NULL;
        //    переносим ключ
        n->name = c->name;
        n->day = c->day;
        n->month = c->month;
        n->year = c->year;
        //    удаляем самый правый узел
        delete c;
    }
    return;
}

void Tree:: removeNode(Node* n, int day, int month, int year)
{
    //    если достигли листа, то узла с данным ключем не существует
    if( n == 0 )
        return;
    //    если ключ текущего узла меньше искомого
    if( n->year <= year )
    {
        if(n->day <= day || n->month <= month)
        {
            deleteNode(n);
            n->right = removeNode(n->right, day, month, year);
            return;
        }
        else
        {
           n->right = removeNode(n->left, day, month, year);
        }
            n->right = removeNode(n->right, day, month, year);
            return;
    }
    else
    //    если ключ текущего узла больше искомого
    if( year < n->year )
    {
        //    идем по левой ветке
        n->left = removeNode(n->left, day, month, year);
        return;
    }
}

void Tree::print()
{
    print1(root);
}

void Tree::print1(Node* p)
{
    if(p != 0)
    {
        cout<< p->name <<" "<< p->day << "." << p->month << "." << p->year << endl;
        if(p->left) print1(p->left);
        if(p->right) print1(p->right);
    }
    else return;
}

int main()
{
    Tree c;
    Node *v=new Node;
    setlocale(0, "");
    char name;
    int i,n, d, m, y;

    cout << "Введите кол-во файлов" << endl;
    cin >> n;
    for(i=0; i<n; i++)
        {
        cout << "Имя файла: " << endl;
        cin >> name;
        cout << "День: " << endl;
        cin >> d;
        cout << "Месяц: " << endl;
        cin >> m;
        cout << "Год: " << endl;
        cin >> y;
        c.add_node(name, d, m, y);
        }


    c.print();
    cout << endl;
    cout << "Введите дату:" << endl;
    cout << "День: " << endl;
    cin >> d;
    cout << "Месяц: " << endl;
    cin >> m;
    cout << "Год: " << endl;
    cin >> y;

    c.removeNode(v, d, m, y);
    c.print();

    return 0;
}

feodorv

Дата 15.5.2015, 19:55 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45

Цитата(Creder @ 15.5.2015, 16:18

)

Что не так?

Функция removeNode не возвращает значения:

Цитата(Creder @ 15.5.2015, 16:18

)

void Tree:: removeNode(Node* n, int day, int month, int year)

поэтому присвоить чему-то возвращаемый результат работы функции (а его попросту нет) не удасться:

Цитата(Creder @ 15.5.2015, 16:18

)

n->right = removeNode(n->right, day, month, year);

--------------------

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

Creder

Дата 18.5.2015, 09:10 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 16
Регистрация: 9.5.2015

Репутация: нет
Всего: нет

Код


#include <iostream>
#include <cstdlib>
#include "Tree.h"
using namespace std;

struct Node
    {
        Node* left;
        Node* right;
        char name;
        int day;
        int month;
        int year;
    };


class Tree
{

    Node* root;
    void print1(Node*);
    Node* deleteNode(Node*);
 public:
     Tree()
     {
         root=0;
     }
     bool isEmpty() const { return root==0; }
     bool searchNode(char);
     void add_node(Node*, char, int, int, int);
     Node* removeNode(Node*, int, int, int);
     void print();




};

void Tree::add_node(Node* t, char name, int day, int month, int year)
{
    t->name=name;
    t->day=day;
    t->month=month;
    t->year=year;
    t->left=0;
    t->right=0;

    if (isEmpty()) root=t;
    else
    {
        Node* curr;
        curr=root;

        while(curr)
        {
            if(t->name > curr->name) curr=curr->right;
            else curr=curr->left;
        }

        if(t->name < curr->name)
            curr->left=t;
        else
            curr->right=t;
    }
}

Node* Tree::deleteNode(Node* n)
{
    if( (n->left == n->right) && (n->left == 0) )
    {
        delete n;
        return 0;
    }
    else
    //    левое поддерево пусто
    if( n->left == 0 )
    {
        //    сохраняем указатель на правое поддерево
        Node* r = n->right;
        //    копируем состояние узла находящегося справа
        *n = *r;
        //    удаляем узел
        r->left = 0;
        r->right = 0;
        delete r;
    }
    else
    //    левое поддерево не пусто
    {
        //    ищем узел являющийся самым правым в левом поддереве
        //    самый правый узел
        Node *c = n->left;
        //    родитель самого правого узла
        Node *p = n->left;

        //    двигаемся по правой ветви левого поддерева
        while( c->right )
        {
            p = c;
            c = c->right;
        }

        //    левое поддерево самого правого узла становиться правым поддеревом родителя
        p->right = c->left;
        //    рвем отношение
        c->left = NULL;
        //    переносим ключ
        n->name = c->name;
        n->day = c->day;
        n->month = c->month;
        n->year = c->year;
        //    удаляем самый правый узел
        delete c;
    }
    return n;
}

Node* Tree:: removeNode(Node* n, int day, int month, int year)
{
    //    если достигли листа, то узла с данным ключем не существует
    if( n == 0 )
        return 0;
    //    если ключ текущего узла меньше искомого
    if( n->year <= year )
    {
        if(n->day <= day || n->month <= month)
        {
            deleteNode(n);
            n->right = removeNode(n->right, day, month, year);
            return n;
        }
        else
        {
           n->right = removeNode(n->left, day, month, year);
        }
            n->right = removeNode(n->right, day, month, year);
            return n;
    }
    else
    //    если ключ текущего узла больше искомого
    if( year < n->year )
    {
        //    идем по левой ветке
        n->left = removeNode(n->left, day, month, year);
        return n;
    }
}

void Tree::print()
{
    print1(root);
}

void Tree::print1(Node* p)
{
    if(p != 0)
    {
        cout<< p->name <<" "<< p->day << "." << p->month << "." << p->year << endl;
        if(p->left) print1(p->left);
        if(p->right) print1(p->right);
    }
    else return;
}

int main()
{
    Tree c;
    Node* v=new Node;
    setlocale(0, "");
    char name;
    int i,n, d, m, y;

    cout << "Введите кол-во файлов" << endl;
    cin >> n;
    for(i=0; i<n; i++)
        {
        cout << "Имя файла: " << endl;
        cin >> name;
        cout << "День: " << endl;
        cin >> d;
        cout << "Месяц: " << endl;
        cin >> m;
        cout << "Год: " << endl;
        cin >> y;
        c.add_node(v, name, d, m, y);
        }


    c.print();
    cout << endl;
    cout << "Введите дату:" << endl;
    cout << "День: " << endl;
    cin >> d;
    cout << "Месяц: " << endl;
    cin >> m;
    cout << "Год: " << endl;
    cin >> y;

    c.removeNode(v, d, m, y);
    c.print();

    return 0;
}

Теперь при создании дерева программа стала вылетать. Где ошибка?

feodorv

Дата 18.5.2015, 10:03 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45

Цитата(Creder @ 18.5.2015, 09:10

)

if( (n->left == n->right) && (n->left == 0) )

Знакомое условие. В чем его смысл? Почему оно записано именно в таком дурацком виде?

Девушка из соседней ветки, в которой решена задача, аналогичной Вашей, по этому поводу написала так:

Цитата(lenarano @ 14.5.2015, 15:05

)

я этот алгоритм нашла в нете, просто пробовала адаптировать к моему куску кода

Чтобы адаптировать чужой код, нужно хотя бы разобраться, что он делает, какой вкладывается смысл в возвращаемые значения, как код работает в особых случаях (например, при удалении корня дерева) и т.д.

Цитата(Creder @ 18.5.2015, 09:10

)

при создании дерева

Ну посмотрите на то, как Вы вставляете новый узел в дерево:

Цитата(Creder @ 18.5.2015, 09:10

)

int main()
{
    Node* v=new Node;
    ...
    for(i=0; i<n; i++)
        {
        ....
        c.add_node(v, name, d, m, y);
        }

new Node находится за пределами цикла, то есть все добавляемые узлы представляют собой один единственный экземпляр структуры Node
у нового узла не инициализируются нулями поля left и right
для нового узла все вводимые с клавиатуры данные name, d, m, y - по барабану (они никак не участвуют в создании нового узла)
в функции add_node не используются аргументы name, d, m, y; зачем вообще они передаются в эту фенкцию?
name как был char, так и остался((((

--------------------

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

Creder

Дата 18.5.2015, 13:29 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 16
Регистрация: 9.5.2015

Репутация: нет
Всего: нет

Хорошо. Переписал. Но все равно вылетает ошибка. Что опять не так?

Код


for(i=0; i<n; i++)
        {
        Node* node=new Node;
        cout << "Имя файла: " << endl;
        cin >> name;
        cout << "День: " << endl;
        cin >> d;
        cout << "Месяц: " << endl;
        cin >> m;
        cout << "Год: " << endl;
        cin >> y;
        tree.add_node(node);
        }

Может, где-то напортачил в самой функции добавления узла?

Код


void Tree::add_node(Node *t)
{

    if (isEmpty()) root=t;
    else
    {
        Node* curr;
        curr=root;

        while(curr)
        {
            if(t->name >= curr->name) curr=curr->right;
            else curr=curr->left;
        }

        if(t->name < curr->name)
            curr->left=t;
        else
            curr->right=t;
    }
}

Это сообщение отредактировал(а) Creder - 18.5.2015, 13:53

feodorv

Дата 18.5.2015, 21:32 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45

Цитата(Creder @ 18.5.2015, 13:29

)

Что опять не так?

Хорошо, что создание узла Вы внесли в цикл добавления. Теперь у Вас добавляются разве экземпляры узла. Но данные для этого узла, вводимые с клавиатуры, до узла не доходят. Узел добавляется в дерево в отрыве от этих данных. Более того, конструктор по умолчанию у Node отсутствует, поля у вновь создаваемого Node остаются неинициализированными.

В C++ есть же прекрасная возможность создания экземпляра класса сразу с инициализирующими значениями - конструктор класса. Почему Вы ей не пользуетесь?

Код


for(i=0; i<n; i++)
        {
        cout << "Имя файла: " << endl;
        cin >> name;
        cout << "День: " << endl;
        cin >> d;
        cout << "Месяц: " << endl;
        cin >> m;
        cout << "Год: " << endl;
        cin >> y;
        Node* node=new Node( name, d, m, y);
        tree.add_node(node);
        }

Цитата(Creder @ 18.5.2015, 13:29

)

Может, где-то напортачил в самой функции добавления узла?

Да. Отбросив тот факт, что Вы сравниваете неинициализированные данные (то есть мусор), мы выясняем, что по окончании цикла curr есть 0. Если потом делать curr->name, curr->left, curr->right, то это значит сознательный крах программы.

Это сообщение отредактировал(а) feodorv - 18.5.2015, 21:33

--------------------

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

Creder

Дата 18.5.2015, 23:21 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 16
Регистрация: 9.5.2015

Репутация: нет
Всего: нет

Т. е. сначала, мне надо это

Код


struct Node
    {
        Node* left;
        Node* right;
        string name;
        int day;
        int month;
        int year;
    };

сделать, э-э-э, так или как-то иначе?

Код


class Node
{
protected:
  Node *left, *right;
  string name;
  int day;
  int month;
  int year;

public:

  Node(string name, int day, int month, int year) {}

  friend class Tree;
};

Это сообщение отредактировал(а) Creder - 18.5.2015, 23:33

feodorv

Дата 19.5.2015, 00:22 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45

Цитата(Creder @ 18.5.2015, 23:21

)

сделать, э-э-э, так или как-то иначе?

Можно и так, но параметры-то конструктора должны же быть использованы для инициализации, да и left и right нужно занулить:

Код


  Node(const string &n, int d, int m, int y) : name(n), day(d), month(m), year(y), left(0), right(0) {}

Если Вам не нравится такая форма конструктора, когда поля класса инициализируются до тела конструктора, а само тело конструктора пустое, используйте другой (пусть и худший) подход к конструктору:

Код


  Node(const string &n, int d, int m, int y)
  { 
    name = n;
    day = d;
    month = m;
    year = y;
    left = 0;
    right = 0;
  }

Тогда все поля вновь создаваемого экземпляра класса будут правильно проинициализированы.

PS Для имени файла при передаче конструктору используется ссылка и квалификатор const.
PSS Имена аргументов конструктора изменены таким образом, чтобы они не совпадали с именами полей класса.

--------------------

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

Creder

Дата 19.5.2015, 14:36 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 16
Регистрация: 9.5.2015

Репутация: нет
Всего: нет

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

feodorv

Дата 19.5.2015, 21:47 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45

Цитата(Creder @ 19.5.2015, 14:36

)

Что же, с добавлением узла я все таки разобрался, но я все так же не могу понять, как удалять узел.

Гм. Простите мне мою лень, но второй раз описывать уже описанное не хочется. В соседней ветке всё есть, может не разжевано до конца, до очень много комментариев и пояснений, сделанных в том числе и для Вас. Вам только нужно изменить условие, при котором узел удаляется из дерева. smile

--------------------

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »