Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.50/18: Рейтинг темы: голосов - 18, средняя оценка - 4.50
32 / 21 / 4
Регистрация: 18.11.2012
Сообщений: 933
1

Определить количество уровней двоичного дерева поиска

03.08.2017, 21:45. Просмотров 3205. Ответов 15
Метки нет (Все метки)

Привет всем неравнодушным)!
Кликните здесь для просмотра всего текста
Напишите элемент-функцию depth, принимающую в качестве аргумента двоичное дерево и определяющую, сколько уровней оно содержит.

Вот такое вот, казалось бы, простое задание, которое, тем не менее, привело меня в тупик. Не могу сообразить, как написать эту функцию, может кто-нибудь даст дельный совет, сам, похоже, не смогу решить.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
03.08.2017, 21:45
Ответы с готовыми решениями:

Частотный словарь из слов текстового файла в виде дерева двоичного поиска
Задача: Построить частотный словарь из слов текстового файла в виде дерева двоичного поиска....

Сформировать бинарное дерево поиска и определить максимальную глубину дерева
Добрый день всем. По задаче необходимо сформировать бинарное дерево поиска и определить...

Расчет количества уровней в бинарном дерева
Доброго всем времени суток, есть бинарное дерево с функциями добавления, удаления и печати, нужно...

Пример двоичного дерева
Здравствуйте! Возникла мысль попробовать реализовать двоичное дерево в c++ для этого решил сначала...

15
129 / 101 / 58
Регистрация: 26.10.2013
Сообщений: 306
03.08.2017, 22:15 2
C++
1
2
3
4
5
6
7
8
9
10
int height(Node *node)
{
    if (!node)
        return 0;
 
    int h_l = height(node->left);
    int h_r = height(node->right);
 
    return std::max(h_l, h_r) + 1;
}
1
Заблокирован
03.08.2017, 22:26 3
Цитата Сообщение от stzer Посмотреть сообщение
int height(Node *node)
А почему int? Разве высота может быть отрицательна?
0
32 / 21 / 4
Регистрация: 18.11.2012
Сообщений: 933
03.08.2017, 22:57  [ТС] 4
Цитата Сообщение от stzer Посмотреть сообщение
return std::max(h_l, h_r) + 1;
Что за max?

Добавлено через 3 минуты
А если в элемент-функции возвращаемое значение void?
Я суть решения задачи понять не могу, мне код, по большому счёту, не нужен.
0
129 / 101 / 58
Регистрация: 26.10.2013
Сообщений: 306
03.08.2017, 23:18 5
Liss29, хорошо. Тут просто используется рекурсия. Допустим, у нас есть дерево T с корнем R. Есть два узла, левый (L) и правый (R). Что имеем: высота дерева T на 1 больше максимальной высоты поддеревьев - max(height(L), height(R)). Сначала считаем высоту левого поддерева L, потом правого R. Высоту L и R находим аналогично - 1 + max(высота левого поддерева L, высота правого поддерева R). И т.д. Чувствуете рекурсию? Как только опускаемся до узла, у которого нет потомка, рекурсия останавливается.

Все ответы на вопросы можете найти в книге R. Sedgewick. Alghorithms in C++.
0
32 / 21 / 4
Регистрация: 18.11.2012
Сообщений: 933
03.08.2017, 23:40  [ТС] 6
stzer
Вот что я пока что навоял
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template<typename T>
void ListTree<T>::depthHelper(TreeNode<T>* ptr)
{
    static int left = 0, right = 0;
    //static int depthPtr;
    
    if(ptr != NULL)
    {
        depthHelper(ptr->leftPtr);  
        depthHelper(ptr->rightPtr);
        (ptr->rightPtr != NULL ? right++ : right);
        (ptr->leftPtr != NULL ? left++ : left);
    }
 
    depthRef = (left > right) ? left : right;
}
Вроде бы работает, но нет 100% уверенности...

Добавлено через 3 минуты
Цитата Сообщение от stzer Посмотреть сообщение
Все ответы на вопросы можете найти в книге R. Sedgewick. Alghorithms in C++.
Дейтелов читаю, как только закончу, если желание не отпадёт к изучению языка, то обязательно вернусь к вышеобозначенной книге!
0
129 / 101 / 58
Регистрация: 26.10.2013
Сообщений: 306
03.08.2017, 23:52 7
Liss29, подайте на вход вашей функции дерево, состоящего из 1 узла и 0 ребер.
0
129 / 101 / 58
Регистрация: 26.10.2013
Сообщений: 306
04.08.2017, 00:09 8
Функция некорректно работает, если у нас дерево, например, такого вида:

