Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Для новичков > Удаление узлов из бинарного дерева до даты, введен

Автор: Creder 9.5.2015, 15:05

Здравствуйте. Такой вопрос. Используя классы, создать упорядоченное бинарное дерево, которое описывает справочник файлов в файловой системе. Каждому узлу соответствует некоторый файл , в узле содержится имя файла и дата последнего обращения к нему. Узлов в дереве не менее 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

Цитата(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, так как у него нет предка). А ещё можно поинтересоваться сбалансированными бинарными деревьями, например, https://ru.wikipedia.org/wiki/%CA%F0%E0%F1%ED%EE-%F7%B8%F0%ED%EE%E5_%E4%E5%F0%E5%E2%EE)

Автор: Creder 11.5.2015, 20:35

Я особо не силен в этом. Кое-что нашел в интернете. Подойдет ли это? И если да, то как модифицировать это под мое задание? Код         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 условия удаления узла из дерева.

Автор: feodorv 11.5.2015, 21:07

Цитата(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

А если попробовать как-то так? Код 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, 16:18

Код #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; } В общем, попытался сделать вот так, но компилятор выдает ошибки такого рода: |129|error: void value not ignored as it ought to be| |134|error: void value not ignored as it ought to be| |136|error: void value not ignored as it ought to be| |144|error: void value not ignored as it ought to be| Что не так?

Автор: feodorv 15.5.2015, 19:55

Цитата(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

Код #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

Цитата(Creder @  18.5.2015,  09:10 )     if( (n->left == n->right) && (n->left == 0) ) Знакомое условие. В чем его смысл? Почему оно записано именно в таком дурацком виде? Девушка из http://forum.vingrad.ru/forum/topic-383329.html, в которой решена задача, аналогичной Вашей, по этому поводу написала так: Цитата(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

Хорошо. Переписал. Но все равно вылетает ошибка. Что опять не так? Код 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;     } }

Автор: feodorv 18.5.2015, 21:32

Цитата(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 ) Может, где-то напортачил в самой функции добавления узла? Да. Отбросив тот факт, что Вы сравниваете неинициализированные данные (то есть мусор), http://forum.vingrad.ru/index.php?showtopic=383329&view=findpost&p=2639289, что по окончании цикла curr есть 0. Если потом делать curr->name, curr->left, curr->right, то это значит сознательный крах программы.

Автор: Creder 18.5.2015, 23:21

Т. е. сначала, мне надо это Код 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; };

Автор: feodorv 19.5.2015, 00:22

