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

Максимальная глубина дерева

26.10.2015, 23:12. Показов 5737. Ответов 10
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Помогите пожалуйста написать программу: Определить максимальную глубину дерева,т.е число узлов в самом длинном пути от корня дерева до листьев
Вот что у меня получилась написать
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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
 
 
class TREE{
public:
    struct tree{
        int data;
        int view;//для обхода дерева
        struct tree *Left;
        struct tree *Right;
        struct tree *Prev;//для стека
    };
struct tree *Work;
struct tree *Root;
 
void Create(int i);
void PushTree(int i);
void PrintTree();
void DeleteTree();
 
private: void CreateStack(void);
         struct tree *top;
         void PushStack(struct tree *a);
         void PopStack();
};
 
void TREE::CreateStack(void){
    Root->Prev=NULL;
    top=Root;
}
 
 void TREE::PushStack(struct tree *a){
     a->Prev=top;
     top=a;
 }
 
 void TREE::PopStack(){
     top=top->Prev;
 }
 
void TREE::Create(int i){
    Work=(struct tree*)malloc(sizeof(struct tree));
    Work->Left=NULL;
    Work->Right=NULL;
    Work->data=i;
    Work->view=-1;
    Root=Work;
}
 
void TREE::PushTree(int i){
    Work=Root;
    while(Work!=NULL){//Поиск листа для добавления
        if(i<Work->data){
            if(Work->Left==NULL){
                break;
            }
            Work=Work->Left;
        }
    else{
        if(Work->Right==NULL){
            break;
        }
        Work=Work->Right;
        }
    }
//Добавление нового узла
    if(i<Work->data){//Левый сын
        Work->Left=(struct tree*)malloc(sizeof(struct tree));
        Work=Work->Left;
        Work->Left=NULL;
        Work->Right=NULL;
        Work->data=i;
        Work->view=-1;
    }
    else{//Правый сын
        Work->Right=(struct tree*)malloc(sizeof(struct tree));
        Work=Work->Right;
        Work->Left=NULL;
        Work->Right=NULL;
        Work->data=i;
        Work->view=-1;
    }
}
 
void CreateTree(TREE &BST){ 
    srand(time(NULL));
    int i;
    i=rand()%20+1;
    printf("%s%d","Data: ",i);
    BST.Create(i);//Создаем корень
    for(int j=0; j<9; j++){//Остальные узлы
        i=rand()%20+1;
        BST.PushTree(i);
        printf("%  d",i);
    }
}
 
void TREE::PrintTree(){
    printf("\n\n");
    CreateStack();
    int i=0;
    while(top!=NULL){
        while(top->Right!=NULL&&top->Right->view!=0){
            PushStack(top->Right); 
            i++;
        }
        if(top->view==-1){
            for(int j=i; j>0; j--){
                printf("\t");
            }
            printf(" %d\n",top->data);
            top->view=0;//0-напечатана, -1-не напечатана
        }
        if(top->Left!=NULL&&top->Left->view==-1){
            PushStack(top->Left); 
            i++; 
            continue;
        }
        PopStack();
        i--;
    }
}
 
void TREE::DeleteTree(){
    CreateStack();
    int i=0;
    while(top!=NULL){
        while(top->Right!=NULL){
            Work=top;
            PushStack(top->Right);
            Work->Right=NULL;
        }
        if(top->Left!=NULL){
            Work=top;
            PushStack(top->Left); 
            Work->Left=NULL;
            continue;
        }
        if(top->Left==NULL&&top->Right==NULL){
            Work=top;
            PopStack();
            free(Work);
        }
    }
}
 
void main(){
    TREE BST;
    CreateTree(BST);
    BST.PrintTree();
    BST.DeleteTree();
}
int getMaxDepth(struct tree* t, int depth)
{
if (t == NULL) 
return depth; 
return max(getMaxDepth(t->Left, depth + 1), getMaxDepth(t->Right, depth + 1));
}
Но в последней строчке ругается
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
26.10.2015, 23:12
Ответы с готовыми решениями:

По какой формуле рассчитывается максимальная глубина рекурсии (в том числе косвенной)?
Где-то я читал, что программа падает только при 50 миллионах итераций. При этом размер оперативной памяти на том компьютере не написан. У...

Глубина бинарного дерева
На одном сайте, вроде как сурьезном читаю про деревья. столкнулся вот с таким примером вычисления глубины дерева // Эта функция...

Максимальная глубина списка
Есть список, написать программу, возвращающую максимальную глубину списка.

10
 Аватар для Хулиган
