Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.64/64: Рейтинг темы: голосов - 64, средняя оценка - 4.64
 Аватар для Tanya228
0 / 0 / 0
Регистрация: 20.12.2016
Сообщений: 98
1

Найти максимальную глубину дерева

30.11.2017, 20:47. Показов 13209. Ответов 9
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
C++ Скопировано
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include "stdafx.h"
#include <iostream>
 
using std::cout;
using std::cin;
using std::endl;
 
struct TNode {
    int data;
    TNode* left;
    TNode* right;
};
 
void add(TNode *&tr, int d) {
 
    if (tr == NULL) {
        tr = new TNode;
        tr->data = d;
        tr->left = tr->right = 0;
    }
 
    if (d < tr->data)
        add(tr->left, d);
    if (d > tr->data)
        add(tr->right, d);
 
}
 
int branches(TNode *&tr, int n) {
    int count = 0;
    if (tr == NULL)
        return 0;
    
    if (tr->data == n)
        return count;
    
    return ++count + branches(((tr->data > n) ? tr->left : tr->right), n);
    
}
 
void depth_path(TNode *&tr) {
    int count = 0, count2 = 0;
 
    if (!tr) 
        cout << "\nДерева не существует\n";
    
    if (tr->left == 0 && tr->right == 0)
        cout << "\nМаксимальная глубина дерева: " << count << endl;
    
 
}
 
void tree_print(const TNode* tr) {
    if (tr == NULL)
        return;
    else {
        tree_print(tr->left);
        cout << tr->data << ' ';
        tree_print(tr->right);
    }
}
 
void input_data(TNode *&tr, int dt) {
    int n = 0;
    cout << "Введите количество элементов: \n"; cin >> n;
 
    while (n--) {
        cout << "Введите элемент: "; cin >> dt;
        add(tr, dt);
    }
}
 
void del(TNode *&tr) {
    if (tr != NULL) {
        del(tr->left);
        del(tr->right);
        delete tr;
        tr = NULL;
    }
}
 
int main() {
 
    setlocale(LC_ALL, "rus");
    TNode* tree;
    int data = 0, temp = 0, n = 0; // n - для подсчета ветвей, темп - для хранения ветвей
    tree = NULL;
 
    input_data(tree, data);
 
    cout << endl;
    tree_print(tree);
    
    cout << "\nКакую цифру хотите найти: "; cin >> n;
    temp = branches(tree, n);
    
    cout << "\nКоличество ветвей: " << temp << "\n";
    del(tree);
 
    system("pause");
    return 0;
}
Как найти глубину самого длинного пути дерева, в интернете не нашел никаких примеров, в основном только вывод, создание деревьев?
0
Лучшие ответы (1)
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
30.11.2017, 20:47
Ответы с готовыми решениями:

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

Найти максимальную сумму элементов на ярусе дерева
Найти максимальную сумму элементов на ярусе дерева

Бинарное дерево поиска (определить максимальную глубину)
Всем привет! Делаю лабу, написал основу, но не могу понять, как сделать последний пункт задания, нужно определить максимальную глубину...

9
277 / 226 / 93
Регистрация: 27.06.2016
Сообщений: 639
30.11.2017, 22:18 2
Поиском в глубину.
maxDepth(NULL) = 0
maxDepth(n) = 1 + maxDepth(n->left, n->right)
0
 Аватар для Tanya228
0 / 0 / 0
Регистрация: 20.12.2016
Сообщений: 98
02.12.2017, 16:14  [ТС] 3
Цитата Сообщение от alex white Посмотреть сообщение
maxDepth(NULL) = 0
для чего эта строка?
0
1377 / 521 / 72
Регистрация: 21.07.2015
Сообщений: 1,304
02.12.2017, 16:22 4
Цитата Сообщение от Tanya228 Посмотреть сообщение
в интернете не нашел никаких примеров
Да не гони. https://www.google.ru/search?n... -60Pql5Cdo
0
 Аватар для Tanya228
0 / 0 / 0
Регистрация: 20.12.2016
Сообщений: 98
02.12.2017, 16:24  [ТС] 5
shmkv, плохо искал, наверное
0
277 / 226 / 93
Регистрация: 27.06.2016
Сообщений: 639
02.12.2017, 17:22 6
Лучший ответ Сообщение было отмечено Tanya228 как решение

Решение

Tanya228,
Пардон:
maxDepth(NULL) = 0
maxDepth(n) = 1 + max(maxDepth(n->left), maxDepth(n->right))
1
694 / 6012 / 265
Регистрация: 11.08.2016
Сообщений: 3,636
02.12.2017, 17:33 7
C++ Скопировано
1
2
3
4
5
int maxDepth(TNode* T)
{
if (T==NULL) return 0;
return max(maxDepth(T->left),maxDepth(T->right))+1;
}
0
 Аватар для Tanya228
