1.Проблема с удалением элемента из дерева. (Когда удаляю элемент и вывожу дерево на экран программа зацикливается.) 2. При поиске , если вводить слово которого нет в дереве, некорректно работает. Помогите очень срочно! Могу заплатить! | Код |
#include "stdafx.h"
#include "iostream"
#include <fstream>
#include <string>
using namespace std;
template <class Date> //Шаблон класса для универсального типа хранимых данных
class Tree {
struct node{
string key;
Date info;
node *parent,*left,*right;
};
private:
node *root;
void printTree( node *root, int level=0 ){
if (root != 0){
printTree( root->right, level + 1 );
for ( int i = 0; i < level; i++ ) cout << "\t";
cout << root->key <<endl;
printTree( root->left, level + 1 );
}
};
node * Leftmost( node *root ) {
if (root == NULL)
return NULL;
if (root->left != NULL) {
return Leftmost(root->left);
}
return root;
};
node * Rightmost( node *root ) {
if (root == NULL)
return NULL;
if (root->right != NULL) {
return Rightmost(root->right);
}
return root;
};
public:
//Обнуление указателя на корень
Tree() {
this->root=0;
};
//Cоздание первого элемента
void first( string Keyword, Date information ){
node *pf=new node;
pf->key=Keyword;
pf->info=information;
pf->left=pf->right=pf->parent = 0;
this->root=pf;
};
//Обход дерева
void showTree(){
printTree( this->root, 0 );
};
//Добавление элемента(поиск места)
node *addElement(string Key, Date information){
node *pv = this->root,*prev;
bool found = false;
while ( pv && !found )
{
prev = pv;
if ( pv->key == Key )
found = true;
else if ( pv->key > Key )
pv = pv->left;
else pv = pv->right;
}
if (found) {
cout <<"Такой элемент уже существует"<<endl;
return pv;
}
// Создание нового узла, если элемент не найден:
node *pnew = new node;
pnew->key=Key;
pnew->info=information;
pnew->left = 0;
pnew->right = 0;
pnew->parent = prev;
if ( prev->key > Key )
prev->left = pnew;
else
prev->right = pnew;
return pnew;
};
//Поиск
node *search( string Key ){
node *pv = this->root;
bool found = false;
while ( pv && !found )
{
if ( pv->key == Key )
found = true;
else if ( pv->key > Key )
pv = pv->left;
else
pv = pv->right;
}
if ( found )
return pv;
else return 0;
};
//Удаление корня
void removeRoot(){
node *r =this->root;
if ( ( r->right == 0 ) && ( r->left == 0 ) )
{ this->root = 0;
delete (r);
}
else {
this->root=Rightmost(r->left);
this->root->parent=0;
delete r;
}
};
//Удаление элемента
void delElement( string Key ){
node * n = search(Key); node *q;
q=n;
if ( n == 0 ){
cout << "Value not found!" <<endl;
return;
}
else if (n == this->root) {
removeRoot();
}
else if (( n->left == 0) && (n->right == 0 )) { //Если у элемента нету ни левого, ни правого ответвления
if ( n->parent->left == n)
n->parent->left = 0;
else
n->parent->right = 0;
delete n;
}
else if ( n-> left == 0) {
n->right->parent = n->parent;
if (n->parent->right == n)
n->parent->right = n->right;
else
n->parent->left = n->right;
n=n->right;
delete q;
}
else if ( n-> right == 0) {
n->left->parent = n->parent;
if (n->parent->right == n)
n->parent->right = n->left;
else
n->parent->left = n->left;
n=n->left;
delete q;
}
else{
node *buf1, *buf2;
node *f=Rightmost(n->left);
if (n->parent->left == n)
n->parent->left = f;
else n->parent->right = f;
buf1=n->left;
buf2=n->right;
n=f;
f->left=buf1;
f->right=buf2;
delete q;
}
cout << "Element has been seccessefully deleted" << endl;
};
};
void ShowMenu(){
system("cls");
cout << " ------------------------------------------- " << endl;
cout << "| 1. Create new tree | " << endl;
cout << "| 2. Read from keyboard | " << endl;
cout << "| 3. Read from file | " << endl;
cout << "| 4. Show translation of the word | " << endl;
cout << "| 5. Delete element | " << endl;
cout << "| 6. Show the whole tree | " << endl;
cout << "| 0. EXIT | " << endl;
cout << " ------------------------------------------- " << endl;
cout << "Press number to continue " << endl;
};
int _tmain(int argc, _TCHAR* argv[]){
setlocale(LC_ALL,"russian"); //Русская кодировка
Tree <string> Slovar;
string key,info;
short int selector=255;
for (;;){
ShowMenu();
cin >> (selector);
switch (selector) {
case 1: {
string key,info;
cout << "Enter word" << endl;
cin >> key;
cout << "Enter translation" << endl;
cin >> info;
Slovar.first(key,info);
break;
}
case 2: {
short int i,j;
cout <<"How much words you would like to add?" <<endl;
cin >> j;
for (i=0;i<j;i++) {
cout << "Enter " << i+1 << " word" << endl;
cin >> key;
cout << "Enter " << key << " translation" << endl;
cin >> info;
Slovar.addElement(key,info);
}
break;
}
case 3: {
ifstream potok("note.txt"); // для работы со string'oм проще использовать stream, то есть поток;
string key,info;
while(potok){
getline(potok,key);
getline(potok,info);
if (Slovar.search(key) == 0 ){
Slovar.addElement(key,info);
}
}
break;
}
case 4: {
string key;
cout << "Enter the word" << endl;
cin >> key;
cout << key << " means " << Slovar.search(key)->info << endl;
break;
}
case 5: {
string key;
cout << "Enter the word" << endl;
cin >> key;
Slovar.delElement(key);
break;
}
case 6: {
Slovar.showTree();
break;
}
case 0: {
return(0);
}
};
system("pause");
};
};
|
|
Классы и деревья, Нужна помощь 
Загрузка ...
