Модераторы: bsa
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Нужно найти значение в дереве. 
:(
    Опции темы
sswt
Дата 2.11.2015, 15:31 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

Репутация: нет
Всего: нет
Нужно найти значение в дереве. И как всегда у меня баги((( Где ошибки у меня?
Мой код:
Код

const SortedBinaryTree::Node* FindValue(const SortedBinaryTree* tree, int value)
{
    const SortedBinaryTree::Node* node = tree->root;
    if (node->value == value)
        return node;
    else
    if (node->leftNode->value == value)
        return node;
    else
    if (node->rightNode->value == value)
        return node;
    else
        FindValue(tree->root, value);
PM MAIL   Вверх
math64
Дата 2.11.2015, 15:58 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2505
Регистрация: 12.4.2007

Репутация: 12
Всего: 72
Код

const SortedBinaryTree::Node* FindValue(const SortedBinaryTree* tree, int value)
{
    return FindValue(tree->root, value);
}
const SortedBinaryTree::Node* FindValue(const SortedBinaryTree::Node* node, int value)
{
    if (node == NULL)
      return NULL;
    int nodeValue = node->value;
    if (nodeValue == value)
        return node;
    if (nodeValue < value)
      return FindValue(node->leftNode, value);
    else
      return FindValue(node->rightNode, value);
}

+ InsertValue() должен добавлять узел в дерево в правильное место.

Это сообщение отредактировал(а) math64 - 2.11.2015, 16:00
PM   Вверх
feodorv
Дата 2.11.2015, 16:01 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


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

Репутация: 12
Всего: 45
С рекурсией:
Код
const SortedBinaryTree::Node* FindValue( const SortedBinaryTree::Node* node, int value)
{
    if( node == nullptr ) return nullptr;
    if( value == node->value ) return node;
    return FindValue( (value < node->value) ? node->leftNode : node->rightNode, value);
}


Без рекурсии:
Код
const SortedBinaryTree::Node* FindValue( const SortedBinaryTree::Node* node, int value)
{
    while( node != nullptr )
    {
       if( value == node->value ) break;
       node = (value < node->value) ? node->leftNode : node->rightNode;
    }

    return node;
}


Использовать:
Код

if( (node = FindNode( tree->root, value)) != nullptr ) ...;



--------------------
Напильник, велосипед, грабли и костыли - основные инструменты программиста...
PM MAIL   Вверх
sswt
Дата 2.11.2015, 16:04 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

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

Это сообщение отредактировал(а) sswt - 2.11.2015, 16:38
PM MAIL   Вверх
sswt
Дата 2.11.2015, 16:53 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

Репутация: нет
Всего: нет
math64,  у вас  бага . Так  должно быть: 
    
Код


    if (nodeValue > value)
      return FindValue(node->leftNode, value);
    else
      return FindValue(node->rightNode, value);


Добавлено через 9 минут и 7 секунд
feodorv,  а вот это : 
Код

 node = (value < node->value) ? node->leftNode : node->rightNode;
 можно так  записать?:
Код

f (node->value > value)
            return node->leftNode;
        else 
            return node->rightNode;
PM MAIL   Вверх
feodorv
Дата 2.11.2015, 21:27 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


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

Репутация: 12
Всего: 45
Цитата(sswt @  2.11.2015,  16:53 Найти цитируемый пост)
можно так  записать?

Только так:
Код

if (node->value > value)
    node = node->leftNode;
else 
    node = node->rightNode;



Цитата(sswt @  2.11.2015,  16:53 Найти цитируемый пост)
у вас  бага

Это не бага, это фича. Выбор знака > или < зависит от направления сортировки (от меньших значений к большим или, наоборот, от больших значений к меньшим), каковое Вы не указали.

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


--------------------
Напильник, велосипед, грабли и костыли - основные инструменты программиста...
PM MAIL   Вверх
sswt
Дата 2.11.2015, 21:58 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

Репутация: нет
Всего: нет
feodorv,  хм я  думала влево идут значения которые меньше корня а в право  больше в дереве. 
PM MAIL   Вверх
feodorv
Дата 2.11.2015, 22:06 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


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

Репутация: 12
Всего: 45
Цитата(sswt @  2.11.2015,  21:58 Найти цитируемый пост)
feodorv,  хм я  думала влево идут значения которые меньше корня а в право  больше в дереве. 

Ну, это зависит от задачи. Сортировка в обратном порядке тоже широко используется))) Вы же нигде не задали направление сортировки, поэтому и такой способ сортировки отвечает начальным условиям задачи. Если нужно сортировать от меньших значений к большим, тогда, да, 
Цитата(sswt @  2.11.2015,  16:53 Найти цитируемый пост)
    if (nodeValue > value)




--------------------
Напильник, велосипед, грабли и костыли - основные инструменты программиста...
PM MAIL   Вверх
math64
Дата 3.11.2015, 08:16 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2505
Регистрация: 12.4.2007

Репутация: 12
Всего: 72
Цитата(feodorv @  2.11.2015,  21:27 Найти цитируемый пост)
Цитата(sswt @  2.11.2015,  16:53 Найти цитируемый пост)
у вас  бага

Это не бага, это фича. Выбор знака > или < зависит от направления сортировки (от меньших значений к большим или, наоборот, от больших значений к меньшим), каковое Вы не указали.

Главное - чтобы FindValue и InsertValue сортировали одинаково.
В норме leftNode и rightNode должны быть приватными и пользватель класса не видит какой порядок сортировки внутри дерева.
Но sswt по какой-то причине не хочет пользоваться классами (хотя пишет на C++)

Это сообщение отредактировал(а) math64 - 3.11.2015, 08:17
PM   Вверх
math64
Дата 3.11.2015, 08:31 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2505
Регистрация: 12.4.2007

Репутация: 12
Всего: 72
Чтобы добиться согласованности, можно добавить вспомогательную функцию: 
Код

SortedBinaryTree::Node** FindPlaceForInsertValue(const SortedBinaryTree* tree, int value);
const SortedBinaryTree::Node* FindValue(const SortedBinaryTree* tree, int value)
{
SortedBinaryTree::Node** placeForInsert = FindPlaceForInsertValue(tree, value);
    if (*placeForInsert == nullptr)
      return nullptr;
    return *placeForInsert;
}
const SortedBinaryTree::Node* InsertValue(const SortedBinaryTree* tree, int value)
{
SortedBinaryTree::Node** placeForInsert = FindPlaceForInsertValue(tree, value);
    if (*placeForInsert == nullptr) {
      *placeForInsert = new SortedBinaryTree::Node;
      (*placeForInsert)->leftNode = nullptr;
      (*placeForInsert)->rightNode = nullptr;
      (*placeForInsert)->value = value;
    }
    return *placeForInsert;
}

Но после вставки узла рекомендуется делать балансировку:
Если добавлять узлы в порадке 1, 2, 3, 4, 5 - узлы будут добавляться только в rightNode (или leftNode - в зависимости от порядка сортировки).
PM   Вверх
feodorv
Дата 3.11.2015, 10:56 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


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

Репутация: 12
Всего: 45
Цитата(math64 @  3.11.2015,  08:16 Найти цитируемый пост)
Но sswt по какой-то причине не хочет пользоваться классами (хотя пишет на C++)

Просто sswt думает, что пишет на C.


Цитата(math64 @  3.11.2015,  08:16 Найти цитируемый пост)
Главное - чтобы FindValue и InsertValue сортировали одинаково.

Это да. Ну, и обход дерева тоже делать согласовано)))


Цитата(math64 @  3.11.2015,  08:31 Найти цитируемый пост)
Но после вставки узла рекомендуется делать балансировку

Думаю, нас это ещё ждет впереди smile 


--------------------
Напильник, велосипед, грабли и костыли - основные инструменты программиста...
PM MAIL   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "C/C++: Для новичков"
JackYF
bsa

Запрещается!

1. Публиковать ссылки на вскрытые компоненты

2. Обсуждать взлом компонентов и делиться вскрытыми компонентами

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

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, JackYF, bsa.
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Для новичков | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.1238 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.