18.01.2017, 00:17 [+3 UTC]
в нашей команде: 1 756 чел. | участники онлайн: 3 (рекорд: 21)

:: РЕГИСТРАЦИЯ

:: консультации

:: задать вопрос

:: все разделы

:: правила

:: новости

:: участники

:: доска почёта

:: форум

:: блоги

:: поиск

:: статистика

:: наш журнал

:: наши встречи

:: наша галерея

:: отзывы о нас

:: поддержка

:: руководство

Версия системы:
7.40 (02.09.2016)

Общие новости:
31.12.2016, 18:43

Форум:
14.01.2017, 04:29

Последний вопрос:
17.01.2017, 19:31

Последний ответ:
17.01.2017, 21:15

Последняя рассылка:
17.01.2017, 22:45

Писем в очереди:
0

Мы в соцсетях:

Наша кнопка:

RFpro.ru - здесь вам помогут!

Отзывы о нас:
18.11.2009, 13:57 »
Ramis
Химик CH, благодарю вас за вашу помощь! [вопрос № 174303, ответ № 256645]
19.01.2010, 18:25 »
Смирнов Сергей Анатольевич
Спасибо за скорость!!! [вопрос № 176129, ответ № 258742]
26.06.2012, 12:15 »
Александр Сергеевич
Спасибо!!! Все правильно!!! [вопрос № 186416, ответ № 271307]

РАЗДЕЛ • С / С++

Создание программ на языках C и C++.

[администратор рассылки: Андрей Кузнецов aka Dr_Andrew (Старший модератор)]

Лучшие эксперты в этом разделе

Лысков Игорь Витальевич
Статус: Старший модератор
Рейтинг: 737
solowey
Статус: 5-й класс
Рейтинг: 219
Коцюрбенко Алексей aka Жерар
Статус: Мастер-Эксперт
Рейтинг: 191

Перейти к консультации №:
 

Консультация онлайн # 190300
Раздел: • С / С++
Автор вопроса: Посетитель - 399158 (Посетитель)
Отправлена: 15.12.2016, 19:33
Поступило ответов: 1

Уважаемые эксперты! Пожалуйста, ответьте на вопрос:
Реализуйте класс, представляющий понятие "двоичное дерево поиска". Протестируйте его работу.
Почему 2 функции?

template <typename T>
void Bintree<T>::insert(Node* &xx, T k) {
	Node *z = new Node(k);
	if (xx == nullptr) { //если дерева нет то формируем корень
		xx = z;
		xx->parent = xx->left = xx->right = nullptr;
		return;
	}
	Node *x = xx;
	while (x != nullptr) {
		if (z->key > x->key) {
			if (x->right != nullptr) x = x->right;
			else {
				z->parent = x;
				x->right = z;
				break;
			}
		}
		else if (z->key < x->key) {
			if (x->left != nullptr) x = x->left;
			else {
				z->parent = x;
				x->left = z;
				break;
			}
		}
	}
}


Почему тут 2 функции:

template <typename T>
void Bintree<T>::insert(T k) {//вставка
    insert(head, k);
}
 
template <typename T>
void Bintree<T>::insert(Node* &xx, T k) {
    Node *z = new Node(k);
    if (xx == nullptr) { //если дерева нет то формируем корень
        xx = z;
        xx->parent = xx->left = xx->right = nullptr;
        return;
    }
    Node *x = xx;
    while (x != nullptr) {
        if (z->key > x->key) {
            if (x->right != nullptr) x = x->right;
            else {
                z->parent = x;
                x->right = z;
                break;
            }
        }
        else if (z->key < x->key) {
            if (x->left != nullptr) x = x->left;
            else {
                z->parent = x;
                x->left = z;
                break;
            }
        }
    }
}


и тут:

template <typename T>
void Bintree<T>::show() {
    show(head, 20);
}
 
template <typename T>//показываем элементы дерева
void Bintree<T>::show(Node* head, int sp) {
    if (head == nullptr) return;
    show(head->right, sp + 5);
    for (int i = 0; i < sp; ++i) std::cout << ' ';
    std::cout << head->key << std::endl; 
    show(head->left, sp + 5);
}


можете объяснить?

Состояние: Консультация закрыта

Ответ # 274446 от Лысков Игорь Витальевич (Старший модератор)

Здравствуйте, Посетитель - 399158!
Вот Вам программа на основе приведенного кода.
В данной программе для вывода используется рекурсия, поэтому задавать текущий узел параметром
необходимо, но тогда вызываемую функцию с параметрами необходимо определить, как private
Удаление дерева тоже реализовано рекурсивно, поэтому сделано аналогично

Для вставки передавать корень параметром необходимости нет.
Показано, как задавать параметр по-умолчанию.
Кое-что подправил, прокомментировал

#include <iostream>

using namespace std;

#define	nullptr 0

struct Node
{
	int		key;
	Node	*left;
	Node	*right;
	Node	*parent;
};

template<class T>
class Bintree
{
public:
	//конструктор
	Bintree<T>(){head = nullptr;};

	//деструктор
	~Bintree(void);	

	//вставка
	void insert(T k);

	//вывод
	void show(int sp=20);

private:
	Node*	head;
	void FreeNode(Node *node);
	void show(Node *node, int sp);
};

template<class T>
void Bintree<T>::FreeNode(Node *node)
{
	if (node)
	{
		Bintree::FreeNode(node->left);	//левого потомка
		Bintree::FreeNode(node->right);	//правого потомка
		delete node;					//память самого узла
	}
}

template<class T>
Bintree<T>::~Bintree()
{
	Bintree<T>::FreeNode(head);
}

template <typename T>
void Bintree<T>::insert(T k) 
{
	Node *z = new Node;			//создаем новый узел
	z->key = k;					//ключ
	z->left = z->right = nullptr; //обнулим указатели на потомков

	if (head == nullptr)		//был ли корень?
	{							//если дерева нет то формируем корень
		z->parent = nullptr;	//у корня родителя нет
        head = z;				//сохраним как корень
    }
	else
	{
		Node *x = head;			//начинаем обход с корня
		while (1)				//по всем узлам
		{
			if (z->key > x->key) //если ключ нового узла больше текущего
			{
				if (x->right != nullptr)//и если правый потомок непустой
					x = x->right;		//то правого потомка делаем текущим
				else 
				{						//правый пустой
					z->parent = x;		//текущий для нового будет родителем
					x->right = z;		//а правым потомком текущего станет новый
					break;				//новый узел вставлен в дерево - выходим из цикла
				}
			}
			else if (z->key < x->key) //если ключ нового узла меньше текущего
			{
				if (x->left != nullptr) //и левый потомок непустой
					x = x->left;		//то левого потомка делаем текущим
				else 
				{						//левый пустой
					z->parent = x;		//текущий для нового будет родителем
					x->left = z;		//а левым потомком текущего станет новый
					break;				//новый узел вставлен в дерево - выходим из цикла
				}
			}
			else
			{
				delete z;				//если равно, то удалим созданный узел (игнорируем!)
				break;					//и выходим из цикла
			}
		}
	}
}

template <typename T>	//показываем элементы дерева
void Bintree<T>::show(int sp) 
{
	Bintree<T>::show(head, sp);
}

template <typename T>	//показываем элементы дерева
void Bintree<T>::show(Node *node, int sp=20) 
{
    if (node == nullptr) 
		return;
    show(node->right, sp + 5);
    for (int i = 0; i < sp; ++i) cout << ' ';
    cout << node->key << endl; 
    show(node->left, sp + 5);
}

int main()
{
	Bintree<int> tree;	//создаем класс
	tree.insert(5);		//вставим несколько узлов
	tree.insert(3);
	tree.insert(7);
	tree.insert(6);
	tree.show();		//выведем с позиции 20 (по умолчанию)
	tree.insert(4);		//добавим еще несколько узлов
	tree.insert(8);
	tree.show(0);		//выведем с 0 позиции
	tree.insert(8);		//пытаемся добавить узел с существующим ключом
	tree.show(0);		//выводим
	return 0;
}


Консультировал: Лысков Игорь Витальевич (Старший модератор)
Дата отправки: 16.12.2016, 13:50

Рейтинг ответа:

0

[подробно]

Сообщение
модераторам

Отправлять сообщения
модераторам могут
только участники портала.
ВОЙТИ НА ПОРТАЛ »
регистрация »

Мини-форум консультации № 190300

Лысков Игорь Витальевич
Старший модератор

ID: 7438

# 1

= общий = | 15.12.2016, 20:26 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер
Посетитель - 399158:

Почему 2 функции? Ну сделали так smile Для удобства.
Например, в insert чтобы не задавать явно корень, а только ключ, вызываем первую функцию,
которая вызывает вторую, передавая ей адрес корня и ключ.
В зависимости от реализации, второй способ вызова может быть даже и невозможен, а может и возможен.

В функции show примерно аналогично. При вызове без параметров вызывается вторая
с параметрами по-умолчанию, с указанием корня и количества пробелов, равным 20.
При желании, можно вызывать сразу вторую с явным указанием корня и количества пробелов
(при условии, что есть доступ к корню дерева!).

К слову, в С++ одно и тоже имя функции, но с разными параметрами приводит к двум разным функциям.
Так что, мы имеем по две разные функции...

=====
Каждый выбирает по себе -
Щит и латы, посох и заплаты.
Меру окончательной расплаты
Каждый выбирает для себя.

• Отредактировал: Лысков Игорь Витальевич (Старший модератор)
• Дата редактирования: 15.12.2016, 20:28

Посетитель - 399158
Посетитель

ID: 399158

# 2

= общий = | 15.12.2016, 22:11 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер

а можете рассказать, как происходит вставка у нас? insert

Посетитель - 399158
Посетитель

ID: 399158

# 3

= общий = | 16.12.2016, 10:34 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер

Вопрос, почему именно 2 функции, если мы можем в одной сделать все. Какие плюсы и минусы?

Лысков Игорь Витальевич
Старший модератор

ID: 7438

# 4

= общий = | 16.12.2016, 11:25 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер
Посетитель - 399158:

Я скажу больше: на мой взгляд, так делать, в общем-то, неправильно.
1) Становится доступным передача корня, что уже нехорошо;
2) С другой стороны, корень и так доступен, если он определен в данном классе. Нет никакой необходимости передавать его параметром;
3) Для задания параметра со значением по-умолчанию, можно же написать в списке параметров sp=20. И все!
Как не крути, можно все сделать намного проще и надежней!

Я не говорю, что не будет работать. Будет, но "некрасиво". Плюс имеем заложенную мину с некорректной передачей параметром "левого" корня.

Плюсов тут нет вообще. Так было сделано, чтобы вызывать с меньшим числом параметров. Но! Это можно сделать лучше!

=====
Каждый выбирает по себе -
Щит и латы, посох и заплаты.
Меру окончательной расплаты
Каждый выбирает для себя.

Посетитель - 399158
Посетитель

ID: 399158

# 5

= общий = | 16.12.2016, 11:27 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер

можете написать как?

Лысков Игорь Витальевич
Старший модератор

ID: 7438

# 6

= общий = | 16.12.2016, 11:29 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер
Посетитель - 399158:

А как работает insert, почитайте, как вообще работает двоичное дерево поиска smile
В Инете все разложено по полочкам. Учитесь работать самостоятельно.

=====
Каждый выбирает по себе -
Щит и латы, посох и заплаты.
Меру окончательной расплаты
Каждый выбирает для себя.

Лысков Игорь Витальевич
Старший модератор

ID: 7438

# 7

= общий = | 16.12.2016, 11:43 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер
Посетитель - 399158:

© Цитата:
можете написать как?
В течение дня, как будет время, нарисую что-нибудь... smile

=====
Каждый выбирает по себе -
Щит и латы, посох и заплаты.
Меру окончательной расплаты
Каждый выбирает для себя.

Посетитель - 399158
Посетитель

ID: 399158

# 8

= общий = | 16.12.2016, 11:48 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер

спасибо

Лысков Игорь Витальевич
Старший модератор

ID: 7438

# 9

= общий = | 16.12.2016, 13:25 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер
Посетитель - 399158:

Вот Вам программа.
Некоторое уточнение к предыдущему.
В данной программе для вывода используется рекурсия, поэтому задавать текущий узел параметром
необходимо, но тогда вызываемую функцию с параметрами необходимо определить, как private
Как и удаление дерева...
Для вставки передавать корень параметром необходимости нет.
Кое-что подправил, прокомментировал smile

#include <iostream>

using namespace std;

#define	nullptr 0

struct Node
{
	int		key;
	Node	*left;
	Node	*right;
	Node	*parent;
};

template<class T>
class Bintree
{
public:
	//конструктор
	Bintree<T>(){head = nullptr;};

	//деструктор
	~Bintree(void);	

	//вставка
	void insert(T k);

	//вывод
	void show(int sp=20);

private:
	Node*	head;
	void FreeNode(Node *node);
	void show(Node *node, int sp);
};

template<class T>
void Bintree<T>::FreeNode(Node *node)
{
	if (node)
	{
		Bintree::FreeNode(node->left);	//левого потомка
		Bintree::FreeNode(node->right);	//правого потомка
		delete node;					//память самого узла
	}
}

template<class T>
Bintree<T>::~Bintree()
{
	Bintree<T>::FreeNode(head);
}

template <typename T>
void Bintree<T>::insert(T k) 
{
	Node *z = new Node;			//создаем новый узел
	z->key = k;					//ключ
	z->left = z->right = nullptr; //обнулим указатели на потомков

	if (head == nullptr)		//был ли корень?
	{							//если дерева нет то формируем корень
		z->parent = nullptr;	//у корня родителя нет
        head = z;				//сохраним как корень
    }
	else
	{
		Node *x = head;			//начинаем обход с корня
		while (1)				//по всем узлам
		{
			if (z->key > x->key) //если ключ нового узла больше текущего
			{
				if (x->right != nullptr)//и если правый потомок непустой
					x = x->right;		//то правого потомка делаем текущим
				else 
				{						//правый пустой
					z->parent = x;		//текущий для нового будет родителем
					x->right = z;		//а правым потомком текущего станет новый
					break;				//новый узел вставлен в дерево - выходим из цикла
				}
			}
			else if (z->key < x->key) //если ключ нового узла меньше текущего
			{
				if (x->left != nullptr) //и левый потомок непустой
					x = x->left;		//то левого потомка делаем текущим
				else 
				{						//левый пустой
					z->parent = x;		//текущий для нового будет родителем
					x->left = z;		//а левым потомком текущего станет новый
					break;				//новый узел вставлен в дерево - выходим из цикла
				}
			}
			else
			{
				delete z;				//если равно, то удалим созданный узел (игнорируем!)
				break;					//и выходим из цикла
			}
		}
	}
}

template <typename T>	//показываем элементы дерева
void Bintree<T>::show(int sp) 
{
	Bintree<T>::show(head, sp);
}

template <typename T>	//показываем элементы дерева
void Bintree<T>::show(Node *node, int sp=20) 
{
    if (node == nullptr) 
		return;
    show(node->right, sp + 5);
    for (int i = 0; i < sp; ++i) cout << ' ';
    cout << node->key << endl; 
    show(node->left, sp + 5);
}

int main()
{
	Bintree<int> tree;	//создаем класс
	tree.insert(5);		//вставим несколько узлов
	tree.insert(3);
	tree.insert(7);
	tree.insert(6);
	tree.show();		//выведем с позиции 20 (по умолчанию)
	tree.insert(4);		//добавим еще несколько узлов
	tree.insert(8);
	tree.show(0);		//выведем с 0 позиции
	tree.insert(8);		//пытаемся добавить узел с существующим ключом
	tree.show(0);		//выводим
	return 0;
}

=====
Каждый выбирает по себе -
Щит и латы, посох и заплаты.
Меру окончательной расплаты
Каждый выбирает для себя.

• Отредактировал: Лысков Игорь Витальевич (Старший модератор)
• Дата редактирования: 16.12.2016, 13:26

Посетитель - 399158
Посетитель

ID: 399158

# 10

= общий = | 16.12.2016, 13:32 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер

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

 

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

Яндекс Rambler's Top100

главная страница | поддержка | задать вопрос | интересные статьи

Время генерирования страницы: 0.24739 сек.

© 2001-2017, Портал RFPRO.RU, Россия
Авторское право: ООО "Мастер-Эксперт Про"
Калашников О.А.  |  Гладенюк А.Г.
Версия системы: 7.40 от 02.09.2016
Бесплатные консультации онлайн