Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Перезагрузить страницу Удалить узел в бинарном дереве
Регистрация

Восстановить пароль		 Повторная активизация e-mail
Регистрация Задать
вопрос		 Заплачу
за решение		 Новые
сообщения 		Сообщения
за день 		Расширенный
поиск		 Правила Всё
прочитано

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 22.06.2016, 20:43   #1
Вероника99
Форумчанин
 
Регистрация: 15.12.2013
Сообщений: 414
По умолчанию Удалить узел в бинарном дереве
Добрый вечер. В задании нужно найти узел дерева с наибольшим показателем счетчика, после чего удалить найденный узел из дерева. В структуре помимо счетчика также хранится английское слово,русское слово и естественно указатели на правую и левую стороны. Возникли проблемы с функцией удаления найденного узла.
Код:
struct tree
{
    string eng; //слово
    string rus; //слово
    int count; //количество обращений
    tree *left;
    tree *right;
};
void DeleteNode(tree*p) //функция удаления найденного узла
{
    tree*r=p;
    tree *p_new,*pp;
    if(p->left==NULL&&p->right==NULL)
    {
        p=NULL;
        return;
    }
    else if(p->right==NULL)
    {
        p=p->left;
        return;
    }
    else if(p->left==NULL)
    {   p=p->right;
    return;
    }
    else
    {
        p_new=p->left;
        pp=p;
        while(p_new->right!=NULL)
        {
            pp=p_new;
            p_new=p_new->right;
        }
        p_new->right=p->right;
        if(pp!=p)
        {
            pp->right=p_new->left;
            p_new->left=p->left;
        }
    }
    p=p_new;
    
    //free(r);
    //return;
    
//DeleteNode(root,p->left);
}
...
//main:

tree *p=seek_count(root,0); //ф-ция seek_count возвращает указатель на найденный узел с максимальным показателем счетчика
    cout<<"Delete"<<endl;
    DeleteNode(p);
        print_tree (root, 0);
Вероника99 вне форума Ответить с цитированием
Старый 22.06.2016, 21:03   #2
ura_111
Участник клуба
 
Регистрация: 14.05.2016
Сообщений: 1,793
По умолчанию
Выложи полный код. Я хочу посмотреть.
ura_111 вне форума Ответить с цитированием
Старый 22.06.2016, 21:10   #3
Вероника99
Форумчанин
 
Регистрация: 15.12.2013
Сообщений: 414
По умолчанию
Код:

...
int max_l=0;
tree *seek_count (tree *p, int level) //функция поиска максимального показателе счетчика в узлах
{
	if(p)
	{
		if(max_l<p->count)
		{
			max_l=p->count;
			
		}
		seek_count(p->left,level+1);
			seek_count(p->right,level+1);

	}
	return p;
}
// Функция показа дерева
void print_tree (tree *p, int level)
{
	if (p)
	{
		print_tree(p->left, level+1);
		for (int i=0; i<level; i++)
		cout<<" ";
		cout<<p->eng<<endl;
			cout<<p->rus<<endl;
		for (int i=0; i<level; i++)
		cout<<" ";
		cout<<p->count<<endl;
		print_tree (p->right, level+1);
	}
	lev=level;
}
tree* copy_root(tree*p)
{

	tree *pv=new tree;
	pv->eng=p->eng;
	pv->rus=p->rus;
	pv->count=p->count;
	pv->left=0;
	pv->right=0;
	return pv;
}
void DeleteNode(tree*p)
{
	tree*r=p;
	tree *p_new,*pp;
	if(p->left==NULL&&p->right==NULL)
	{
		p=NULL;
		return;
	}
	else if(p->right==NULL)
	{
		p=p->left;
		return;
	}
	else if(p->left==NULL)
	{	p=p->right;
	return;
	}
	else
	{
		p_new=p->left;
		pp=p;
		while(p_new->right!=NULL)
		{
			pp=p_new;
			p_new=p_new->right;
		}
		p_new->right=p->right;
		if(pp!=p)
		{
			pp->right=p_new->left;
			p_new->left=p->left;
		}
	}
	p=p_new;
	
	free(p);
	//return;
	
DeleteNode(p->left);
DeleteNode(p->right);
}
int main()
{

	tree *root=NULL;
//добавление узлов в дерево
...
tree *p=seek_count(root,0);
	cout<<"Delete"<<endl;
	DeleteNode(p);
		print_tree (root, 0);


	cout<<"\nMax= "<<max_l<<endl;
	tree *new_root=NULL;
	if(new_root==NULL)
	new_root=copy_root(p); //после нахождения узла с макс.счетчиком нужно сформировать новое дерево,в которые заносить найденные узлы
	print_tree (new_root, 0);
	
	
	return 0;

}
Вероника99 вне форума Ответить с цитированием
Старый 22.06.2016, 21:17   #4
ura_111
Участник клуба
 
