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

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

30.11.2017, 20:47. Показов 13103. Ответов 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)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
30.11.2017, 20:47
Ответы с готовыми решениями:

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

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

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

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

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
0 / 0 / 0
Регистрация: 20.12.2016
Сообщений: 98
02.12.2017, 16:14  [ТС] 3
Цитата Сообщение от alex white Посмотреть сообщение
maxDepth(NULL) = 0
для чего эта строка?
0
1375 / 519 / 72
Регистрация: 21.07.2015
Сообщений: 1,304
02.12.2017, 16:22 4
Цитата Сообщение от Tanya228 Посмотреть сообщение
в интернете не нашел никаких примеров
Да не гони. https://www.google.ru/search?n... -60Pql5Cdo
0
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 / 5764 / 265
Регистрация: 11.08.2016
Сообщений: 3,557
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
0 / 0 / 0
Регистрация: 20.12.2016
Сообщений: 98
02.12.2017, 17:36  [ТС] 8
Ivandur, не понимаю, что делает функция max()
0
694 / 5764 / 265
Регистрация: 11.08.2016
Сообщений: 3,557
02.12.2017, 17:43 9
max - максимум двух чисел.
1
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
02.12.2017, 18:06
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
02.12.2017, 18:06
Помогаю со студенческими работами здесь

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru