Модераторы: LSD, AntonSaburov
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> нужно ли удалять дублирующее элементы? в двоичном дереве  
V
    Опции темы
Wyatt
Дата 20.6.2010, 15:57 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

Репутация: нет
Всего: нет
Есть допустим у нас класс который реализует Binary Tree. 
вопрос в следующем: допустим есть дерево:

Код

        obj.insert( "A" );
        obj.insert( "B" );

        obj.insert( "D" );
        obj.insert( "F" );

        obj.insert( "G" );
        obj.insert( "E" );

        obj.insert( "M" );
        obj.insert( "N" );
        obj.insert( "F" ); 


Код

height: 6
size: 8


но size 9 то есть F считает как один элемент. Вот не знаю это правильно или нет ? 
PM MAIL   Вверх
powerOn
Дата 20.6.2010, 18:17 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


software saboteur
****


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

Репутация: 47
Всего: 159
Я, честно говоря, вообще не понял суть вопроса.


--------------------
user posted image нет времени думать - нужно писать КОД!
PM MAIL   Вверх
kemiisto
Дата 20.6.2010, 18:26 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Дикий Кот. =^.^=
****
Награды: 1



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

Репутация: 5
Всего: 160
Цитата(Wyatt @  20.6.2010,  16:57 Найти цитируемый пост)
Вот не знаю это правильно или нет ?  

Хм... А как такое может быть правильно? Добавили в древовидную структуру данных 9 элементов, а метод подсчёта элементов явно ошибочно рапортует только о 8. Или возможно где=то в другом месте ошибка...

Цитата(Wyatt @  20.6.2010,  16:57 Найти цитируемый пост)
но size 9 то есть F считает как один элемент

Вы уверены, что причина в этом? У Вас есть исходный код?


--------------------
XMPP-канал.

Unit testing isn't enough. You need static typing.

Пей, кури, пиши на си! smile
PM MAIL WWW GTalk Jabber   Вверх
Wyatt
Дата 20.6.2010, 18:26 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

Репутация: нет
Всего: нет
вообщем есть класс BinaryTree. 

добавлаю я в дерево 

следующие значения 
Код

        BinaryTree obj = new BinaryTree();
        obj.insert( 2 );
        obj.insert( 7 );
        obj.insert( 5 );
        obj.insert( 9 );
        obj.insert( 4 );
        obj.insert( 2 );
        obj.insert( 6 );
        obj.insert( 5 );
        obj.insert( 11 );
        System.out.println("height: " + obj.height());
        System.out.println("size: " + obj.size());


на выходе получаю что size равно 7(хотя значений 9, то есть одинаковые элементы удалиться ) а height: 3. 

вот я и хочу узнать правильно ли то что одинаковые элементы удаляются ? что на выходе мы получаем size 7 вместо 9

Добавлено через 44 секунды
Вы уверены, что причина в этом? У Вас есть исходный код?  да есть 
PM MAIL   Вверх
kemiisto
Дата 20.6.2010, 18:33 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Дикий Кот. =^.^=
****
Награды: 1



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

Репутация: 5
Всего: 160
Цитата(Wyatt @  20.6.2010,  19:26 Найти цитируемый пост)
вот я и хочу узнать правильно ли то что одинаковые элементы удаляются ? 

Если Вам нужно именно бинарное древо, то там можно иметь сколько угодно узлов с одинаковым значением. Главное, чтобы выполнялось рекурсивное определение
Цитата
<дерево> ::= ( <данные> <дерево> <дерево> ) | nil .



--------------------
XMPP-канал.

Unit testing isn't enough. You need static typing.

Пей, кури, пиши на си! smile
PM MAIL WWW GTalk Jabber   Вверх
Wyatt
Дата 20.6.2010, 18:34 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

Репутация: нет
Всего: нет
....

Это сообщение отредактировал(а) Wyatt - 21.6.2010, 21:12
PM MAIL   Вверх
kemiisto
Дата 20.6.2010, 18:48 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Дикий Кот. =^.^=
****
Награды: 1



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

Репутация: 5
Всего: 160
Wyatt, ну вот! Ошибка простенькая.

Код

    private Node insert( Comparable data, Node current ) {
        if ( current == null ) {
            size++;
            current = new Node( data, null, null );
        } else if ( data.compareTo( current.data ) < 0 ) {
            current.left = insert( data, current.left );
        } else if ( data.compareTo( current.data ) > 0 ) {
            current.right = insert( data, current.right );
        }
        return current;
    }

А что делать, если data.compareTo( current.data ) окажеться нулём у Вас не описано! Вот ничего и не происходит при добавлении элемента, значение которого уже есть в древе. Нужно одно из неравенств сделать нестрогим. 

А уж не двоичное ли древо поиска Вы пишете? Тогда надо так:
Код

    private Node insert( Comparable data, Node current ) {
        if ( current == null ) {
            size++;
            current = new Node( data, null, null );
        } else if ( data.compareTo( current.data ) < 0 ) {
            current.left = insert( data, current.left );
        } else if ( data.compareTo( current.data ) >= 0 ) {
            current.right = insert( data, current.right );
        }
        return current;
    }


Тут бы можно упростить, но так как это Java, я не буду соваццо. smile 

Это сообщение отредактировал(а) kemiisto - 20.6.2010, 18:58


--------------------
XMPP-канал.

Unit testing isn't enough. You need static typing.

Пей, кури, пиши на си! smile
PM MAIL WWW GTalk Jabber   Вверх
Wyatt
Дата 20.6.2010, 18:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

Репутация: нет
Всего: нет
да двоичное )).
только чтото неправильно возвращает  height: 4. а по идее в этом примере должно возвращать 3 (( 

или я может не правильно тестирую ? 

можете привести пример как тестировать дерево ?
я сейчас делаю вот так: 
Код

        BinaryTree obj = new BinaryTree();
        obj.insert( 2 );
        obj.insert( 7 );
        obj.insert( 5 );
        obj.insert( 9 );
        obj.insert( 4 );
        obj.insert( 2 );
        obj.insert( 6 );
        obj.insert( 5 );
        obj.insert( 11 );
        System.out.println("height: " + obj.height());
        System.out.println("size: " + obj.size());


и так как я понимаю должно быть в дереве 9 элементов и height должно быть 3 ? правильно ?

Это сообщение отредактировал(а) Wyatt - 21.6.2010, 09:54
PM MAIL   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Java"
LSD   AntonSaburov
powerOn   tux
javastic
  • Прежде, чем задать вопрос, прочтите это!
  • Книги по Java собираются здесь.
  • Документация и ресурсы по Java находятся здесь.
  • Используйте теги [code=java][/code] для подсветки кода. Используйтe чекбокс "транслит", если у Вас нет русских шрифтов.
  • Помечайте свой вопрос как решённый, если на него получен ответ. Ссылка "Пометить как решённый" находится над первым постом.
  • Действия модераторов можно обсудить здесь.
  • FAQ раздела лежит здесь.

Если Вам помогли, и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, LSD, AntonSaburov, powerOn, tux, javastic.
 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Java: Общие вопросы | Следующая тема »

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


 




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


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

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