Регистрация: 14.05.2016
Сообщений: 1,793
По умолчанию
Я имел ввиду полный (найполнейший, най-найполнейший) код. Дело в том, что я пока ещё учусь, и мне трудно по одному взгляду на код что то сказать (для этого нужно знать что делает каждая строчка кода). Я так пока не могу. Мне надо, то что называется, пощупать код, посмотреть его в работе.

А то у меня компилятор ругается на твой код


Последний раз редактировалось ura_111; 22.06.2016 в 21:32.
ura_111 вне форума Ответить с цитированием
Старый 22.06.2016, 21:31   #5
Вероника99
Форумчанин
 
Регистрация: 15.12.2013
Сообщений: 414
По умолчанию
Пожалуйста
Код:

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

string temp_eng;
string temp_rus;
int temp_count;
int lev=0;
struct tree
{
	string eng; //слово
	string rus; //слово
	int count; //количество обращений
	tree *left;
	tree *right;
};
// Функция создания первого элемента
// Функция фoрмирования первого элемента дерева:
tree *first (string temp_eng,string temp_rus,int temp_count)
{
	tree *pv=new tree;
	pv->eng=temp_eng;
	pv->rus=temp_rus;
	pv->count=temp_count;
	pv->left=0;
	pv->right=0;
	return pv;
}

// Функция поиска и добавления элемента в дерево:
tree *search_insert (tree *root, string temp_eng, string temp_rus,int temp_count)
{
	tree *pv=root, *prev;
	bool found=false;
	//поиск по дереву
	while (pv&&!found) 
	{
	prev=pv;
	if ((temp_eng==pv->eng)&&(temp_rus==pv->rus))
		found = true;
	else if (temp_count < pv->count)
		pv=pv->left;
	else pv=pv->right;
	}
	if (found) return pv;
	//создание нового узла
	tree *pnew=new tree;
	pnew->eng=temp_eng;
	pnew->rus=temp_rus;
	pnew->count=temp_count;
	pnew->left=0;
	pnew->right=0;
	if (temp_count < prev->count)
	prev->left=pnew; //присоединение к левому поддереву предка
	else prev->right=pnew; //присоединение к правому поддереву предка
	return pnew;
}
//функция поиска наибольшего счетчика
int max_l=0;
tree *seek_count (tree *p, int level)
{
	if(p)
	{
		if(max_l<p->count)
		{
			max_l=p->count;
			
		}
		seek_count(p->left,level+1);
			seek_count(p->right,level+1);

	}
	return p;
}
// Функция показа дерева
void print_tree (tree *p, int level)
{
	if (p)
	{
		print_tree(p->left, level+1);
		for (int i=0; i<level; i++)
		cout<<" ";
		cout<<p->eng<<endl;
			cout<<p->rus<<endl;
		for (int i=0; i<level; i++)
		cout<<" ";
		cout<<p->count<<endl;
		print_tree (p->right, level+1);
	}
	lev=level;
}
tree* copy_root(tree*p)
{

	tree *pv=new tree;
	pv->eng=p->eng;
	pv->rus=p->rus;
	pv->count=p->count;
	pv->left=0;
	pv->right=0;
	return pv;
}
void DeleteNode(tree*p)
{
	tree*r=p;
	tree *p_new,*pp;
	if(p->left==NULL&&p->right==NULL)
	{
		p=NULL;
		return;
	}
	else if(p->right==NULL)
	{
		p=p->left;
		return;
	}
	else if(p->left==NULL)
	{	p=p->right;
	return;
	}
	else
	{
		p_new=p->left;
		pp=p;
		while(p_new->right!=NULL)
		{
			pp=p_new;
			p_new=p_new->right;
		}
		p_new->right=p->right;
		if(pp!=p)
		{
			pp->right=p_new->left;
			p_new->left=p->left;
		}
	}
	p=p_new;
	
	free(p);
	//return;
	
DeleteNode(p->left);
DeleteNode(p->right);
}
/*
tree *copy_search_insert (tree *root)
{
	tree *pv=root, *prev;
	bool found=false;
	//поиск по дереву
	while (pv&&!found) 
	{
	prev=pv;
	if ((temp_eng==pv->eng)&&(temp_rus==pv->rus))
		found = true;
	else if (temp_count < pv->count)
		pv=pv->left;
	else pv=pv->right;
	}
	if (found) return pv;
	//создание нового узла
	tree *pnew=new tree;
	pnew->eng=temp_eng;
	pnew->rus=temp_rus;
	pnew->count=temp_count;
	pnew->left=0;
	pnew->right=0;
	if (temp_count < prev->count)
	prev->left=pnew; //присоединение к левому поддереву предка
	else prev->right=pnew; //присоединение к правому поддереву предка
	return pnew;
}

*/
int main()
{
	tree *root=NULL;
	for(int i=0;i<3;i++)
	{
	cout<<"Vvedite angliskoe slovo: "<<endl;
	cin>>temp_eng;
		cout<<"Vvedite russkoe slovo: "<<endl;
	cin>>temp_rus;
	cout<<"Vvedite znachenie schetchika: "<<endl;
	cin>>temp_count;
	if(!root)
	{
		root=first(temp_eng,temp_rus,temp_count);
	}
	else 
		search_insert (root, temp_eng, temp_rus,temp_count);
	}
	print_tree (root, 0);

	tree *p=seek_count(root,0);
	cout<<"Delete"<<endl;
	DeleteNode(p);
		print_tree (root, 0);


	cout<<"\nMax= "<<max_l<<endl;
	tree *new_root=NULL;
	if(new_root==NULL)
		new_root=copy_root(p);
	print_tree (new_root, 0);
	
	
	return 0;
}
Вероника99 вне форума Ответить с цитированием
Старый 23.06.2016, 14:27   #6
ura_111
Участник клуба
 