88 / 83 / 21
Регистрация: 08.08.2012
Сообщений: 737
27.10.2015, 00:24
C++
1
#include <algorithm>
для std::max
0
2784 / 1937 / 570
Регистрация: 05.06.2014
Сообщений: 5,602
27.10.2015, 00:36
1) struct tree *Work; . В плюсах эта хрень с подписыванием всюду "struct" не нужна.
2) Так короче:
C++
1
2
3
4
5
6
7
struct tree
{
    ...
    int getMaxDepth()const
    {
        return this?1+max(left->getMaxDepth(),right->getMaxDepth()):0;
    }
0
Эксперт С++
 Аватар для hoggy
8973 / 4319 / 960
Регистрация: 15.11.2014
Сообщений: 9,760
27.10.2015, 04:50
Цитата Сообщение от Renji Посмотреть сообщение
this?
компилятор имеет право оптимизировать проверку валидности this.
и в релизе ноль не вернется никогда
1
0 / 0 / 1
Регистрация: 24.02.2014
Сообщений: 17
27.10.2015, 16:49  [ТС]
Renji, Не работает
0
88 / 84 / 31
Регистрация: 18.11.2013
Сообщений: 390
27.10.2015, 16:56
Цитата Сообщение от andrei4ik1997 Посмотреть сообщение
Renji, Не работает
Так тебе сказали:
Цитата Сообщение от Хулиган Посмотреть сообщение
#include <algorithm>
для std::max
0
0 / 0 / 1
Регистрация: 24.02.2014
Сообщений: 17
27.10.2015, 22:07  [ТС]
Krock21rus, все равно у меня ошибка выскакивает https://gyazo.com/84c1c3d480d085ea0ae98f5e1096a986
0
88 / 84 / 31
Регистрация: 18.11.2013
Сообщений: 390
28.10.2015, 22:15
странно, чего это такую ошибку не заметили:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
 
 
class TREE{
public:
    struct tree{
        int data;
        int view;//для обхода дерева
        struct tree *Left;
        struct tree *Right;
        struct tree *Prev;//для стека
    };
struct tree *Work;
struct tree *Root;
обьявить структуру в классе?
замените на

C++
1
2
3
4
5
6
7
8
9
    struct tree{
        int data;
        int view;//для обхода дерева
        tree *Left;
        tree *Right;
        tree *Prev;//для стека
    };
struct tree *Work;
struct tree *Root;
эмм, возможно верхнее не верно, есть 2 варианта:
либо у вас не дописан class TREE(нет Root)(вероятнее так)
либо у вас неправильно определено

Цитата Сообщение от Renji Посмотреть сообщение
1) struct tree *Work; . В плюсах эта хрень с подписыванием всюду "struct" не нужна.
уберите ВСЕ struct из программы, оставьте только в одном месте, при объявлении
0
0 / 0 / 1
Регистрация: 24.02.2014
Сообщений: 17
29.10.2015, 01:00  [ТС]
Krock21rus, убрал все но все равно ругается с той же ошибкой) Попробуйте,скинуть мне весь код может я что то неправильно удалил
0
88 / 84 / 31
Регистрация: 18.11.2013
Сообщений: 390
30.10.2015, 13:36
код написан с неправильным синтаксисом и плохой реализацией, может вы скажете всю задачу(откуда берётся дерево, каким методом нужно найти)
0
0 / 0 / 1
Регистрация: 24.02.2014
Сообщений: 17
31.10.2015, 01:27  [ТС]
Krock21rus, Вот задание с методички:
Создать проект для работы с деревом поиска, содержащий последующие обработчики, которые должны:
– ввести информацию (лучше, используя StringGrid), состоящую из целочисленного ключа и строчки текста (к примеру, номер паспорта и ФИО);
– записать информацию в дерево поиска;
– сбалансировать дерево поиска;
– добавить в дерево поиска новейшую запись;
– по данному ключу отыскать информацию и показать ее;
– удалить из дерева поиска информацию с данным ключом;
– распечатать информацию прямым, обратным обходом и в порядке возрастания ключа;
– решить одну из следующих задач: Определить максимальную глубину дерева,т.е число узлов в самом длинном пути от корня дерева до листьев


Вот сама метода:http://www.bsuir.by/m/12_100229_1_93670.pdf
Лаба №8 Вариант 4
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
31.10.2015, 01:27
Помогаю со студенческими работами здесь

Глубина дерева
Найти глубину бинарного дерева.

Глубина бинарного дерева
Доброго времени суток. Помогите пожалуйста написать процедуру вычисления глубины бинарного дерева. program derevo; uses crt; type...

Неправильно считается глубина бинарного дерева
Вот весь код модуля: module Nat where data Nat = Zero | Succ Nat deriving (Show, Eq, Ord) instance Num Nat where ...

Глубина списка и упорядоченность бинарного дерева
вобщем есть такое задание:  Определить функцию, вычисляющую глубину списка (самой глубокой ветви).  Определить функцию для...

Бинарные деревья, глубина (высота) дерева
Есть дерево, состоящее из целых чисел , читаемых из файла. С выводом и нахождением высоты дерева понятно. Как можно вывести все ветви,...


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

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Новые блоги и статьи
Отображение реквизитов в документе по условию и контроль их заполнения
Maks 04.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .
Фото всей Земли с борта корабля Orion миссии Artemis II
kumehtar 04.04.2026
Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .
Вывод диалогового окна перед закрытием, если документ не проведён
Maks 04.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .
Программный контроль заполнения реквизита табличной части документа
Maks 02.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать контроль заполнения реквизита "ПричинаСписания". . .
wmic не является внутренней или внешней командой
Maks 02.04.2026
Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/
Программная установка даты и запрет ее изменения
Maks 02.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .
Вывод данных в справочнике через динамический список
Maks 01.04.2026
Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .
Программное заполнения текстового поля в реквизите формы документа
Maks 01.04.2026
Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru