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

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Создать бинарное дерево 
:(
    Опции темы
shilovec5377
  Дата 7.6.2015, 12:36 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

Репутация: нет
Всего: нет
Всем привет. По условию нужно
Код

 Используя классы, создать бинарное дерево. В узлах бинарного дерева имеется элемент (целое число), являющийся ключом. В записях дерева хранятся также целые числа. В дереве не более 50 узлов. Элементы дерева заполнять с помощью функции генерации случайных чисел. Реализовать функцию вывода дерева на экран.

посмотрите пж, меня смущает вывод этого дерева на экран и правильно ли я это сделал
Код

#include <iostream>
#include <conio.h>
#include <string.h>
using namespace std;
struct btree
{
   int key;
   char link [50];
   btree *left;
   btree *right;
};
//----------------------------------------------//
 
btree *First(btree **root, int val)
{
   // Обязательно выделяем память
   (*root)= new btree;
   (*root)->key= val;
   (*root)->left= NULL;
   (*root)->right= NULL;
   return *root;
}
//----------------------------------------------//
btree *AddLeaf(btree *root, int val)
{
   if (root == NULL)
      root= First(&root, val);
   else
   {
      if (val < root->key)
      {
         if (root->left == NULL)
            First(&(root->left), val);
         else
            AddLeaf(root->left, val);
      }
      if (val > root->key)
      {
         if (root->right == NULL)
            First(&(root->right), val);
         else
            AddLeaf(root->right, val);
      }
   }
   return root;
}
//----------------------------------------------//
void Print(btree *root)
{
   if (root)
   {
      cout << root->key << " ";
      Print(root->left);
      Print(root->right);
   }
}
//----------------------------------------------//
int main (int argc, char **argv)
{
   btree *a;
   First(&a, 20);
   for (int i=0;i<10;i++)
     AddLeaf(a, rand()%50);
   Print(a);
   getch();
   return 0;
} 
PM MAIL   Вверх
feodorv
Дата 7.6.2015, 13:59 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


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

Репутация: 11
Всего: 45
Цитата(shilovec5377 @  7.6.2015,  12:36 Найти цитируемый пост)
меня смущает вывод этого дерева на экран

Если Вас интересует вывод в возрастающем порядке, то это можно сделать так:
Код

void Print(btree *root)
{
   if (root)
   {
      Print(root->left);
      cout << root->key << " ";
      Print(root->right);
   }
}



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


Новичок



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

Репутация: нет
Всего: нет
а помогите пожалуйста реализовать функцию, которая удаляет из дерева все узлы-дубликаты, т.е. узлы с повторяющимися значениями.
PM MAIL   Вверх
feodorv
Дата 7.6.2015, 15:30 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


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

Репутация: 11
Всего: 45
Цитата(shilovec5377 @  7.6.2015,  14:47 Найти цитируемый пост)
т.е. узлы с повторяющимися значениями

Не понял. С "повторяющимися значениями" чего?


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


Новичок



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

Репутация: нет
Всего: нет
если в дереве встречаются повторяющиеся значения, например 2 две вершины  и у каждой значение =3 или 5 или 6, что бы не было повторяющихся значений
PM MAIL   Вверх
feodorv
Дата 7.6.2015, 15:45 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


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

Репутация: 11
Всего: 45
У Вас в условии задачи стоит:
Цитата(shilovec5377 @  7.6.2015,  12:36 Найти цитируемый пост)
В узлах бинарного дерева имеется элемент (целое число), являющийся ключом. В записях дерева хранятся также целые числа.

Итого: у Вас есть целочисленное значение ключа, а есть куча целочисленных значений, хранящихся в "записях дерева" (тех же узлах?) Какие именно "повторяющиеся значения" из этих значений Вы имеете в виду?


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


Новичок



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

Репутация: нет
Всего: нет
вот мое условие: 
Код

Используя классы, создать бинарное дерево. В узлах бинарного дерева имеется элемент (целое число), являющийся ключом. В записях дерева хранятся также целые числа. В дереве не более 50 узлов. Элементы дерева заполнять с помощью функции генерации случайных чисел. Реализовать функцию вывода дерева на экран. Реализовать функцию, которая удаляет из дерева все узлы-дубликаты, т.е. узлы с повторяющимися значениями. Реализовать функцию, которая сортирует узлы дерева по возрастанию его информационной части.
PM MAIL   Вверх
feodorv
Дата 7.6.2015, 16:23 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


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

Репутация: 11
Всего: 45
Цитата(shilovec5377 @  7.6.2015,  15:55 Найти цитируемый пост)
вот мое условие

И? Ответить на вопрос Вы можете?

И даже если Вы уверенно заявите, что имеется в виду "значение ключа", то:
  • чтобы иметь повторяющиеся значения ключа, нужно предоставить возможность добавления в дерево узлов с повторяющимися значением ключа. В Вашем коде такая возможность отсутствует напрочь:
    Цитата(shilovec5377 @  7.6.2015,  12:36 Найти цитируемый пост)
          if (val < root->key)
          {
             if (root->left == NULL)
                First(&(root->left), val);
             else
                AddLeaf(root->left, val);
          }
          if (val > root->key)
          {
             if (root->right == NULL)
                First(&(root->right), val);
             else
                AddLeaf(root->right, val);
          }
    Здесь при совпадении ключей (val == root->key) новый узел просто не добавляется в дерево.
  • даже если в дереве найдутся два узла с совпадающими значениями ключа, то какой узел из них следует удалить, а какой оставить? У Вас есть критерий выбора?
PS Как понимать "возрастание его информационной части" при наличии в информационной части нескольких целочисленных значений?


Это сообщение отредактировал(а) feodorv - 7.6.2015, 16:24


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


Новичок



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

Репутация: нет
Всего: нет
вот такое задание дали, у меня хоть правильно создается дерево и заполняется?
PM MAIL   Вверх
feodorv
Дата 7.6.2015, 21:04 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


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

Репутация: 11
Всего: 45
Цитата(shilovec5377 @  7.6.2015,  16:42 Найти цитируемый пост)
вот такое задание дали

Я могу только развести руками.


Цитата(shilovec5377 @  7.6.2015,  16:42 Найти цитируемый пост)
у меня хоть правильно создается дерево и заполняется

На вид, должно работать)))


--------------------
Напильник, велосипед, грабли и костыли - основные инструменты программиста...
PM MAIL   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
Earnest Daevaorn

Добро пожаловать!

  • Черновик стандарта C++ (за октябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика(4.4мб).
  • Черновик стандарта C (за сентябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика (3.4мб).
  • Прежде чем задать вопрос, прочтите это и/или это!
  • Здесь хранится весь мировой запас ссылок на документы, связанные с C++ :)
  • Не брезгуйте пользоваться тегами [code=cpp][/code].
  • Пожалуйста, не просите написать за вас программы в этом разделе - для этого существует "Центр Помощи".
  • C++ FAQ

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

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


 




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


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

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