Регистрация: 14.05.2016
Сообщений: 1,793
По умолчанию
Короче, перепахал всю программу (не только ф-цию удаления), теперь начала что-то выводить. Вероник, возьми и хорошенько протестируй мой код (у меня на это не было времени). Если что, будем общаться дальше. Здесь ограничение на код в 8000 букв, поэтому разбил программу на 2-части (см. ниже).



Код:
#include <iostream>
#include <string>
using namespace std;

string temp_eng;
string temp_rus;
int temp_count;
int lev = 0;
struct tree
{
	string eng; //слово
	string rus; //слово
	int count; //количество обращений
	tree *left;
	tree *right;
};
// Функция создания первого элемента
// Функция фoрмирования первого элемента дерева:
tree *first(string temp_eng, string temp_rus, int temp_count)
{
	tree *pv = new tree;
	pv->eng = temp_eng;
	pv->rus = temp_rus;
	pv->count = temp_count;
	pv->left = 0;
	pv->right = 0;
	return pv;
}

// Функция поиска и добавления элемента в дерево:
tree *search_insert(tree *root, string temp_eng, string temp_rus, int temp_count)
{
	tree *pv = root, *prev;
	bool found = false;
	//поиск по дереву
	while (pv&&!found)
	{
		prev = pv;
		if ((temp_eng == pv->eng) && (temp_rus == pv->rus))
			found = true;

		if ((pv->left != NULL) && (pv->right == NULL))
		{
			pv = pv->left;
			continue;
		}
		if ((pv->left == NULL) && (pv->right != NULL))
		{
			pv = pv->right;
			continue;
		}
		if ((prev->left == NULL) && (prev->right == NULL))
		{
			break;
		}
	}
	if (found) return pv;
	//создание нового узла
	tree *pnew = new tree;
	pnew->eng = temp_eng;
	pnew->rus = temp_rus;
	pnew->count = temp_count;
	pnew->left = 0;
	pnew->right = 0;
	if (temp_count < prev->count)
		prev->left = pnew; //присоединение к левому поддереву предка
	else prev->right = pnew; //присоединение к правому поддереву предка
	return pnew;
}

//функция поиска наибольшего счетчика
int max_l = 0;

void seek_count(tree *p)
{
	tree *p_max_1 = p;
	max_l = p_max_1->count;
	while (true)
	{
		if ((p->left != NULL) && (p->right == NULL))
		{
			p = p->left;
		}
		if ((p->left == NULL) && (p->right != NULL))
		{
			p = p->right;
		}
		if (max_l < p->count)
		{
			p_max_1 = p;			
			max_l = p_max_1->count;
		}
		if ((p->left == NULL) && (p->right == NULL))
		{
			break;
		}	
	}
}