0 / 0 / 0
Регистрация: 20.12.2016
Сообщений: 98
02.12.2017, 17:36  [ТС] 8
Ivandur, не понимаю, что делает функция max()
0
694 / 6012 / 265
Регистрация: 11.08.2016
Сообщений: 3,636
02.12.2017, 17:43 9
max - максимум двух чисел.
1
 Аватар для Tanya228
0 / 0 / 0
Регистрация: 20.12.2016
Сообщений: 98
02.12.2017, 18:06  [ТС] 10
Ivandur, большое спасибо.
shmkv, там просто дичь пишут, вот здесь дали нормальный понятный ответ.
А вот еще вопрос, у меня есть функция branches():
C++ Скопировано
1
2
3
4
5
6
7
8
9
10
11
int branches(TNode *&tr, int n) {
    int count = 0;
    if (tr == NULL)
        return 0;
 
    if (tr->data == n)
        return count;
 
    return ++count + branches(((tr->data > n) ? tr->left : tr->right), n);
 
}
Функция находит количество ветвей до заданной вершины. Я ввожу вершину и ищет все нормально, но если ввожу несуществующую вершину, он мне выдает место, где бы эта вершина располагалась, я писал различные условия, но ничего не выходит, если не трудно, помогите.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
02.12.2017, 18:06
Помогаю со студенческими работами здесь

Хитрый обход дерева в глубину
По условию необходимо обойти дерево так чтобы найти путь max длины не имеющий кратных вершин, приэтом советуют пользоваться алгоритмом с...

Реализация обхода в ширину и глубину бинарного дерева
Как реализовать обход дерева (глубины три, т.е. трех уровневое) в глубину и ширину и что под этим подразумевается?

Найти максимальную оценку студента и вывести его ID потом фамилию и максимальную оценку
Здравствуйте! Мне нужно найти максимальную оценку студента и вывести его ID потом фамилию и макс оценку Вот образец INPUT: 3 1...

Найти максимальную глубину дерева
найти максимальную глубину дерева

Найти максимальную и минимальную глубину дерева
1)вести дерево с клавиатуры 2)определить max глубину дерева 3)определить min глубину дерева


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

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

Редактор формул (кликните на картинку в правом углу, чтобы закрыть)
Новые блоги и статьи
Предотвращение XSS, CSRF и SQL-инъекций в JavaScript
run.dev 13.03.2025
JavaScript занимает первые позиции среди языков веб-разработки, но его распространенность делает его привлекательной целью для злоумышленников. Межсайтовый скриптинг (XSS), межсайтовая подделка. . .
PHP 8.x: JIT-компиляция и улучшение производительно­сти
Jason-Webb 13.03.2025
PHP никогда не славился своей скоростью. Многие сталкивались с проблемами производительности при работе со сложными вычислениями или обработкой больших объемов данных. Традиционная модель выполнения. . .
Сериализация данных с Apache Avro в Kafka
Javaican 12.03.2025
Apache Kafka стала одним из ключевых решений для работы с большими потоками данных. Однако с ростом объемов передаваемых данных возникает проблема: как эффективно сериализовать и десериализовать. . .
Создание потребителей Kafka с помощью Reactor Kafka
Javaican 12.03.2025
Reactor Kafka — это библиотека, объединяющая Apache Kafka с реактивным программированием на базе Project Reactor. Такое сочетание позволяет строить неблокирующие, асинхронные приложения с контролем. . .
Ключевые слова Python
py-thonny 12.03.2025
Ключевые слова — не просто часть синтаксиса, а настоящий каркас языка, определяющий его возможности и ограничения. В Python существует 35 ключевых слов и 4 так называемых "мягких ключевых слова" —. . .
Сортировка в Python: Подробный обзор sorted() и .sort()
py-thonny 12.03.2025
В Python для решения задач сортировки предусмотрены два основных инструмента: функция sorted() и метод . sort(). На первый взгляд, различия между ними могут показаться незначительными, но когда дело. . .
Автоматизация задач в HCL Notes
Mr. Docker 12.03.2025
Если вы когда-нибудь работали с HCL Notes (раньше известным как Lotus Notes), то наверняка испытали смешанные чувства. С одной стороны, это мощная платформа для корпоративных приложений, с другой —. . .
Установка и настройка HCL Notes
Mr. Docker 12.03.2025
HCL Notes (ранее известный как IBM Notes и Lotus Notes) — это не просто почтовый клиент, а целая корпоративная платформа для коллективной работы. Если вы когда-нибудь попадали в компанию, где все. . .
Разработка API GraphQL в Java
Javaican 12.03.2025
Технология GraphQL, созданная Facebook в 2012 году и выпущенная в открытый доступ в 2015, постепенно превратилась из экспериментальной альтернативы REST в один из основных подходов к созданию API. . . .
Производительны­е API с Java и gRPC
Javaican 12.03.2025
Традиционные подходы к построению API, такие как REST, долгое время доминировали на рынке, но растущие требования к производительности, масштабируемости и надежности заставляют инженеров искать. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru
Выделить код Копировать код Сохранить код Нормальный размер Увеличенный размер