Цитата(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

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

Автор: feodorv 19.5.2015, 21:47

Цитата(Creder @  19.5.2015,  14:36 ) Что же, с добавлением узла я все таки разобрался, но я все так же не могу понять, как удалять узел. Гм. Простите мне мою лень, но второй раз описывать уже http://forum.vingrad.ru/index.php?showtopic=383329&view=findpost&p=2639249 не хочется. В соседней ветке всё есть, может не разжевано до конца, до очень много комментариев и пояснений, сделанных в том числе и для Вас. Вам только нужно изменить условие, при котором узел удаляется из дерева.

Автор: Creder 20.5.2015, 13:12

Похоже, это подойдет. Код void Tree::remove_node( Node *node, Node* parent) {     if( node->right == 0 && node->left == 0 )     {         if( parent == 0 )             root = 0;         else if( parent->left == node )                 parent->left = 0;             else                 parent->right = 0;     }     else if( node->right == 0 )     {         if( parent == 0 )             root = node->left;         else if( parent->left == node )             parent->left = node->left;         else             parent->right = node->left;     }     else if( node->left == 0 )     {         if( parent == 0 )             root = node->right;         else if( parent->left == node )             parent->left = node->right;         else             parent->right = node->right;     }     else     {         Node *c, *p = node;         for( c = node->right; c->left != 0; c = c->left) p = c;         if( p!= node )         {             p->left = c->right;             c->right = node->right;         }         c->left = node->left;         if( parent == 0 )             root = c;         else if( parent->left == node )                 parent->left = c;         else                 parent->right = c;     }     delete node; } Но правильно ли я ищу узлы? Код void Tree::search_node(Node* n, int day, int month, int year) {     if(n != 0)     {         if(n->year <= year)             {                 if(n->day <= day || n->month <= month)                     {                         remove_node(n, 0);                         search_node(n->left, day, month, year);                     }                 else                         search_node(n->right, day, month, year);             }         else if(n->year > year)             search_node(n->right, day, month, year);     }     else return; }

Автор: feodorv 21.5.2015, 03:33

Цитата(Creder @  20.5.2015,  13:12 ) Похоже, это подойдет. Похоже или подойдёт? Вы ту тему до конца читали? Цитата(Creder @  20.5.2015,  13:12 ) Но правильно ли я ищу узлы? Нет. Совершенно нет. В remove_node нужно отправлять указатель на предка удаляемого узла, у Вас это всегда - 0 (вне зависимости от n), что приведёт к порче структуры дерева. Рекурсивный поиск узлов на удаление в правой и левой ветке узла n должен происходить вне зависимости от значения года, месяца или дня. Условие, при котором узел должен быть удалён, реализовано в коде неверно. И снова вопрос: Вы ту тему до конца читали?

Автор: Creder 21.5.2015, 15:11

Насколько я понял, нужно создать логическую функцию проверки даты - передать в эту функцию записанную дату с клавиатуры и дату из узла и проверить их. Код bool Node::date() {  ... } Затем результат этой проверки использовать в этих функциях: Здесь Код void Tree::search_node( Node *node, Node *parent) {  ...     while( parent->left != 0 && !parent->left->date() )       remove( parent->left, parent); ...   else   {     while( parent->right != 0 && !parent->date() )       remove( parent->right, parent);  ...     }   } } и здесь Код void Tree::search_node() {   while( root != 0 && !root->date() ) remove_node( root, 0);   if( root != 0 )   {     search_node( root->left, root);     search_node( root->right, root);   } } А затем нужный узел удалить! Код void Tree::remove_node( Node *node, Node* parent) {     if( node->right == 0 && node->left == 0 )         parentFixup(parent, node, 0);     else if( node->right == 0 )         parentFixup(parent, node, node->left);     else if( node->left == 0 )         parentFixup(parent, node, node->right);     else     {         Node *c, *p = node;         for( c = node->right; c->left != 0; c = c->left) p = c;         if( p!= node )         {             p->left = c->right;             c->right = node->right;         }         c->left = node->left;         parentFixup(parent, node, c);     }     delete node; }

Автор: feodorv 21.5.2015, 22:28

Цитата(Creder @  21.5.2015,  15:11 ) Насколько я понял, нужно создать логическую функцию проверки даты - передать в эту функцию записанную дату с клавиатуры и дату из узла и проверить их. Можно и так. Только прототип функции проверки будет таким: Код bool Node::check( int d, int m, int y); либо таким: Код bool check( Node *n, int day, int month, int year); В последнем случае функция проверки не будет принадлежать классу Node. Цитата(Creder @  21.5.2015,  15:11 ) Затем результат этой проверки использовать в этих функциях: Да! Но от while'ов лучше отказаться, сначала проверив левую и правые ветви узла, а уже затем сам узел на удовлетворение условию. А так же придётся таскать за собой параметры проверки day, month, year.

Автор: Creder 22.5.2015, 20:38

Цитата(feodorv @ 21.5.2015,  22:28) Но от while'ов лучше отказаться, сначала проверив левую и правые ветви узла, а уже затем сам узел на удовлетворение условию. А так же придётся таскать за собой параметры проверки day, month, year. Извините. Не совсем понял. Можете по-подробнее объяснить?

Автор: feodorv 23.5.2015, 00:11

Ну, например: Код void Tree::search_node( int day, int month, int year) {   if( root != 0 )   {     search_node( root->left, root, day, month, year);     search_node( root->right, root, day, month, year);     if( !root->uptodate( day, month, year) ) remove_node( root, 0);   } }

Автор: Creder 25.5.2015, 10:09

Это же обратный обход дерева. Как я сразу не догадался? И последнее. Не могу разобраться с логической функцией. Мне приходит в голову только это: Код bool Node::date(int d, int m, int y) {   if(year <= y)   {       if(month <= m || day <= d)         return true;       else         return false;   }   return true; }

Автор: feodorv 25.5.2015, 16:42