// Функция показа дерева
void print_tree(tree *p, int level)
{
	tree *p_next = p;
	seek_count(p);      // находим max_l чисто ради красоты вывода (определение отступов)
	
	int *left = new int[max_l];
	for (int i = 0; i < max_l; i++)
		left[i] = 0;
	string St("");
	int ii = 0;
	bool t = false;
	while (true)
	{
		if ((p_next->left != NULL) && (p_next->right == NULL))
		{
			left[ii]++;
			p_next = p_next->left;
			continue;
		}
		if ((p_next->left == NULL) && (p_next->right != NULL))
		{
			ii++;
			p_next = p_next->right;
			continue;
		}
		if ((p_next->left == NULL) && (p_next->right == NULL))
		{
			break;
		}
	}
	ii = left[0];
	for (int i = 0; i < max_l; i++)
	{
		if (left[i] > ii)
			ii = left[i];
	}
	delete[] left;
	for (int i = 0; i <= ii; i++)
		St = St + " ";
	p_next = p;
	while (true)
	{
		if ((p_next->left != NULL) && (p_next->right == NULL))
		{
			cout << St << p_next->eng << "-" << p_next->rus << endl;
			cout << St << p_next->count << endl;
			St.resize(St.size() - 1);			
			p_next = p_next->left;
			continue;
		}
		if ((p_next->left == NULL) && (p_next->right != NULL))
		{
			cout << St << p_next->eng << "-" << p_next->rus << endl;
			cout << St << p_next->count << endl;
			St = St + " ";
			p_next = p_next->right;
			continue;
		}
		if ((p_next->left == NULL) && (p_next->right == NULL))
		{
			cout << St << p_next->eng << "-" << p_next->rus << endl;
			cout << St << p_next->count << endl;
			break;
		}
	}
	
	//if (p)
	//{
	//	print_tree(p->left, level + 1);
	//	for (int i = 0; i<level; i++)
	//		cout << " ";
	//	cout << p->eng << "  ";
	//	cout << p->rus << endl;
	//	for (int i = 0; i<level; i++)
	//		cout << " ";
	//	cout << p->count << endl;
	//	print_tree(p->right, level + 1);
	//}
	//lev = level;
}
tree* copy_root(tree*p)
{

	tree *pv = new tree;
	pv->eng = p->eng;
	pv->rus = p->rus;
	pv->count = p->count;
	pv->left = 0;
	pv->right = 0;
	return pv;
}

tree* DeleteNode(tree *p)
{
	if ((p->left == NULL) && (p->right == NULL))
	{
		cout << "Нельзя удалить один единственный узел!" << endl << endl;
		return p;
	}
	if ((max_l == p->count) || (max_l == p->count))
	{
		if ((p->left != NULL) && (p->right == NULL))
			return p->left;
		if ((p->left == NULL) && (p->right != NULL))
			return p->right;
	}

	tree *p_prev = p;
	tree *p_next = p;
	while (true)
	{
		if ((p_prev->left != NULL) && (p_prev->right == NULL))
		{
			p_next = p_prev->left;
			
			if (max_l == p_next->count)
			{
				if ((p_next->left != NULL) && (p_next->right == NULL))
				{
					p_prev->left = p_next->left;
					break;
				}
				if ((p_next->left == NULL) && (p_next->right != NULL))
				{
					p_prev->left = p_next->right;
					break;
				}
				if ((p_next->left == NULL) && (p_next->right == NULL))
				{
					p_prev->left = NULL;
					break;
				}
			}
			else
			{
				p_prev = p_next;
			}
			continue;
		}		
		if ((p_prev->left == NULL) && (p_prev->right != NULL))
		{
			p_next = p_prev->right;
			if (max_l == p_next->count)
			{
				if ((p_next->left != NULL) && (p_next->right == NULL))
				{
					p_prev->right = p_next->left;
					break;
				}
				if ((p_next->left == NULL) && (p_next->right != NULL))
				{
					p_prev->right = p_next->right;
					break;
				}
				if ((p_next->left == NULL) && (p_next->right == NULL))
				{
					p_prev->right = NULL;
					break;
				}
			}
			else
			{
				p_prev = p_next;
			}
			continue;
		}
	}
	delete p_next;
	return p;
}
Последний раз редактировалось ura_111; 23.06.2016 в 14:38.
ura_111 вне форума Ответить с цитированием
Старый 23.06.2016, 14:27   #7
ura_111
Участник клуба
 