Узлы, в которых нет цифр - просто NULL. Ищите ошибку =)
1
Миниатюры
Определить количество уровней двоичного дерева поиска  
32 / 21 / 4
Регистрация: 18.11.2012
Сообщений: 933
04.08.2017, 23:46  [ТС] 9
stzer
Как не пробую, ничего не получается. Обходим левое поддерево, затем правое поддерево, а как узнать, что левое поддерево обошли, не могу никак въехать в это(

Добавлено через 3 часа 29 минут
А такой варик:
C++
1
2
3
4
5
6
7
8
9
template<typename T>
void ListTree<T>::depthHelper(TreeNode<T>* ptr)
{
    if(ptr != NULL)
    {
        depthRef++;
        (ptr->leftPtr != NULL) ? depthHelper(ptr->leftPtr) : depthHelper(ptr->rightPtr);
    }
}
Интересное задание, все нервы мне вымотало
0
129 / 101 / 58
Регистрация: 26.10.2013
Сообщений: 306
05.08.2017, 00:35 10
Liss29, неа, неправильно. Допустим у узла R есть два не NULL потомка. Функция пойдет рекурсивно исполняться только по левому поддереву, минуя правое. У правого поддерева высота может быть больше.
0
32 / 21 / 4
Регистрация: 18.11.2012
Сообщений: 933
05.08.2017, 04:06  [ТС] 11
Цитата Сообщение от stzer Посмотреть сообщение
У правого поддерева высота может быть больше.
Выше я спросил, как задать условие, которое способно определить конец левого поддерева и, если оно существует, начало правого поддерева, всю голову сломал, решения не нашёл
0
2572 / 2188 / 233
Регистрация: 03.07.2012
Сообщений: 7,896
Записей в блоге: 1
05.08.2017, 04:47 12
Цитата Сообщение от Liss29 Посмотреть сообщение
всю голову сломал, решения не нашёл
А что его искать - оно в первом ответе.
0
32 / 21 / 4
Регистрация: 18.11.2012
Сообщений: 933
06.08.2017, 21:35  [ТС] 13
Цитата Сообщение от zer0mail Посмотреть сообщение
А что его искать - оно в первом ответе.
ах, ну да, а я тут мозг ..бу себе и другим, так что ли..

Добавлено через 17 часов 6 минут
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
template<typename T>
void ListTree<T>::depthHelper(TreeNode<T>* ptr)
{
    static int left = 0, right = 0;
    left = high_left(ptr->leftPtr);
    right = high_right(ptr->rightPtr);
 
    depthRef = (left > right) ? (left + 1) : (right + 1);
}

Так работает, а как сделать так, чтобы не использовать вспомогательные функции?
0
32 / 21 / 4
Регистрация: 18.11.2012
Сообщений: 933
09.08.2017, 23:39  [ТС] 14
Интересно, а как удалить корневой узел двоичного дерева поиска? Получается, что родительский узел удаляемого элемента будет иметь адрес нуль, если удаляется корневой узел, я пробовал так:

Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//если родительский узел удаляемого узла нуль
if(rootNodeDelete == NULL) //коневой узел удаляемого узла 
{
    TreeNode<T>* tempPtr = ptr; //ptr - узел для удаления
    if(rootNodeR == NULL) //Корневой узел замещающего узла
    {
        //rootNodeDelete = new TreeNode<T>(deletePtr->data);
        
        //deletePtr - замещающий узел 
        deletePtr->leftPtr = ptr->leftPtr;
        deletePtr->rightPtr = ptr->rightPtr;
    }
    else //если у замещающего узла есть корневое значение 
    {
        /*deletePtr->leftPtr = ptr->leftPtr;
        deletePtr->rightPtr = ptr->rightPtr;
        rootNodeR->leftPtr = NULL;*/        
    }
    delete tempPtr;
    return;
}

Хотел указатели корневого значения присвоить замещающему узлу, которое должно стать новым корнем дерева, не знаю, мне это показалось вполне приемлемо. Что я делаю не так?
Но после удаления портирся адрес и в общем-то всё.
0
Заблокирован
10.08.2017, 00:20 15
Liss29, http://www.geeksforgeeks.org/b... -2-delete/
0
32 / 21 / 4
Регистрация: 18.11.2012
Сообщений: 933
10.08.2017, 19:47  [ТС] 16
Tree depthОтлично, только ничего не понял.

Добавлено через 15 часов 15 минут
Похоже разобрался, спасибо, "за помощь".
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
10.08.2017, 19:47

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Подсчет уровней в двоичном дереве поиска
каков алгоритм подсчета уровней в двоичном дереве поиска. спасибо.

Алгоритм реализации двоичного дерева
Нужно написать реализацию двоичного дерева с использованием шаблонов в упрощенном виде следуя...

Проверка корректности двоичного дерева
Здравствуйте! Задача такая, Свойство двоичного дерева поиска можно сформулировать следующим...

Обход двоичного дерева по уровням
Доброго времени! Нужно реализовать нерекурсивный обход двоичного дерева поиска по уровням, я...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
16
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.