Цитата(Creder @  25.5.2015,  10:09 ) Не могу разобраться с логической функцией. Давайте посмотрим на условие задачи: Цитата(Creder @  9.5.2015,  15:05 ) Реализовать функцию, которая удаляет из дерева все файлы(узлы), обращение к которому было произведено до даты, введённой с клавиатуры. То есть, если дата в узле меньше, то узел нужно удалить. Если больше или равна, то удалять не нужно. В своём коде Вы всё время пытаетесь удалить узел, если его дата меньше или равна, что неверно. Должен заметить, что проверочной функции стОит дать говорящее название. date() - это не о чем. Вот что должна делать функция с именем date()? А Бог его знает. Up-to-date - другое дело, можно даже is_uptoday() - является ли дата узла достаточно новой. Соответственно, эта функция будет возвращать true, если узел ещё актуален (его удалять не нужно) и false в случае устаревания узла (однозначно удалять). Понятие даты не совсем однозначно, оно может включать в себя помимо собственно дня (день месяца + номер месяца + год) ещё и суточное время (час + минута + секунда). Что здесь имеется в виду, лучше уточнить у препода. Сама проверка даты в том виде, в котором она присутствует в коде, не представляет никакого труда. Сначала нужно проверить год узла. Если он больше года введённой с клавиатуры даты, то узел - свежий, удалять не надо. Если меньше, то узел устарел, нужно удалять. Проблема возникает только в случае равенства годов, в таком случае нужно проверить месяц узла. Если он больше месяца введённой с клавиатуры даты, то узел - свежий, удалять не надо. Если меньше, то узел устарел, нужно удалять. Проблема возникает только в случае равенства и месяцев, в таком случае нужно проверить день узла. Если он больше или равен дня введённой с клавиатуры даты, то узел - свежий, удалять не надо. Если меньше, то узел устарел. Программно эта проверка вообще выглядит смешно: Код bool Node::is_uptodate( int d, int m, int y) {   if( year < y ) return false;   if( year > y ) return true;   if( month < m ) return false;   if( month > m ) return true;   if( day < d ) return false;   return true; }

Автор: Creder 26.5.2015, 09:28

Эх, во вемя удаления узлов вылетает. Код #include <iostream> #include <cstdlib> using namespace std; class Node { protected:   Node *left, *right;   string name;   int day;   int month;   int year; public:   bool uptodate(int, int, int);   Node(const string &n, int d, int m, int y) : name(n), day(d), month(m), year(y), left(0), right(0) {}   friend class Tree; }; bool Node::uptodate( int d, int m, int y) {   if( year < y ) return false;   if( year > y ) return true;   if( month < m ) return false;   if( month > m ) return true;   if( day < d ) return false;   return true; } class Tree {     Node* root;     void print(Node*);     void parentFixup( Node*, Node*, Node*);     void search_node( Node*, Node*, int, int, int);     void remove_node(Node*, Node*);     void cleartree( Node*);  public:      Tree() : root(0) {}      ~Tree() {cleartree(root); }      void add_node(Node*);      void search_node(int, int, int);      void print(); }; void Tree::cleartree( Node *node ) {   if( node != 0 )   {     cleartree( node->left);     cleartree( node->right);     delete node;   } } void Tree::add_node(Node *t) {         Node *parent = 0, *curr=root;         while(curr!=0)         {             parent=curr;             if(t->name > curr->name) curr=curr->right;             else curr=curr->left;         }         if( parent == 0 )             root = t;         else if(t->name < parent->name)             parent->left=t;         else             parent->right=t; } void Tree::parentFixup( Node *parent, Node *oldNode, Node *newNode) {   if( parent == 0 )     root = newNode;   else if( parent->left == oldNode )     parent->left = newNode;   else     parent->right = newNode; } void Tree::remove_node( Node *node, Node* parent) {     if( node->right == 0 && node->left == 0 )         parentFixup(parent, node, 0);     else if( node->right == 0 )         parentFixup(parent, node, node->left);     else if( node->left == 0 )         parentFixup(parent, node, node->right);     else     {         Node *c, *p = node;         for( c = node->right; c->left != 0; c = c->left) p = c;         if( p!= node )         {             p->left = c->right;             c->right = node->right;         }         c->left = node->left;         parentFixup(parent, node, c);     }     delete node; } void Tree::search_node( Node *node, Node *parent, int day, int month, int year) {   if( parent->left == node)   {     Node *temp;     if( (temp = parent->left) != 0 )     {       search_node( temp->left, temp, day, month, year);       search_node( temp->right, temp, day, month, year);       if( temp->uptodate(day, month, year) ) remove_node( temp, 0);     }   }   else if( parent->right == node)   {     Node *temp;     if( (temp = parent->right) != 0 )     {       search_node( temp->left, temp, day, month, year);       search_node( temp->right, temp, day, month, year);       if( temp->uptodate(day, month, year) ) remove_node( temp, 0);     }   } } void Tree::search_node(int day, int month, int year) {     if( root != 0 )     {         search_node( root->left, root, day, month, year);         search_node( root->right, root, day, month, year);         if( root->uptodate(day, month, year) ) remove_node( root, 0);     } } void Tree::print() {     print(root); } void Tree::print(Node* p) {     if(p != 0)     {         cout<< p->name <<" "<< p->day << "." << p->month << "." << p->year << endl;         if(p->left) print(p->left);         if(p->right) print(p->right);     }     else return; } int main() {     Tree tree;     setlocale(0, "");     string name;     int i,n, d, m, y;     cout << "Введите кол-во файлов" << endl;     cin >> n;     for(i=0; i<n; i++)         {         cout << "Имя файла: " << endl;         cin >> name;         cout << "День: " << endl;         do         {             cin >> d;             if(d<1||d>31)                 cout << "Ошибка. Введите число от 1 до 31." << endl;         }         while(d<1||d>31);         cout << "Месяц: " << endl;         do         {             cin >> m;             if(m<1||m>12)                 cout << "Ошибка. Введите число от 1 до 12." << endl;         }         while(m<1||m>12);         cout << "Год: " << endl;         cin >> y;         Node* node=new Node(name, d, m, y);         tree.add_node(node);         }     tree.print();     cout << "Введите дату файла:" << endl;     cout << "День: " << endl;         do         {             cin >> d;             if(d<1||d>31)                 cout << "Ошибка. Введите число от 1 до 31." << endl;         }         while(d<1||d>31);     do         {             cin >> m;             if(m<1||m>12)                 cout << "Ошибка. Введите число от 1 до 12." << endl;         }         while(m<1||m>12);     cout << "Год: " << endl;     cin >> y;     tree.search_node(d, m, y);     tree.print();     return 0; }

Автор: feodorv 26.5.2015, 12:40

Цитата(Creder @  26.5.2015,  09:28 ) Эх, во вемя удаления узлов вылетает. Обязано вылетать.  Цитата(Creder @  26.5.2015,  09:28 ) void Tree::search_node( Node *node, Node *parent, int day, int month, int year) {   if( node == 0 ) return;   if( parent->left == node)   {     Node *temp;     if( (temp = parent->left) != 0 )     {       search_node( temp->left, temp, day, month, year);       search_node( temp->right, temp, day, month, year);       if( temp->uptodate(day, month, year) ) remove_node( temp, 0 parent);     }   }   else if( parent->right == node) // есть сомнения???   {      // Аналогичные изменения       } } Зачем Вам temp, если он в точности равен node? Уберите temp, убедитесь, что код в if и else в точности совпадают. Итого: Код void Tree::search_node( int day, int month, int year) {   search_node( root, 0, day, month, year); } void Tree::search_node( Node *node, Node *parent, int day, int month, int year) {   if( node != 0 )   {     search_node( node->left, node, day, month, year);     search_node( node->right, node, day, month, year);     if( !node->uptodate( day, month, year) ) remove_node( node, parent);   } }

Автор: Creder 26.5.2015, 15:02

Сработало! Спасибо вам!

Автор: Creder 27.5.2015, 23:22

Хм. В общем, просмотрели мой код и ппоросили сделать в нем некоторые поправки. У меня к этому есть несколько вопросов. В С++ к полям классам добавляют префиксы m_ .  Правильно понимаю, что это в классе Node нужно приписать это к переменным? Код class Node { protected:   Node *left, *right;   string m_name;   int m_day;   int m_month;   int m_year;   bool uptodate( int, int, int ); public:   Node( const string &n, int d, int m, int y ) : m_name( n ), m_day( d ), m_month( m ), m_year( y ), left( nullptr ), right( nullptr ) {}   friend class Tree; }; Tree пользуется полями Node напрямую: т.е. нарушена инкапсуляция внутри Node. Что такое инкапсуляция? И что нужно делать с этим? Вместо 0 нужно использовать для сравнения адресов nullptr : это ключевое слово специально завели для этих целей.  С этим тоже не все понятно. В чем разница и, выходит, мне нужно все нули в коде заменить на nullptr? Добавьте, пожалуйста, конструктор копирования и оператор присваивания или запретите ими пользоваться.  Например, я захотел запретить конструктор копирования и оператор присваивания. Достаточно ли добавить в мой код этот класс? Код class noncopyable {    protected:       noncopyable() {}       ~noncopyable() {}    private:       noncopyable( const noncopyable& );       const noncopyable& operator=( const noncopyable& ); }; Добавьте, пожалуйста, проверку данных через исключения в add_node, например, когда t == nullptr. Тоже не совсем понимаю, что нужно сделать.  Предлагаю попробовать реализовать operator << вместо print().  Нужно перегрузить оператор <<? Как это делается? Main: проведите, пожалуйста, декомпозицию. Имеется ввиду читабельность кода в функции main()? Нужно что-то поправить? Надеюсь на вашу помощь.

Автор: Creder 29.5.2015, 08:21

....

Автор: feodorv 29.5.2015, 08:48

Формально "препод" прав. Цитата(Creder @  27.5.2015,  23:22 ) В С++ к полям классам добавляют префиксы m_  Не http://habrahabr.ru/post/124417/ (в принудительном порядке), а принято добавлять, чтобы по имени сразу можно было понять, что переменная является членом класса. "m_" - для нестатических членов класса. Цитата(Creder @  27.5.2015,  23:22 ) Правильно понимаю, что это в классе Node нужно приписать это к переменным? И для класса Tree тоже. И тогда уж все имена полей класса, не только каких-то избранных. Тогда и в конструкторе можно будет вернуться к day, month, year, name заместо урезанных d, m, y, n. Цитата(Creder @  27.5.2015,  23:22 ) Что такое инкапсуляция? И что нужно делать с этим? Гм. Почему бы этот вопрос не задать интернету? Это одно из основополагающих понятий ООП; ведь могут потом и спросить, что это такое. Грубо говоря, никто не должен иметь прямой доступ к данным (полям) класса, а считывание и установка их значений должна происходить через так называемые функции геттеры (от английского get) и сеттеры (от английского set): Код void Node::setLeft( Node *left ) {   m_left = left; } Node *Node::getLeft() {   return m_left; } Цитата(Creder @  27.5.2015,  23:22 ) В чем разница и, выходит, мне нужно все нули в коде заменить на nullptr? Да))) Везде в коде, где речь идёт об указателях. Цитата(Creder @  27.5.2015,  23:22 ) Достаточно ли добавить в мой код этот класс? Но вот что волшебным образом должно поменяться, если Вы добавите этот класс в свой код?   Да ничего. Дело ведь не в самом классе, или его присутствии, а в том, что он объявляет конструктор копирования и оператор присваивания. Тупо объявляет, но не реализует (для них нет тел функций): Цитата(Creder @  27.5.2015,  23:22 )       noncopyable( const noncopyable& );       const noncopyable& operator=( const noncopyable& ); Зачем всё это? Если их не объявлять, то компилятор их автоматически создаст, что в Вашем случае не хорошо: Код Tree tree1, tree2; tree1.add_node(...); tree2.add_node(...); tree2 = tree1; Автоматически создаваемые конструктор копирования и оператор присваивания очень просты: Цитата По умолчанию при инициализации одного объекта другим С++ выполняет побитовое копирование. В результате у Вас будет два взамозависимых дерева, и, например, при вызове очередного деструктора дерева вполне возможен крах программы, не говоря уже о просто некорректности такой ситуации (ведь это два разных независимых друг от друга экземпляра класса дерева). Чтобы этого не происходило, Вам необходимо переопределить эти вещи. Но зачем Вам их по настоящему реализовывать? Они же не используются. Поэтому Вы просто объявляете, что они где-то есть (при таком объявлении компилятор их автоматически не создаёт), но не реализуете (не пишете под них код). Тогда, если в они нигде в коде не применяются, то компилятор как бы и не заметит их отсутствия (они же не нужны). Но если они применяются где-нибудь в коде, то компилятор выдаст ошибку об их нереализованности. Так можно избежать их реального применения в коде. Послушайте, не в моих силах расписать здесь весь учебник C++. Вы всегда можете воспользоваться поиском, например, http://yandex.ru/yandsearch?text=%D0%BA%D0%BE%D0%BD%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D0%BE%D1%80%20%D0%BA%D0%BE%D0%BF%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F%20%D0%BF%D0%BE%20%D1%83%D0%BC%D0%BE%D0%BB%D1%87%D0%B0%D0%BD%D0%B8%D1%8E%20c%2B%2B&clid=48648. Тема начинает далеко выходить за пределы удаления узлов из бинарного дерева и касаться основ C++. Цитата(Creder @  27.5.2015,  23:22 ) Имеется ввиду читабельность кода в функции main()? В main() бардак. Нужно как минимум вынести код ввода данных с клавиатуры в отдельные функции.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)