Регистрация: 14.05.2016
Сообщений: 1,793
По умолчанию
Код:
/*
tree *copy_search_insert (tree *root)
{
tree *pv=root, *prev;
bool found=false;
//поиск по дереву
while (pv&&!found)
{
prev=pv;
if ((temp_eng==pv->eng)&&(temp_rus==pv->rus))
found = true;
else if (temp_count < pv->count)
pv=pv->left;
else pv=pv->right;
}
if (found) return pv;
//создание нового узла
tree *pnew=new tree;
pnew->eng=temp_eng;
pnew->rus=temp_rus;
pnew->count=temp_count;
pnew->left=0;
pnew->right=0;
if (temp_count < prev->count)
prev->left=pnew; //присоединение к левому поддереву предка
else prev->right=pnew; //присоединение к правому поддереву предка
return pnew;
}

*/
int main()
{
	setlocale(LC_ALL, "Russian");
		
	tree *root = NULL;
	//for (int i = 0; i<3; i++)
	//{
	//	cout << "Vvedite angliskoe slovo: " << endl;
	//	cin >> temp_eng;
	//	cout << "Vvedite russkoe slovo: " << endl;
	//	cin >> temp_rus;
	//	cout << "Vvedite znachenie schetchika: " << endl;
	//	cin >> temp_count;
	//	if (!root)
	//	{
	//		root = first(temp_eng, temp_rus, temp_count);
	//	}
	//	else
	//		search_insert(root, temp_eng, temp_rus, temp_count);
	//}

	//root = first("a", "а", 8);
	//search_insert(root, "b", "б", 2);
	//search_insert(root, "c", "в", 3);
	//search_insert(root, "d", "г", 4);
	//search_insert(root, "f", "д", 9);
	//search_insert(root, "g", "е", 6);
	//search_insert(root, "h", "ё", 5);
	//search_insert(root, "k", "ж", 1);
	//search_insert(root, "i", "з", 7);

	//root = first("a", "а", 9);
	//search_insert(root, "b", "б", 8);
	//search_insert(root, "c", "в", 7);
	//search_insert(root, "d", "г", 6);
	//search_insert(root, "f", "д", 5);
	//search_insert(root, "g", "е", 4);
	//search_insert(root, "h", "ё", 3);
	//search_insert(root, "k", "ж", 2);
	//search_insert(root, "i", "з", 1);
	
	root = first("a", "а", 9);
	search_insert(root, "b", "б", 8);
	search_insert(root, "c", "в", 7);
	search_insert(root, "d", "г", 6);
	search_insert(root, "f", "д", 5);
	search_insert(root, "g", "е", 10);
	search_insert(root, "h", "ё", 11);
	search_insert(root, "k", "ж", 12);
	search_insert(root, "i", "з", 13);


	cout << "Первоначальное дерево " << endl;
	print_tree(root, 0);
	
	seek_count(root);  
	cout << "\nНайденный Max= " << max_l << ". Удалим его." << endl << endl;
	root = DeleteNode(root);	
	cout << "Новое дерево " << endl;
	print_tree(root, 0);
	
	seek_count(root);
	cout << "\nНайденный Max= " << max_l << ". Удалим его." << endl << endl;
	root = DeleteNode(root);
	cout << "Новое дерево " << endl;
	print_tree(root, 0);
	
	seek_count(root);
	cout << "\nНайденный Max= " << max_l << ". Удалим его." << endl << endl;
	root = DeleteNode(root);
	cout << "Новое дерево " << endl;
	print_tree(root, 0);
	
	system("pause");
	return 0;
}
ura_111 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Освобождение памяти в бинарном дереве? perceptron2013 Общие вопросы C/C++ 4 06.11.2012 16:28
удаление элемента в бинарном дереве Kukurudza Общие вопросы C/C++ 1 26.06.2011 22:51
Расчет уровней в бинарном дереве holi10 Общие вопросы C/C++ 0 01.06.2011 18:22
Поиск в бинарном дереве не по ключу lebrosha Помощь студентам 2 26.05.2009 15:32
Удаление вершины в бинарном дереве lebrosha Помощь студентам 2 24.05.2009 13:51

Реклама на форуме - Обратная связь - Правила - Исходники Delphi - Справочник Delphi - Архив - Вверх